第1問

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

A

と表す）と青銅貨（

B

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

n

枚のアルミニウム貨と

n

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

k\le2n

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

k

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

n

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

(n,k)

（

1\le k\le2n

）をすべて求めよ。

ステップ 1/5: 凍結した配置により

k<n

を除外する

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

ざっくり言うと

$k$ が小さいとき、ある配置は $k$ 番目の硬貨を、左端に完全には到達し得ないほど短いチェーンの中に永久に留めておくことができる。

A\ldots A\,B\ldots B\,A

詳しい解説

$k<n$ のとき、初期配置 $A\ldots A\,B\ldots B\,A$ （ $A$ の塊、続いて $n$ 枚すべての $B$ 、最後に $A$ 一枚）を、 $k$ 番目の硬貨が常に先頭の長い $A$ チェーンの中にあるように選ぶ。操作を行うとその同じチェーンが前方へ移動するだけで配置は変わらず、左端の $n$ 枚が単一種類になることは決してない。