数学2 因数定理･剰余の定理 問題 14 解説

方針・初手

(1) は問題のルールに従い、与えられた数列のシャッフル操作を3回繰り返して直接求める。

(2) は数列の前半部分と後半部分に分けて、シャッフル後の位置 $f(k)$ を式で表す。前半の要素と後半の要素がそれぞれどの位置に移動するかを一般化し、$f(k) - 2k$ が $2N+1$ の倍数になることを確かめる。

(3) は (2) の結果を合同式を用いて解釈する。(2) より $f(k) \equiv 2k \pmod{2N+1}$ が成り立つため、シャッフルを繰り返す操作は、法 $2N+1$ のもとで $2$ を掛け続ける操作と同値である。これを利用して $2n$ 回の操作後の位置を評価する。

解法1

(1)

$N=4$ の場合であり、初期状態の数列は $\{1, 2, 3, 4, 5, 6, 7, 8\}$ である。 シャッフル操作を行うと、数列を前半 $\{1, 2, 3, 4\}$ と後半 $\{5, 6, 7, 8\}$ に分け、後半の項と前半の項を交互に並べることになる。

1回目のシャッフル：

$$ \{5, 1, 6, 2, 7, 3, 8, 4\} $$

2回目のシャッフル（前半 $\{5, 1, 6, 2\}$ と後半 $\{7, 3, 8, 4\}$）：

$$ \{7, 5, 3, 1, 8, 6, 4, 2\} $$

3回目のシャッフル（前半 $\{7, 5, 3, 1\}$ と後半 $\{8, 6, 4, 2\}$）：

$$ \{8, 7, 6, 5, 4, 3, 2, 1\} $$

したがって、3回シャッフルしたときに得られる数列は $\{8, 7, 6, 5, 4, 3, 2, 1\}$ である。

(2)

数列 $\{1, 2, \cdots, 2N\}$ において、数 $k$ の初期位置は $k$ である。 シャッフル後の位置 $f(k)$ を、前半と後半に分けて考える。

(i) $1 \leqq k \leqq N$ のとき 数 $k$ は元の数列の前半の $k$ 番目（すなわち $a_k$）である。 シャッフルの規則により、$a_k$ は $b_1, a_1, \cdots, b_k, a_k$ と並ぶため、新しい数列での位置は $2k$ 番目となる。 よって、$f(k) = 2k$ である。 このとき、

$$ f(k) - 2k = 0 $$

となり、$0$ は任意の整数の倍数であるから、$2N+1$ で割り切れる。

(ii) $N+1 \leqq k \leqq 2N$ のとき 数 $k$ は元の数列の後半の $k-N$ 番目（すなわち $b_{k-N}$）である。 シャッフルの規則により、$b_{k-N}$ は $b_1, a_1, \cdots, a_{k-N-1}, b_{k-N}$ と並ぶため、新しい数列での位置は $2(k-N)-1$ 番目となる。 よって、$f(k) = 2k - 2N - 1$ である。 このとき、

$$ f(k) - 2k = -(2N+1) $$

となり、これは $2N+1$ で割り切れる。

(i), (ii) より、任意の $1 \leqq k \leqq 2N$ に対して、$f(k) - 2k$ は $2N+1$ で割り切れる。

(3)

(2) の結果より、任意の $k$ ($1 \leqq k \leqq 2N$) に対して、

$$ f(k) \equiv 2k \pmod{2N+1} $$

が成り立つ。

数列を $m$ 回シャッフルした後の数 $k$ の位置を $f_m(k)$ と表すことにすると、$1$ 回のシャッフルごとに位置の番号は法 $2N+1$ で $2$ 倍されるため、

$$ f_m(k) \equiv 2^m k \pmod{2N+1} $$

が成り立つ。

いま、$N = 2^{n-1}$ であり、操作を $2n$ 回繰り返す場合を考える。 法となる値は $2N+1 = 2 \cdot 2^{n-1} + 1 = 2^n + 1$ である。 この法 $2^n+1$ において、

$$ 2^n \equiv -1 \pmod{2^n+1} $$

が成り立つため、両辺を $2$ 乗すると、

$$ 2^{2n} \equiv (-1)^2 = 1 \pmod{2^n+1} $$

となる。

したがって、$2n$ 回シャッフルした後の位置 $f_{2n}(k)$ は、

$$ f_{2n}(k) \equiv 2^{2n} k \equiv 1 \cdot k = k \pmod{2N+1} $$

を満たす。

ここで、$f_{2n}(k)$ および $k$ はいずれも $1$ 以上 $2N$ 以下の整数であるから、

$$ -(2N-1) \leqq f_{2n}(k) - k \leqq 2N-1 $$

である。この範囲において $2N+1$ の倍数となるのは $0$ のみであるから、

$$ f_{2n}(k) = k $$

となる。 これは、全ての数が元の位置に戻ることを意味しており、数列 $\{1, 2, 3, \cdots, 2N\}$ は $\{1, 2, 3, \cdots, 2N\}$ に戻る。

解説

(2)の証明を通して、シャッフル操作による要素の移動が、法 $2N+1$ における「2倍」の操作として表現できることを見抜くのが本問の核心である。(3)では、$f_{2n}(k) \equiv k \pmod{2N+1}$ が示された後に、「値域の制約から差が $0$ になる」という合同式から等式への論理の橋渡しを忘れずに記述する必要がある。法に関する周期性を利用した典型的な整数と数列の融合問題である。

答え

(1) $\{8, 7, 6, 5, 4, 3, 2, 1\}$

(2) 任意の $1 \leqq k \leqq 2N$ について $f(k)$ を前半と後半に分けて立式し、それぞれで $f(k) - 2k$ が $0$ または $-(2N+1)$ となることから証明された。

(3) $f_{2n}(k) \equiv 2^{2n}k \equiv k \pmod{2N+1}$ となることを示し、$1 \leqq f_{2n}(k) \leqq 2N$ かつ $1 \leqq k \leqq 2N$ であることから $f_{2n}(k) = k$ が成り立つことで証明された。