Math Pro 數學補給站's Archiver

人生沒有太多的應該,
只有感謝。

waitpub 發表於 2012-2-4 13:09

2001 TRML 團體賽一題

題目:[b][i][font=標楷體][size=4][color=#111111]在1、2、...、2001中,最少要取出多少個數,
才能保證其中必有相異兩數的和為10的倍數?[/color][/size][/font][/i][/b]
[i][font=標楷體][size=4][color=#111111]題目是從網友彬爸珍媽的部落格下載下來的。[/color][/size][/font][/i]
[url=http://cplee8tcfsh.blogspot.com/2007/02/blog-post.html]http://cplee8tcfsh.blogspot.com/2007/02/blog-post.html[/url]
也看了網友tsusy寫的詳解。
[url=http://tsusy.files.wordpress.com/2011/09/trml2001team.pdf]http://tsusy.files.wordpress.com/2011/09/trml2001team.pdf[/url]
對詳解內容不太能理解!
可否請板上老師解釋一下這題。

tsusy 發表於 2012-2-4 18:49

回復 1# waitpub 的帖子

題目說「最少」,所以思考上其實就點像是一些不等式做極值的時候

1. 先找出下界
注意只要那群數里有任兩個 個位數相加為 10, 那就有了.

所以如果要取一個最多個數的反例,個位 1 和 9 ,必取 1,因為 1 的多一個,是 201

個位 2 和 8, 只能其中一組全取 200 個

3 和 7 、 4 和6 同上,而 0 和 5 只能取一個,不然像 10+20, 5+15 就會有十的倍數。

所以一供 803了

2.證明 804 個時,一定有兩個數相加為 10 的倍數

這時候就要應用鴿籠原理,去說明像 1,9 或 2,8 或 3,7 或 4,6 或 5,5 或 0,0 的配對至少會出現一組

用鴿籠,其實就是再走一次剛剛 803 怎麼來的…

[[i] 本帖最後由 tsusy 於 2012-2-4 06:54 PM 編輯 [/i]]

頁: [1]

論壇程式使用 Discuz! Archiver 6.1.0  © 2001-2007 Comsenz Inc.