東京大学前期 2002年第6問 (解答解説)

を正の整数とする． 2個の項からなる数列を

という数列に並べ替える操作を「シャッフル」と呼ぶことにする．並べ替えた数列はを初項とし，の次に，の次にが来るようなものになる．また，数列をシャッフルしたときに得られる数列において，数が現れる位置をで表す．

たとえば，のとき，をシャッフルするととなるので，

である．

【解答】

最初からスタートすると，具体的に回シャッフルした時の並び替えは

回 シ ャ ッ フ ル 回 シ ャ ッ フ ル 回 シ ャ ッ フ ル

である．よって回シャッフルした結果はである．

を回シャッフルした後における数（）の位置をと表す．また最初の配置はとする．回目での遷移を考えると以下の漸化式を得る．

の 時 ， の 時 ，

題意から最初シャッフルする前は，一回シャッフルするとだから， (式4)においてとして

の 時 ， の 時 ，

となり，を計算すると

の 時 ， の 時 ，

だから，いずれもはで割り切れる．

以下合同式の法をとする． (式4)から，，いずれの場合も

だから，くり返し用いて初項は(2)よりだから

である．回シャッフルした時のことを考えるから，として

である．

ここでだから，法がであること（区間の幅が法より小さいこと）より，合同から等号が従い

である．よって題意は示された．