今回はChompというゲームに関する小ネタです. Chompは石を使って2人で遊ぶゲームです.石をに並べます.プレイヤーは図のようにある1つの石を選んで,そこより右上にある石を全て取り去ります.これを交互に繰り返して,一番左下の石を取った方が負けです. 実はChompは先手必勝であることを示すことができます(このブログで以前紹介した手法です。ぜひ考えてみてください)が,今回はその話ではなく,ゲームが有限の手数で終わるかどうかという点に着目します. もちろんChompそのものは,有限個の石が一手ごとに減っていくわけなので,自明に有限手数で決着がつきます. しかし,石が右と上方向に無限に続いているという設定にした「無限Chomp」を考えると話は難しくなります.果たして無限Chompは有限手数で決着がつくのでしょうか? 実は無限Chompは必ず有限の手数で終わることが証明できます.このことはもち