IMO 2022
問題 1

あるコインの並べ方について，左から $k$ 枚目のコインを含む最も長い鎖を左に移すことを繰り返すことでもとの並べ方に戻るとき，その並べ方を $k$不変な並べ方であると呼ぶ．

$$\underbrace{AA\cdots A}_{n-1}\underbrace{B\cdots B}_{n}A$$

は $k=1,\dots,n-1$ に対して $k$ 不変であり，

$$\underbrace{A\cdots A}_{n-\lfloor n/2\rfloor}\underbrace{B\cdots B}_{n-\lfloor n/2\rfloor}\underbrace{A\cdots A}_{\lfloor n/2\rfloor}\underbrace{B\cdots B}_{\lfloor n/2\rfloor}$$

は $k=n+1-\lfloor n/2\rfloor,\dots,n$ に対して $k$ 不変である．

ある $AA\cdots ABB\cdots B$ でも $AA\cdots ABB\cdots B$ でもない並べ方 $X$ とある整数 $n\leq k\leq n-\lfloor n/2\rfloor$ が存在して，$X$ が $k$ 不変であると仮定すると，$X$ に含まれる鎖の数は $4$ 以上の偶数なので，$X$ に含まれるある鎖があって，その鎖の長さは $\lfloor n/2\rfloor$ 以下である．従って操作を繰り返すと，最も右でも最も左でもない鎖が存在して，それが左に移される．この操作によって鎖の数は減り，$X$ が $k$ 不変であることに矛盾する．よって並べ方 $X$ は $k$ 不変でなく，操作によって $k$ 不変になったとき，それは $AA\cdots ABB\cdots B$ または $AA\cdots ABB\cdots B$ のいずれかに一致する．

以上より，求める組 $(n,k)$ は $n\leq k\leq n-\lfloor n/2\rfloor$ なる組全体である．