發新話題
打印

109新北市能力競賽複試二

推到噗浪
推到臉書

109新北市能力競賽複試二

第七題
從1~120這120個正整數中取出n個數,使得沒有一個數是另一個數的2倍,則n的最大值是多少?

解答是80

想了很久但想不到該怎麼下手,還請各位大大幫幫我,感謝!

TOP

回復 1# Gary 的帖子

先考慮後半段61-120,再來考慮這些前面1-60乘上兩倍不會在61-120裡面,全部最多有1-30的奇數,
最後還有一些偶數在1-30裡面,這些偶數有個特性就是乘上兩倍不為1-30的奇數的兩倍,兩倍後數也可以在31-60裡面。

[ 本帖最後由 PDEMAN 於 2021-10-4 11:49 編輯 ]

TOP

回復 1# Gary 的帖子

首先61,63,65....119,這30個不為別數兩倍也不會被別數兩倍的數,一定要全選,少選一個就損失一個.
接下來62,64,66....120,這30個可以考慮全選,因為例如少選一個64,則只可多選一個32,但16又不能選了.
最後選1,3,5...29有15個以及4,8,12,16,20,24,28這7個中最多只能挑5個,如4,12,16,20,28.
因此n最多30+30+15+5=80
本以為從1~3m這3m個正整數中取出n個數,使得沒有一個數是另一個數的2倍,則n的最大值是2m,
但是m=7時,即 1~21中卻可挑出1,3,4,5,11,12,13,14,15,16,17,18,19,20,21共15(>2m)個數.

[ 本帖最後由 laylay 於 2021-10-5 10:08 編輯 ]

TOP

每次向下切一半,一段選一段不選
61-120選
31-60不選
16-30選
8-15不選
4-7選
2-3不選
1-1選
60+15+4+1

TOP

回復 1# Gary 的帖子

本題有兩個方式可以進行而且重點是要說明為何能是最多個數的取法.
1.由小而大能取就取的取法(此為總和最小的取法) :
   以1,2 這兩數而言有 A:只取1 , B:只取2 ,C:都不取 三種選擇 , 針對後面的3--120取法而言A,C是一樣的,但C顯然就比A少取一個,
   故C不能採用,又B顯然比A少了一個4可以選,故A可以保證是最多個數的取法.
   取了1之後,2馬上刪掉,接下來以3,6這兩數而言有 A:只取3 , B:只取6 ,C:都不取 三種選擇 , 針對後面的4--120(不含6)取法而言A,C是一樣
   的,但C顯然就比A少取一個, 故C不能採用,又B顯然比A少了一個12可以選,故A可以保證是最多個數的取法.如此以同樣方式由小
   而大能取就取的取法進行下去,就可以保證是最多個數的取法.由此法我們會選出1,3,5..119共60個奇數,當然2的奇數倍全數刪除,以及 還有
   4的倍數.......4,12,16,20,28,36,44,48,52,60,64,68,76,80,84,92,100,108,112,116 總共有60+20=80 個數是最多個數的取法.
2.由大而小能取就取的取法(此為總和最大的取法) :
   以120,60 這兩數而言有 A:只取120 , B:只取60 ,C:都不取 三種選擇 , 針對前面的119--1(不含60)取法而言A,C是一樣的,但C顯然就比A少取一個, 故C不能採用,又B顯然比A少了
   一個30可以選,故A可以保證是最多個數的取法.
   如此我們選出(120,119...61),(30,29...16),(7,6,5,4),(1)共60+15+4+1總共有80 個數是最多個數的取法.

[ 本帖最後由 laylay 於 2021-10-14 09:14 編輯 ]

TOP

發新話題