越南奧賽題：海姑娘蛋糕上的蠟燭解答

來源: constant

	海姑娘蛋糕上點了120根蠟燭。趁著海姑娘不在，腦賊和獅子玩吹蠟燭的遊戲，規則如下：每人每次可以吹滅一根，或吹滅n-[n/3]根，其中n是當時點著的蠟燭的根數，即剩下[n/3]根。例如第一次可以剩下119根或40根。腦賊先吹，誰能贏？ 後來海姑娘出來了，看到自己的得力部下輸了，覺得不公平，又點了3000多根蠟燭，說：“這回你該贏了。”海姑娘又點了多少根蠟燭？ 容易看出3根蠟燭是負狀態，4根蠟燭是勝狀態得到11根蠟燭是勝狀態（可以到3），12根蠟燭是負狀態（隻能到4或11），13根蠟燭是勝狀態。再乘3，得38根蠟燭勝（可以到12），39根蠟燭負（隻能到13或38），40根蠟燭勝。再乘3，得119根勝，120根負。因此腦賊負。 用歸納法可以證明(3^k-5)/2根蠟燭勝，(3^k-3)/2根蠟燭負，(3^k-1)/2根蠟燭勝。為了讓腦賊勝，海姑娘可以點3278或3280根蠟燭。

•  通解好像很麻煩。 -亂彈- ♂   (0 bytes) (10 reads) 9/1/06  •  回複：通解好像很麻煩。 -trytosee- ♂   (721 bytes) (10 reads) 9/1/06  •  期待中 -亂彈- ♂   (0 bytes) (3 reads) 9/1/06