第4問

n

と

k

を正の整数とする。Cathy は次のゲームを行う。

1

から

n

までの番号がついた

n

個のビー玉と

k

個の箱があり、最初はすべてのビー玉が一つの箱に入っている。各手番で Cathy は一つの箱を選び、その中で最小の番号（これを

i

とする）をもつビー玉を、空の箱か、またはビー玉

i+1

が入っている箱へ移す。ある時点でビー玉

n

だけが入った箱ができれば Cathy の勝ちである。Cathy が勝てるような整数の組

(n,k)

をすべて求めよ。

ステップ 1/4: 連続区間の不変量と可逆性

\text{Every non-empty box holds a consecutive interval }\{a,a+1,\ldots,b\};\ \text{moves are reversible}

詳しい解説

最初、開始の箱には $\{1,\ldots,n\}$ が入っている。Cathy は常に箱の最小元を取り出し、空の箱に入れるか別の箱の最小元 $i+1$ の上に重ねるだけなので、空でない各箱には常に連続した番号の区間が入り、また任意の合法手の逆操作も合法手である。