發新話題
打印

2001 TRML 團體賽一題

推到噗浪
推到臉書

2001 TRML 團體賽一題

題目:在1、2、...、2001中,最少要取出多少個數,
才能保證其中必有相異兩數的和為10的倍數?

題目是從網友彬爸珍媽的部落格下載下來的。
http://cplee8tcfsh.blogspot.com/2007/02/blog-post.html
也看了網友tsusy寫的詳解。
http://tsusy.files.wordpress.com/2011/09/trml2001team.pdf
對詳解內容不太能理解!
可否請板上老師解釋一下這題。

TOP

回復 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 怎麼來的…

[ 本帖最後由 tsusy 於 2012-2-4 06:54 PM 編輯 ]
網頁方程式編輯 imatheq

TOP

發新話題