ひたすら受験問題を解説していくブログ
スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
東京大学2002年前期数学第6問
todai_2002_math_6q.png

解説


見慣れない感じの問題ですが,群論だのオイラーの定理だのの話を聞いたことあると割りとすぐに見えてくるものがあるのではないでしょうか。闇雲に考えるとなると(3)は難問で,(2)の適切な誘導がきらりと光ります。
このように余りで操作を考えることはよくあることです。例えば受験史上最難問とか言われている東大後期1998年第3問(グラフの論証)も,余りで操作を考えていけば解けた記憶があります。

(1)
単純に3回やってもいいですが,有限要素の置換(入れ替え)操作は多くとも”要素数の階乗+1”回以内に繰り返すので(鳩ノ巣原理),繰り返し構造ありきで1回目の操作を見ていきましょう(Nまでは順に偶数,N+1以降は順に奇数)。
1→2
2→4
3→6
4→8
5→1
6→3
7→5
8→7
となり,順にたどれば,1→2→4→8→7→5→(1)の繰り返しと,3→6→(3)の繰り返しの2グループに分かれます。
さて,3回のシャッフルなので,右に3ずれればいいことになります。でも,答えるときは1がどこに来るよりも,1番目が何かの方が手っ取り早いので,逆向きに3戻りましょう。
{8,7,6,5,4,3,2,1}
きれいに逆向きになるんですね。

(2)
aになるかbになるかで挙動が違うので場合分けします(abの境目に対して対称なので,本当は全く同じ挙動なんですけどね)。

(i)1≦k≦Nのとき
偶数を順に占めるので,f(k)=2kです。よって,f(k)-2k=0≡0(mod 2N+1)

(ii)N+1≦k≦2Nのとき
N+1がbの1項目,つまり,k-Nがbの何番目かであり,奇数を順に占めていくので,f(k)=2(k-N)-1です。よって,f(k)-2k=-2N-1≡0(mod 2N+1)

(i)(ii)より,f(k)-2kは2N+1で割り切れます。

(3)
2N+1の余り基準で考えれば,1から2Nの整数はすべて識別できます。(2)より,
f(k)-2k≡0(mod 2N+1)
なので,
f(k)≡2k(mod 2N+1)
です。よって,2n回繰り返せば,
f2n(k)≡22nk(mod 2N+1)
になるので,
22n≡1(mod 2N+1)
を示せばOKです。

2N+1=2n+1
であることから,
2n≡-1(mod 2N+1)
であり(ここで(1)で丁度逆順になっていることも思い出すといいかもしれません),
22n≡1(mod 2N+1)
です。

よって,
f2n(k)≡22nk(mod 2N+1)≡k(mod 2N+1)
となり,置換である以上
f2n(k)=k
にしかなりえません。
スポンサーサイト

テーマ:大学受験 - ジャンル:学校・教育

コメント
コメント
コメントの投稿
URL:
本文:
パスワード:
非公開コメント: 管理者にだけ表示を許可する
 
トラックバック
トラックバック URL
http://jukenkaisetsu.blog.fc2.com/tb.php/270-ed45d6ee
この記事にトラックバックする(FC2ブログユーザー)
トラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。