越南奥赛题：海姑娘蛋糕上的蜡烛解答

来源: 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