七五三ゲームにおける棒の消し方の総数が割ときれいだった話

最初に結論

$${n=2m}$$　 のとき　　$${m(m+1)}$$ 通り
$${n=2m+1}$$のとき　　$${(m+1)^2}$$通り

割ときれいじゃないです？

七五三ゲームとは

交互に棒を消していって最後に消した方が負け、のあのゲーム。
実は攻略法があることが知られていて、(3,5,7)の場合は先手必勝。
有名なのだと(1,2,3)や(2,2)は後手の勝ち。
この形を相手に渡せるようにがんばる。

で、必勝法ですが、ググったらいくつか出てくると思います。
たいてい二進数表記してからXOR。
(分銅に変えてる本もありましたが、要はそういうこと)
この辺考えると最後消した方の勝ちにしたくなるかも。

さて、必勝法はすでに知られていますが、
棒の消し方について考えてみましょう。

まずはルールから

棒の消し方のルール

・横一列で線を引いて棒を消す
・段やすでに消えている棒をまたいで消すことはできない
・必ず1本は消す
実際に遊んでいるときに間違えることはあんまりないかもしれません。
要するに、横に並んでいる棒を一本の線で引くだけです。シンプル！

棒の数が少ないときは割と簡単に総数がわかります。
例えば3本あった場合

全部消す・一本残す・連続2本残す・両端を残す

の4通り。もう少し数が増えると、

1本…1通り
2本…2通り
3本…4通り
4本…6通り
5本…9通り
6本…12通り
7本…16通り

本来の753ゲームは最大が7本なのでこれで良いんですが、
一般化したくなりますよね？

漸化式

さて、上の1~7までを検証していく時に何となく漸化式が見えてきます。

$${a_1=1 \quad a_2=2 \quad a_{n+2}=a_n+n}$$

単に端から消していくとn通り。間を消したい場合は両端を除いた棒の消し方と同じなので2つ前の結果を参照する、といった感じです。

で、これを解くと冒頭で示した

$${n=2m}$$　 のとき　　$${m(m+1)}$$ 通り
$${n=2m+1}$$のとき　　$${(m+1)^2}$$通り

と、割ときれいな式が出てた！良さげ！
特に奇数の時なんて二乗なので表を見てれば気付けそうな式ですが、
出てきた途中式に気を取られて全然見えてなかったです。

おもろいね、という話でした。途中式が気になった方は是非やってみてください。一見めんどくさい式に見えますが、意外と楽に答えが出てきます。