第110回 フリップ・トリップ(後編)

「単純なパターンなのにいろんな表し方があるんだね」と僕はミルカさんに言った。
【お休みの予告】
結城浩です。いつもご愛読ありがとうございます。 おかげさまでこのWeb連載も今回で第110回を迎えることになりました! みなさまの応援に感謝します。

さて、たいへん恐れ入りますが、さらなるパワーアップをはかるため、 このWeb連載の更新を二週間お休みさせてください。

日程は以下の通りです。ご迷惑をおかけしますが、よろしくお願いいたします。

Web連載「数学ガールの秘密ノート」予定

・2015年3月13日(金)第110回更新
・2015年3月20日(金)お休み
・2015年3月27日(金)お休み
・2015年4月3日(金)第111回更新
・(以後、毎週金曜日更新)
$ \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 & \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$ 手目に動かす円板の番号になっているよね」

ミルカ「……」

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

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

この続きは有料会員登録をすると
読むことができます。
cakes会員の方はここからログイン

1週間無料のお試し購読する

cakesは定額読み放題のコンテンツ配信サイトです。簡単なお手続きで、サイト内のすべての記事を読むことができます。cakesには他にも以下のような記事があります。

人気の連載

おすすめ記事

ケイクス

この連載について

初回を読む
数学ガールの秘密ノート

結城浩

数学青春物語「数学ガール」の中高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わいましょう。本シリーズはすでに12巻も書籍化されている大人気連載です。 (毎週金曜日更新)

この連載の人気記事

関連記事

関連キーワード

コメント

kazuki_0014 |数学ガールの秘密ノート|結城浩 @hyuki |cakes(ケイクス) 難しいけどわかるところはわかるから面白い https://t.co/zSKCbkbzM9 5年以上前 replyretweetfavorite

brv00 "僕"がユーリっぽいよ? 5年以上前 replyretweetfavorite

l_sigma http://t.co/6dM66jfg6d ←アルゴリズムも試せるようになりました 5年以上前 replyretweetfavorite

siro_ni  ああああああああああ やっぱり先週みのがしたああああああああああ 5年以上前 replyretweetfavorite