第1問

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

A

と表す）と青銅貨（

B

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

n

枚のアルミニウム貨と

n

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

k\le2n

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

k

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

n

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

(n,k)

（

1\le k\le2n

）をすべて求めよ。

ステップ 3/5:

k

がチェーンの内部にあれば二つのチェーンが融合する

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

ざっくり言うと

中間のチェーンを前方へ移動すると、それに隣接する同種の二つのチェーンが一つに結合するので、チェーンの総数は減ることしかできない。

B_1=[l',l-1],\quad B_2=[m+1,m']

詳しい解説

$k$ が $l>1$ 、 $m<2n$ （最初でも最後でもないチェーン）を満たすチェーン $[l,m]$ の内部にあるとする。 $[l,m]$ を前方へ移動すると、その直前のチェーン $B_1=[l',l-1]$ と直後のチェーン $B_2=[m+1,m']$ が隣接するようになる。 $B_1$ と $B_2$ は同じ硬貨の種類なので一つのチェーンに融合し、チェーンの総数は厳密に減少する。