Evolton

東京大学 2002年度 前期日程 第2次学力試験理系数学 第6問

Nを正の整数とする.
2N個の項からなる数列{a1,a2,⋯ ,aN,b1,b2,⋯ ,bN}を{b1,a1,b2,a2,⋯ ,bN,aN}という数列に並べ替える操作を「シャッフル」と呼ぶことにする.
並べ替えた数列はb1を初項とし,
biの次にai,aiの次にbi+1が来るようなものになる.
また,数列{1,2,⋯ ,2N}をシャッフルしたときに得られる数列において,
数kが現れる位置をf(k)で表す.

たとえば,N=3のとき,
{1,2,3,4,5,6}をシャッフルすると{4,1,5,2,6,3}となるので,f(1)=2,f(2)=4,f(3)=6,f(4)=1,f(5)=3,f(6)=5である.

(1) 数列{1,2,3,4,5,6,7,8}を3回シャッフルしたときに得られる数列を求めよ.

(2) 1≦k≦2Nを満たす任意の整数kに対し,
f(k)−2kは2N+1で割り切れることを示せ.

(3) nを正の整数とし,N=2n−1のときを考える.
数列{1,2,3,⋯ ,2N}を2n回シャッフルすると,
{1,2,3,⋯ ,2N}にもどることを証明せよ.

難易度6/ 10計算量5/ 10目安18分

整数、数列 合同式、数学的帰納法、帰納的定義の利用、計算整理

方針

(1) は定義通りに、前半を ai、後半を bi と見て3回並べる。(2)は 1≦k≦N なら k=ak、N<k≦2N なら k=bk−N として、シャッフル後の位置 f(k) を直接求める。(3)は(2)から f(k)≡2k(mod2N+1) を得て、反復後の位置が 2mk と合同になることを帰納法で示す。N=2n−1 では 2N+1=2n+1 なので 22n≡1 を使う。

解答

(1) N=4 である。はじめの数列 {1,2,3,4,5,6,7,8} を {a1,a2,a3,a4,b1,b2,b3,b4} と見ると、1回シャッフルして {5,1,6,2,7,3,8,4} となる。

これをさらにシャッフルする。前半4項を a1,a2,a3,a4、後半4項を b1,b2,b3,b4 と見るので、2回目は {7,5,3,1,8,6,4,2} である。さらに3回目は {8,7,6,5,4,3,2,1} である。

(2)
まず 1≦k≦N とする。このとき、もとの数列のk番目の数kは ak である。シャッフル後、ak は 2k 番目に置かれるので f(k)=2k である。したがって f(k)−2k=0 であり、これは 2N+1 で割り切れる。

次に N<k≦2N とする。このとき k=bk−N である。シャッフル後、bk−N は 2(k−N)−1 番目に置かれるので f(k)=2(k−N)−1=2k−(2N+1) である。したがって f(k)−2k=−(2N+1) であり、これも 2N+1 で割り切れる。

よって任意の 1≦k≦2N について f(k)≡2k(mod2N+1) である。

(3) m 回シャッフルした後に、数 k が現れる位置を fm(k) とする。m=1 では(2)より f1(k)=f(k)≡2k(mod2N+1) である。

いま fm(k)≡2mk(mod2N+1) と仮定する。次にもう1回シャッフルすると、位置も同じ規則で移るので fm+1(k)=f(fm(k))≡2fm(k)≡2m+1k(mod2N+1) である。よって帰納法により fm(k)≡2mk(mod2N+1) がすべての正の整数 m で成り立つ。

ここで N=2n−1 だから 2N+1=2n+1 である。したがって 2n≡−1(mod2N+1) であり、両辺を2乗して 22n≡1(mod2N+1) である。よって f2n(k)≡22nk≡k(mod2N+1) となる。

最後に、f2n(k) も k も 1 以上 2N 以下の整数である。この範囲の2つの整数が 2N+1 を法として合同なら、実際に等しい。したがって f2n(k)=k である。これはすべての k で成り立つので、2n 回シャッフルすると元の数列 {1,2,3,…,2N} にもどる。

【位置は法 2N+1 で2倍】

別解

解法2

方針

位置 1,…,2N を法 2N+1 の非零剰余として扱う。1回のシャッフルが剰余の2倍写像であることから、反復を一度に計算する。

解答

(1) (1,2,3,4,5,6,7,8)⟼(5,1,6,2,7,3,8,4)⟼(7,5,3,1,8,6,4,2)⟼(8,7,6,5,4,3,2,1).(2)
1≦k≦N なら f(k)=2k、N<k≦2N ならf(k)=2(k−N)−1=2k−(2N+1).従って常にf(k)≡2k(mod2N+1).(3)
m 回後の位置を fm(k) とすれば、上の合同式を反復してfm(k)≡2mk(mod2N+1).N=2n−1 のとき2N+1=2n+1,2n≡−1(mod2N+1).従ってf2n(k)≡22nk≡k(mod2N+1).f2n(k) と k はともに 1,…,2N の範囲にあるため実際に等しい。すべての k が元の位置へ戻るので、数列全体も元に戻る。

総評

難度は10段階中6、計算量は10段階中5。目安時間は18分。採点ポイントは、シャッフル後の位置を f(k) として明確に式で表すこと、f(k)≡2k(mod2N+1) を作ること、反復後も位置が同じ合同式で管理できることを帰納法で示すことである。誤りやすいのは、数そのものと位置を混同すること、また最後に合同だけでなく 1≦f2n(k),k≦2N だから等しいと確認する点を落とすことである。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る東大の整数の問題で問題集を作る

出典: 東京大学 2002年度 前期 数学。問題文はHTML表示のために再入力・数式組版しています。