1957年(昭和32年)東京大学-数学(一般数学)[3]

2022.02.13記

[3] 甲乙両人が次のようなゲームをする．まず机の上に 個の碁石をおき，その中から甲乙交互に幾個かの碁石を取る．ただし，一回に取る碁石の個数は1 個または2 個または3 個とし，相手が取った個数と同数の碁石をその直後に取ることは許されない．このようにして机の上の碁石の数をへらしてゆくうちに，しまいには碁石を取ることができなくなる．最初に取れなくなったものを負けとする（たとえば，乙が3 個取って机の上の碁石がなくなれば甲の負けであり，乙が1 個取って1 個残しても甲の負けである）． が4 の倍数であって，甲から取り始めるものとすれば，甲がどのような取り方をしても，乙は甲に勝つことができる．このことを証明せよ．

2022.02.11記
この石取りゲームは有名で、Tales of Phantasia にも登場する。

[解答]
甲が 個取った次に乙が 個取るようにすると，甲の番に戻ったとき碁石は常に4個減っていることになるので，続けていくとやがて甲の番に戻ったときの碁石の数は丁度4個となり，その次に甲がどのようにとっても，乙は机の碁石をなくすことができるので乙が勝つことになる。