東大2002 大問6(3) の簡潔な解法

この著者は初心者として投稿しています。間違いや考慮が足りていない点が含まれている可能性が高いです。見つけたらコメント欄で優しく指摘してあげましょう。

本題

$n$を整数とする。数列$\{a_1,\dots,a_{2^{n-1}},b_1,\dots,b_{2^{n-1}}\}$に対して、数列を$\{b_1,a_1,b_2,a_2,\dots,b_{2^{n-1}},a_{2^{n-1}} \}$ に置き換える操作をシャッフルと呼ぶ。数列$\{1,2,\dots,2^n\}$に対してシャッフルを$2n$回行うと元の数列に戻ることを示せ。

数列の値、添え字ともに0-indexed で考えます。シャッフルを一回行った数列において、$k$が現れる位置を$f(k)$とすると、
$$f(k)= \left\{ \begin{array}{ll} 2k+1 & (0 \leq k < 2^{n-1}) \\ 2(k-2^{n-1}) & (2^{n-1}\leq k < 2^n) \end{array} \right.$$
が成立します。$k$ を$n$桁の$2$進数で考えることにすると次のように対応します。
$$f(k)= \left\{ \begin{array}{ll} kを1ビット左シフトしたのち1足した数 & (k の最上位ビットが0のとき) \\ kを1ビット左シフトした数 & (k の最上位ビットが1のとき) \end{array} \right.$$
結局これは$k$の最上位ビットを反転して末尾に追加しているだけです。したがって、$n$回、シャッフル($k=f(k) と置き換える)$すると$k$は最初の$k$をビット反転させたものとなり、$2n$回シャッフルすると元に戻ります。

投稿日：8時間前

更新日：7時間前

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

AaAa

他の人のコメント

コメントはありません。

読み込み中

AaAa

東大2002 大問6(3) の簡潔な解法