第1問

オスロ銀行はアルミニウム貨（

A

と表す）と青銅貨（

B

と表す）の二種類の硬貨を発行している。マリアンヌは

n

枚のアルミニウム貨と

n

枚の青銅貨を任意の初期順序で一列に並べている。チェーンとは同じ種類の連続する硬貨からなる部分列のことである。固定された正の整数

k\le2n

に対して、マリアンヌは次の操作を繰り返し行う。左から

k

番目の硬貨を含む最長のチェーンを特定し、そのチェーンに含まれるすべての硬貨を列の左端に移動する。すべての初期順序に対して、操作の過程のある時点で左端の

n

枚がすべて同じ種類になるような組

(n,k)

（

1\le k\le2n

）をすべて求めよ。

ステップ 4/5:

n\le k\le\lceil3n/2\rceil

でチェーン数が減り続けることを示す

前のステップ次のステップ

n\le k\le\lceil3n/2\rceil\ \Rightarrow\ \text{chains keep merging until }2\text{ remain}

詳しい解説

$k$ が第一のチェーン $[1,l]$ （ $l\ge k\ge n$ ）に入るならば、ちょうど $l=n$ となり、これは既に求める結論である。一方 $k$ が最後のチェーンに入るならば、鳩の巣原理による数え上げにより、チェーンが少なくとも $4$ つあるときは常に $2n-k+1$ 枚未満のチェーンが存在し、 $k$ を保持する最後の位置を常に含むことはできない。したがって $k$ は最終的に内部のチェーンに入り（前のステップの融合を引き起こす）か、チェーンが $2$ つまたは $3$ つだけの配置になるかのいずれかとなり、この議論を繰り返すとチェーン数は $2$ まで下がり、その時点で左端の $n$ 枚は同じ種類になる。