lego54 wrote:
有150個洞,每個洞裡有一顆球
有150個人
第1個人過去 ~~ 把每個洞的球拿出來 ~~然後走開
第2個人過去 ~~把 2 的倍數的洞放 1 個球進去 ~
第3個人過去 ~~把 3 的倍數的洞放 1 個球進去 ~
但是如果原來洞裡就有球的時候~~則是把球拿出來~不放球進去
第4個人過去 ~~把 4 的倍數的洞放 1 個球進去 ~
但是如果原來洞裡就有球的時候~~則是把球拿出來~不放球進去
依此類推
請問第150個人作完上述動作後
這150個洞裡~~合計有多少球~~~~~~~
000000000000000000000<--第1個人走過後
010101010101010101010
011100011100011100011
011000001101011000001
011010001001010000011
011011001000010001011
011011101000000001010
011011111000000001010
011011110000000000010<--第9個人走過後
當第9個人走過後,前9洞的狀態不會再改變了
可以發現,只有1、4、9這幾個完全平方數的洞是沒有球的
為何完全平方數的洞會沒有球呢,因為會去碰它的人數,剛好是偶數
例如第4洞會有第2人、第4人去碰
第9洞會有第3人、第9人去碰
但是第18洞會有第2、3、6、9、18人去碰
所以非完全平方數的洞,最後一定是1
而完全平方數的洞有哪些呢
1、4、9、16、25....144 總共12個,所以有12個洞是空的,其他都是1顆球,總共138顆