[logo] Web連載「数学ガールの秘密ノート」
Share

第110回 シーズン11 エピソード10
フリップ・トリップ(後編)

書籍『数学ガールの秘密ノート/ビットとバイナリー』

この記事は『数学ガールの秘密ノート/ビットとバイナリー』として書籍化されています。

無料でWeb立ち読み アマゾンで購入

$ \newcommand{\TEXT}[1]{\textbf{#1}} \newcommand{\REMTEXT}[1]{\textbf{#1}} \newcommand{\UL}[1]{\underline{#1}} \newcommand{\BAR}[1]{\bar{#1}} \newcommand{\BAND}{\mathrel{\&}} \newcommand{\LAND}{\land} \newcommand{\LOR}{\,\lor\,} \newcommand{\NEQ}{\neq} \newcommand{\LEQ}{\leqq} \newcommand{\LEQX}{\preceq} \newcommand{\ORX}{\vee} \newcommand{\ANDX}{\wedge} \newcommand{\CUP}{\cup} \newcommand{\CAP}{\cap} $

登場人物紹介

:数学が好きな高校生。

ミルカさん:数学が好きな高校生。のクラスメート。長い黒髪の《饒舌才媛》。

リサ:自在にプログラミングを行う無口な女子。赤い髪の《コンピュータ少女》。

双倉図書館

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

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

「漸化式? 何の?」

リサ「グレイコード」

「グレイコード?」

リサ「お気に入り」

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

$4$ ビットのグレイコード

$$ \begin{array}{rcc} n & \REMTEXT{$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$ 手目に動かす円板の番号になっているよね」

ミルカ「……」

ミルカさんは一瞬だけ目を閉じる。そして楽しそうに微笑んだ。

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

無料で「試し読み」できるのはここまでです。 この続きをお読みになるには「読み放題プラン」へのご参加が必要です。

ひと月500円で「読み放題プラン」へご参加いただきますと、 427本すべての記事が読み放題になりますので、 ぜひ、ご参加ください。


参加済みの方/すぐに参加したい方はこちら

結城浩のメンバーシップで参加 結城浩のpixivFANBOXで参加

(2015年3月13日)

書籍『数学ガールの秘密ノート/ビットとバイナリー』

この記事は『数学ガールの秘密ノート/ビットとバイナリー』として書籍化されています。

書籍化にあたっては、加筆修正をたくさん行い、 練習問題や研究問題も追加しました。

どの巻からでも読み始められますので、 ぜひどうぞ!

無料でWeb立ち読み アマゾンで購入

[icon]

結城浩(ゆうき・ひろし) @hyuki


『数学ガール』作者。 結城メルマガWeb連載を毎週書いてます。 文章書きとプログラミングが好きなクリスチャン。2014年日本数学会出版賞受賞。

Twitter note 結城メルマガ Mastodon Bluesky Threads Home