数学2 多項式の割り算問題 14 解説

方針・初手

シャッフル操作によって、元の数列の $k$ 番目の項がどこに移動するかを数式で表現することが第一歩である。前半にある項と後半にある項で規則が変わるため、場合分けをして考える。合同式を用いると、シャッフルを繰り返す操作を簡潔に記述でき、見通しが良くなる。

解法1

(1) $N=4$ であり、与えられた数列は $\{1, 2, 3, 4, 5, 6, 7, 8\}$ である。シャッフルの規則に従い、後半の4項と前半の4項を交互に配置していく。

1回目のシャッフル：

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

2回目のシャッフル：

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

3回目のシャッフル：

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

(2) 元の数列において、左から $k$ 番目にある項が、シャッフル後に左から $f(k)$ 番目に移動するとする。

(i) $1 \leqq k \leqq N$ のときこの項は数列の前半に属し、問題文における $a_k$ に該当する。シャッフル後の数列は $\{b_1, a_1, b_2, a_2, \cdots\}$ となり、$a_k$ は偶数番目の $2k$ の位置に来る。よって、$f(k) = 2k$ である。このとき、

$$f(k) - 2k = 0 = 0 \times (2N+1)$$

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

(ii) $N+1 \leqq k \leqq 2N$ のときこの項は数列の後半に属し、後半の先頭から $k-N$ 番目の項であるので、$b_{k-N}$ に該当する。シャッフル後の数列において、$b_i$ は奇数番目の $2i-1$ の位置に来る。よって、$i = k-N$ として、

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

である。このとき、

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

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

(i)、(ii) のいずれの場合も、$f(k) - 2k$ は $2N+1$ で割り切れる。

(3) (2) の結果より、任意の $k$ に対して $f(k) - 2k \equiv 0 \pmod{2N+1}$、すなわち

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

が成り立つ。これは、1回のシャッフルで項の位置番号が法 $2N+1$ のもとで $2$ 倍になることを意味する。 $m$ 回シャッフルした後に、元の位置 $k$ にあった項が移動する位置を $f_m(k)$ とすると、これを繰り返すことで

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

が成り立つ。いま、$2n$ 回シャッフルした後の位置 $f_{2n}(k)$ を考えると、

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

となる。ここで、$N = 2^{n-1}$ であるから $2N+1 = 2^n+1$ であり、また $2^{2n} = (2^n)^2$ である。

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

であるから、両辺を2乗して

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

すなわち、

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

が成り立つ。したがって、

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

となる。 $f_{2n}(k)$ と $k$ はともに $1$ 以上 $2N$ 以下の整数であるから、その差の絶対値は $2N-1$ 以下である。

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

この範囲にある $2N+1$ の倍数は $0$ しか存在しないため、

$$f_{2n}(k) - k = 0 \iff f_{2n}(k) = k$$

となる。すべての $k$ ($1 \leqq k \leqq 2N$) について元の位置に戻るため、数列は $\{1, 2, 3, \cdots, 2N\}$ に戻ることが示された。

解説

いわゆる「パーフェクトシャッフル（アウトシャッフル・インシャッフル）」を題材にした整数・数列の問題である。 (1) の具体例を通してシャッフルの規則性を掴み、(2) でそれを定式化する誘導となっている。規則を立式する際、偶数・奇数の位置に行くことを正確に把握することが重要である。 (3) では、(2) で得られた「差が $2N+1$ の倍数」という条件を「法 $2N+1$ における合同式」と言い換える発想ができるかどうかが鍵となる。位置番号が $2$ 倍されていくという構造を見抜ければ、指数計算によって鮮やかに証明できる。