MathLabs

第1問

オスロ銀行はアルミニウム貨（AA と表す）と青銅貨（BB と表す）の二種類の硬貨を発行している。マリアンヌは nn 枚のアルミニウム貨と nn 枚の青銅貨を任意の初期順序で一列に並べている。チェーンとは同じ種類の連続する硬貨からなる部分列のことである。固定された正の整数 k≤2nk\le2n に対して、マリアンヌは次の操作を繰り返し行う。左から kk 番目の硬貨を含む最長のチェーンを特定し、そのチェーンに含まれるすべての硬貨を列の左端に移動する。すべての初期順序に対して、操作の過程のある時点で左端の nn 枚がすべて同じ種類になるような組 (n,k)(n,k)（1≤k≤2n1\le k\le2n）をすべて求めよ。
ステップ 2/5: 四チェーンの巡回により k>⌈3n/2⌉k>\lceil3n/2\rceil を除外する
前のステップ次のステップ
⌊n/2⌋, ⌈n/2⌉, ⌈n/2⌉, ⌊n/2⌋\lfloor n/2\rfloor,\ \lceil n/2\rceil,\ \lceil n/2\rceil,\ \lfloor n/2\rfloor
詳しい解説

k>⌈3n/2⌉k>\lceil3n/2\rceil のとき、A,B,A,BA,B,A,B と交互になる大きさ ⌊n/2⌋,⌈n/2⌉,⌈n/2⌉,⌊n/2⌋\lfloor n/2\rfloor,\lceil n/2\rceil,\lceil n/2\rceil,\lfloor n/2\rfloor の四つのチェーンを取る。最後のチェーンは少なくとも ⌊n/2⌋\lfloor n/2\rfloor 枚あるので、kk は常にその中に入り、それを前方へ移動すると四つのチェーンが単に回転するだけなので、パターンは永久に繰り返され、左端の nn 枚が一致することは決してない。