札幌の予備校・塾|大学受験(英語・数学)は札幌のマンツーマン個別指導塾、高上へお電話ください!大学受験において偏差値を上げる塾ですので、生徒の地力を底上げします。札幌駅、大通り駅にある予備校・塾のマンツーマン個別指導塾高上は、大学受験の英語、数学、物理、化学を静かな環境の個室で指導します。周りの声が邪魔になることはありません。英作文の添削、スカイプでの指導も全国どこからでも随時受け付けております。
お気軽にお問い合わせください。
TEL:080-1885-3972
受付時間:10:00~21:00
年中無休(相談などについては要予約)
※指導中はお電話に出られません。
お問い合わせページよりご連絡ください。
公開日:2020年10月6日
最終更新日:2020年10月16日

こんにちは。「ャに」です。
前回、合同式を解説しました (前回の記事はこちら)。
今回は合同式を利用して、大学入試の過去問を解いてみたいと思います。
問題は2002年東京大学理系 (理科一、二、三類) 前期試験数学の第6問です。
以下に問題とその解答例を示します。

問題
\(N\) を正の整数とする。\(2N\) 個の項からなる数列$$\{a_1, a_2, \dots, a_N, b_1, b_2, \dots, b_N\}$$を$$\{b_1, a_1, b_2, a_2, \dots, b_N, a_N\}$$という数列に並び替える操作を「シャッフル」と呼ぶことにする。並び替えた数列は \(b_1\) を初項とし、\(b_i\) の次に \(a_i\)、\(a_i\) の次に \(b_{i + 1}\) が来るようなものになる。また、数列 \(\{1, 2, \dots, 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 \leq k \leq 2N\) を満たす任意の整数 \(k\) に対し、\(f(k) – 2k\) は \(2N + 1\) で割り切れることを示せ。
(3) \(n\) を正の整数とし、\(N = 2^{n – 1}\) のときを考える。数列 \(\{1, 2, \dots, 2N\}\) を \(2n\) 回シャッフルすると、\(\{1, 2, \dots, 2N\}\) に戻ることを証明せよ。
解答例
(1) 数列 \(\{1, 2, 3, 4, 5, 6, 7, 8\}\) を \(1\) 回、 \(2\) 回、\(3\) 回シャッフルした数列はそれぞれ$$\begin{align*}&\{5, 1, 6, 2, 7, 3, 8, 4\},\\&\{7, 5, 3, 1, 8, 6, 4, 2\},\\&\{8, 7, 6, 5, 4, 3, 2, 1\}\end{align*}$$となる。
よって、求める数列は \(\{8, 7, 6, 5, 4, 3, 2, 1\}\) である。

(2) 数列 \(\{a_1, a_2, \dots, a_N, b_1, b_2, \dots, b_N\}\) をシャッフルすると、\(a_i\) は第 \(2i\) 項、\(b_i\) は第 \(2i – 1\) 項に移る。ただし、\(i \in \{1, 2, \dots, N\}\) である。
この数列が \(\{1, 2, \dots, 2N\}\) であるとき、\(a_i = i,\ b_i = N + i\) であるから、\(1 \leq k \leq 2N\) を満たす任意の整数 \(k\) に対して$$f(k) = \begin{cases}2k & (1 \leq k \leq N)\\2(k – N) – 1 = 2k – (2N + 1) & (N \lt k \leq 2N)\end{cases}$$となる。
よって、

i) \(1 \leq k \leq N\) のとき、$$\begin{align*}f(k) – 2k &\equiv 2k – 2k\\ &\equiv 0 \pmod{2N + 1},\end{align*}$$
ii) \(N \lt k \leq 2N\) のとき、$$\begin{align*}f(k) – 2k &\equiv \{2k – (2N + 1)\} – 2k\\ &\equiv -(2N + 1)\\ &\equiv 0 \pmod{2N + 1}\end{align*}$$

となり、題意が成り立つことがわかる。

(3) 数列 \(\{1, 2, \dots, 2N\}\) を \(i\) 回シャッフルしたときに得られる数列において、\(1 \leq k \leq 2N = 2^n\) を満たす任意の整数 \(k\) に対して、数 \(k\) が現れる位置を \(f^i(k)\) とおき、\(f^{2n}(k) = k\) を示せばよい。
まず、任意の正の整数 \(n\) に対して、\(f^n(k) \equiv 2^nk \pmod{2N + 1}\) であることを数学的帰納法で示す。

i) \(n = 1\) のとき、(2) より、\(f^1(k) – 2k = f(k) – 2k \equiv 0 \pmod{2N + 1}\) が成り立つので、\(f^1(k) \equiv 2k \pmod{2N + 1}\) となる。
ii) \(n = i\) (\(i\) は正の整数) のとき、\(f^i(k) \equiv 2^ik \pmod{2N + 1}\) が成り立つと仮定する。
\(n = i + 1\) のとき、\(i\) 回シャッフルしたときに得られる数列を \(\{a_1, a_2, \dots, a_N, b_1, b_2, \dots, b_N\}\) とおくと、

イ) \(f^i(k)\) が \(a_j\ (j \in \{1, 2, \dots, N\})\) の位置にあるとき、$$\begin{align*}f^{i + 1}(k) &\equiv f\left(f^i(k)\right)\\ &\equiv 2f^i(k)\\&\equiv 2\cdot 2^ik\\ &\equiv 2^{i + 1}k \pmod{2N + 1},\end{align*}$$
ロ) \(f^i(k)\) が \(b_j\ (j \in \{1, 2, \dots, N\})\) の位置にあるとき、$$\begin{align*}f^{i + 1}(k) &\equiv f\left(f^i(k)\right)\\ &\equiv 2f^i(k) – (2N + 1)\\ &\equiv 2\cdot 2^ik – (2N + 1)\\ &\equiv 2^{i + 1}k \pmod{2N + 1}\end{align*}$$

となり、\(f^n(k) \equiv 2^nk \pmod{2N + 1}\) となる。
いま、\(N = 2^{n – 1}\) とおくと、\(2N + 1 = 2^n + 1\) より、$$2^n \equiv -1 \pmod{2^n + 1}$$すなわち$$2^{2n} \equiv 1 \pmod{2^n + 1}$$が成り立つ。
したがって、$$\begin{align*}f^{2n}(k) &\equiv 2^{2n}k\\ &\equiv 1\cdot k\\ &\equiv k \pmod{2^n + 1}\end{align*}$$となる。
よって、\(1 \leq k \leq 2^n\) だから、$$f^{2n}(k) = k$$が成り立つ。

(1) はやるだけです。
\(3\) 回のシャッフルで数列が逆順になってますから、もう \(3\) 回シャッフルすれば元の数列に戻ることがわかります。
(3) でその事実を証明します。

(2) は \(k\) が \(a_i\) か \(b_i\) かで移り方が変わってきますので、そこで場合分けすればよいです。\(b_i\) となるときは \(b_i = N + i\ = k\) となりますから、\(i = k – N\) です。これを前の行の \(i\) に代入してます。

(3) は (2) をヒントに考えます。
\(f^2(k) = f\left(f(k)\right), f^3(k) = f\left(f^2(k)\right)\) を計算すると、\(2\) 倍ずつ増えていくことに気づきます。
\(f^{2n}(k) \equiv 2^{2n}k \equiv k \pmod{2^n + 1}\) を直接示す方法がちょっと思いつかない場合でも (2) の形が (ある意味?) ヒントになっていて、\(f^{2n}(k) – k\) の形であれば、$$\begin{align*}f^{2n}(k) – k &\equiv 2^{2n}k – k\\ &\equiv (2^{2n} – 1)k\\ &\equiv (2^n – 1)(2^n + 1)k\\ &\equiv 0 \pmod{2^n + 1}\end{align*}$$と因数分解で簡単に示すことができます。

ちゃんと確かめていないのでわかりませんが、指数の \(2n\) は$$2^{e} \equiv 1 \pmod{2^n + 1}$$をみたす最小の正の整数 \(e\) ではないかと思っています。
なにかわかったら更新します。
では。

この記事の著者

webma_user
記事一覧

高上は医学部合格率80%!
結果が出る指導を受けてみませんか?

 医学部合格実績を見る 

著者一覧