第110回 シーズン11 エピソード10

フリップ・トリップ（後編）

双倉図書館

僕「でも、なぜだろう？　現象としては理解したけど、 理由がわかってないぞ。なぜ、フリップ・トリップのゲームにルーラー関数が絡んでくるんだ？」

ミルカ「漸化式を考えてみればいい」

僕「漸化式？　何の？」

リサ「グレイコード」

僕「グレイコード？」

リサ「お気に入り」

ミルカ「君がいま作ったフリップ・トリップのパターンは、 $4$ ビットのグレイコードになる。 $0$ から $15$ までの非負整数 $n$ に対してグレイコードを $g(n)$ と表すことにすると、 $g(n)$ と $g(n+1)$ の $2$ 進法による表記は $1$ ビットしか違わないという性質がある」

僕「なるほど……確かにこれはさっき考えたフリップ・トリップのパターンだね（第109回参照）。 あ、でも、漸化式というのは？」

ミルカ「$n$ ビットのグレイコードの列を $G_n$ で表すことにする。 すなわち、 $G_4$ はさっきの表の通り、こうなる」

僕「うん、それで？」

ミルカ「君は数式が何よりも好きなんじゃなかったのか。 $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_3$」

僕「もうわかったよ」

ミルカ「次は？」

僕「次は $G_4$ だけど、もう一般化できるよ。 漸化式を考えるというのは、《$n+1$ ビットのグレイコードの列》を 《$n$ ビットのグレイコードの列》を使って表すということだから……」

ミルカ「そうなる」

僕「さっき $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$ を加えた列を得る操作》。 もう一つは、《列を逆順にした列を得る操作》。 だからこれを式で書けるように定義してやれば漸化式ができる」

僕「なるほどね」

ミルカ「そして、この漸化式で数学的帰納法を使えば、 グレイコードの各ビットパターンが $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$ 手目に動かす円板の番号になっているよね」

ミルカ「……」

ミルカ「ハノイの塔もまた、グレイコードの漸化式と対応付けて理解できるな」