結城浩です。いつもご愛読ありがとうございます。 おかげさまでこのWeb連載も今回で第110回を迎えることになりました！ みなさまの応援に感謝します。
さて、たいへん恐れ入りますが、さらなるパワーアップをはかるため、 このWeb連載の更新を二週間お休みさせてください。
日程は以下の通りです。ご迷惑をおかけしますが、よろしくお願いいたします。
Web連載「数学ガールの秘密ノート」予定
・2015年3月13日（金）第110回更新
・2015年3月20日（金）お休み
・2015年3月27日（金）お休み
・2015年4月3日（金）第111回更新
・（以後、毎週金曜日更新）
僕：数学が好きな高校生。
ミルカさん：数学が好きな高校生。僕のクラスメート。長い黒髪の《饒舌才媛》。
リサ：自在にプログラミングを行う無口な女子。赤い髪の《コンピュータ少女》。
双倉図書館
僕「でも、なぜだろう？ 現象としては理解したけど、理由がわかってないぞ。なぜ、フリップ・トリップのゲームにルーラー関数が絡んでくるんだ？」
ミルカ「漸化式を考えてみればいい」
僕「漸化式？ 何の？」
リサ「グレイコード」
僕「グレイコード？」
リサ「お気に入り」
ミルカ「君がいま作ったフリップ・トリップのパターンは、 $4$ ビットのグレイコードになる。 $0$ から $15$ までの非負整数 $n$ に対してグレイコードを $g(n)$ と表すことにすると、 $g(n)$ と $g(n+1)$ の $2$ 進法による表記は $1$ ビットしか違わないという性質がある」
$$ \begin{array}{rcc} n & \text{ $g(n)$ の $2$ 進表記} \\ \hline 0 & 0000 \\ 1 & 0001 \\ 2 & 0011 \\ 3 & 0010 \\ 4 & 0110 \\ 5 & 0111 \\ 6 & 0101 \\ 7 & 0100 \\ 8 & 1100 \\ 9 & 1101 \\ 10 & 1111 \\ 11 & 1110 \\ 12 & 1010 \\ 13 & 1011 \\ 14 & 1001 \\ 15 & 1000 \\ \end{array} $$
僕「なるほど……確かにこれはさっき（第109回参照）考えたフリップ・トリップのパターンだね。あ、でも、漸化式というのは？」
ミルカ「 $n$ ビットのグレイコードの列を $G_n$ で表すことにする。すなわち、 $G_4$ はさっきの表の通り、こうなる」
$$ G_4 = 0000, 0001, 0011, \ldots, 1011, 1001, 1000 $$僕「うん、それで？」
ミルカ「君は数式が何よりも好きなんじゃなかったのか。 $G_n$ に関する漸化式を作ってみよう」
僕「ちょっと待ってよ。 $G_n$ に関する漸化式ということは、 $G_{n+1}$ を $G_n$ であらわすということだろう？」
ミルカ「たとえば、そうなる」
僕「たとえば、等比数列は $a_{n+1} = ra_{n}$ のように式で書けるけど、でも、 $G_n$ はビットパターンの列だよね……計算はどうすれば？」
ミルカ「ビットパターンに対する操作や、列に対する操作を定義してやればいい」
僕「うーん……」
ミルカ「たとえば、 $G_1$ は具体的にどうなるか」
リサ「 $G_1 = 0, 1$ 」
ミルカ「リサには聞いてない」
リサ「テンポ遅すぎ」
ミルカ「しょうがないな。では次の $G_2$ は具体的にどうなるか」
僕「 $G_2$ は $2$ ビットのグレイコードということだから……こうだね」
$$ G_2 = 00, 01, 11, 10 $$ミルカ「次は $G_3$ 」
僕「もうわかったよ」
$$ G_3 = 000, 001, 011, 010, 110, 111, 101, 100 $$ミルカ「次は？」
僕「次は $G_4$ だけど、もう一般化できるよ。漸化式を考えるというのは、《 $n+1$ ビットのグレイコードの列》を 《 $n$ ビットのグレイコードの列》を使って表すということだから……」
$n$ ビットのグレイコードの列を $G_n$ で表すことにする。
$G_1 = 0, 1$ である。
$G_{n+1}$ は、以下の二つの列を続けた列である。
- $G_n$ の各ビットパターンの左に $0$ を加えた列
- $G_n$ を逆順にした列の、各ビットパターンの左に $1$ を加えた列
ミルカ「そうなる」
僕「さっき $G_4$ を作ったときと同じことをやればいいんだね。 $G_2 = 00, 01, 11, 10$ で、この左に $0$ を加えた列 $000,001,011,010$ は、 $G_3$ の前半になる。 そして、 $G_2$ を逆順にした列 $10,11,01,00$ の左に $1$ を加えた列 $110,111,101,100$ が、 $G_3$ の後半になる」
ミルカ「そういうこと。ここに出てくる基本操作は二つだけ。一つは《列中の各ビットパターンの左に $0$ や $1$ を加えた列を得る操作》。 もう一つは、《列を逆順にした列を得る操作》。 だからこれを式で書けるように定義してやれば漸化式ができる」
$n$ ビットのグレイコードの列を $G_n$ で表すことにすると、 $G_n$ の漸化式は次の通り。
$$ \left\{\begin{array}{llll} G_1 &= 0, 1 \\ G_{n+1} &= 0G_{n}, 1G'_{n} \\ \end{array}\right. $$
ただし、 $G'_{n}$ は $G_n$ を逆順にした列を表す。 また、 $xG_n$ は $G_n$ の各ビットパターンの前に $x$ を加えた列を表す。
僕「なるほどね」
ミルカ「そして、この漸化式で数学的帰納法を使えば、グレイコードの各ビットパターンが $1$ ビットずつ変化していくことも証明できる。 なぜなら、《 $G_{n}$ の最後のビットパターン》と《 $G'_{n}$ の最初のビットパターン》は等しいので、 《 $0G_{n}$ の最後のビットパターン》と《 $1G'_{n}$ の最初のビットパターン》は $1$ ビットだけ異なるといえるからだ」
僕「ふむふむ」
ミルカ「そしてこの漸化式によって、ルーラー関数 $-1$ がグレイコードの変化していくビット位置になる理由もわかる。 $G_n$ に含まれているビットパターンの個数は $2^n$ 個あり、 $G_{n+1}$ の前半 $0G_n$ と後半 $1G_n$ で切り替わるビット位置は $n$ だからね」
ハノイの塔
僕「ルーラー関数といえば、ユーリが《ハノイの塔》に似てるといってたよ（第108回参照）」
ミルカ「ほう？」
僕「ハノイの塔の円板を上から順に $1,2,3,\ldots$ と番号付けしたとすると、ルーラー関数の値 $\rho(n)$ は第 $n$ 手目に動かす円板の番号になっているよね」
ミルカ「……」
ミルカ「ハノイの塔もまた、グレイコードの漸化式と対応付けて理解できるな」
この連載について
数学ガールの秘密ノート
数学青春物語「数学ガール」の中高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わいましょう。本シリーズはすでに14巻以上も書籍化されている大人気連載です。 （毎週金曜日更新）
