2001TRML團體賽
題目:在1、2、...、2001中，最少要取出多少個數，才能保證其中必有相異兩數的和為10的倍數?題目是從網友彬爸珍媽的部落格下載下來的。
[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]
對詳解內容不太能理解!
可否請板上老師解釋一下這題。
回復 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 怎麼來的…
頁:
[1]