僕：数学が好きな高校生。
ミルカさん：数学が好きな高校生。僕のクラスメート。長い黒髪の《饒舌才媛》。
リサ：自在にプログラミングを行う無口な女子。赤い髪の《コンピュータ少女》。
双倉図書館
今日、僕はミルカさんに呼び出されてここにやってきた。 《変幻ピクセル》のイベントはもうとっくに終わったから、 何もないはずなんだけどな。
広いイベントホールに入ると、 大きなスクリーンにオセロを切り取ったような映像が映っていた。 白と黒の石がたくさん並び、くるくると白黒反転を繰り返している。
そして、スクリーンの前にはコントローラを操作しているミルカさんが立っていた。 傍らにはリサもいる。
僕「何やってるの？ ゲーム？」
ミルカ「おっと」
リサ「注意力不足」
ミルカ「ちょうどいい。彼も来たし、休憩にしよう」
僕「二人でゲームしていたの？」
ミルカ「いや、これは一人ゲーム。フリップ・トリップだよ。 単純といえば単純なゲームだけど、おもしろい」
僕「フリップ・トリップ？」
ミルカ「私は《変幻ピクセル》に来れなかったからな（第103回・第104回「変幻ピクセル」参照）。 君も参加できなかっただろう？ リサに機材の一部をもう一度出してもらった。いっしょに遊ぼう」
リサ「迷惑」
僕「《変幻ピクセル》の話はユーリから聞いたよ。（第107回・第108回「コンプリメント・コンプレックス」参照） リサちゃんからコンピュータのことたくさん教えてもらったって喜んでたよ。 ありがとう」
リサ「《ちゃん》は不要……大したこと、話してない（咳）」
フリップ・トリップ
僕「でも、フリップ・トリップとかいうゲームについては聞かなかったなあ。これはどういうゲームなの？」
ミルカ「さっき私がやっていた《フリップ・トリップ $8$ 》は難しすぎるから、《フリップ・トリップ $4$ 》にしよう」
リサ「説明パネル」
- 盤面には $4$ 個の石がある。表が黒、裏が白である。
- スタートボタンを押すと、 $4$ 個の石はすべて白になる。
- 反転ボタンが $4$ 個あり、押した反転ボタンに対応した石は白黒反転する。
僕「ええと？ まず、スタートボタンを押すと全部白になる、と」
僕「そして、反転ボタンを押したら、それに対応した石は白から黒になるんだね。たとえば、反転ボタン $1$ を押すと、白白黒白ということかな」
僕「そして反転ボタン $0$ を押すと、白白黒黒」
ミルカ「白なら黒になるが、黒なら白になる」
僕「ということは、もう一度ボタン $0$ を押すと、白白黒白に戻るんだね」
ミルカ「同じパターンを出してしまったらエラーになる。スタートしてから、白白黒白は出た。もう一度それを出したからエラーになった。 それがフリップ・トリップ」
リサ「説明パネル」
- スタートボタンを押してから現れた石のパターンは、すべて記録されている。
- 反転ボタンの操作で石のパターンを作ったとき、過去に登場したパターンを作ってしまったら、エラーでゲーム終了となる。この場合、プレイヤーの負けである。
- ただし、すべてのパターンを尽くして白白白白に戻れたなら、フルトリップでゲーム終了となる。この場合、プレイヤーの勝ちである。
僕「過去に登場したパターンを作ってしまったらエラー……ということは、同じパターンを作らないように反転ボタンを操作して、 全部のパターンを作るってこと？」
ミルカ「端的に言えば、そうなるな」
リサ「重複パターン禁止」
僕「うーん……そうか、さっきは「白白白白→白白黒白→白白黒黒→白白黒白」と操作してしまったからエラーになったんだ。 白白黒白が二回出たから。 待てよ、 $4$ 個の石があって、それぞれ白黒二通りあるんだから、 全部で $16$ 個のパターンがある。 ということは、これまで出たパターンを最大 $16$ 個記憶しなくちゃいけないってことか」
ミルカ「まあ、記憶したければ」
僕「いやいや、簡単か。だって、 $2$ 進法を使って数えるのと同じことをすればいいからね」
ミルカ「というと？」
僕「白を $0$ として、黒を $1$ として考えると、 $0000,0001,0010,0011,0100,0101,\ldots$ のように、 $2$ 進法で数を数えていくようにビットパターンを作っていけばいい。 そうすれば、 $4$ ビットのビットパターンすべてを尽くせるから……おっと！ それじゃだめか」
ミルカ「だめだね」
$$ \begin{array}{rcc} n & \text{ $n$ のビットパターン} \\ \hline 0 & 0000 \\ 1 & 0001 \\ 2 & 0010 \\ 3 & 0011 \\ 4 & 0100 \\ 5 & 0101 \\ 6 & 0110 \\ 7 & 0111 \\ 8 & 1000 \\ 9 & 1001 \\ 10 & 1010 \\ 11 & 1011 \\ 12 & 1100 \\ 13 & 1101 \\ 14 & 1110 \\ 15 & 1111 \\ \end{array} $$
僕「そうだなあ。反転ボタンを $1$ 回押すだけで、 $2$ 進法で $+1$ したビットパターンが作れるとは限らないからなあ…… $0000$ から $0001$ を作るのはいい。でも、 $0001$ から $0010$ を作るのはできない。 $0001$ から $0010$ を作ろうとすると、 $000\UL{1}$ と、 $00\UL{0}1$ の二つのビットを反転しなくちゃいけない。 でもたとえば、 $000\UL{1}$ のビットを反転したとたん、 $0000$ というビットパターンができてしまい……」
ミルカ「……そこでエラーになるわけだ」
僕「できないとは限らないか。 $000\UL{1}$ を先に反転するんじゃなく、 $00\UL{0}1$ を先に反転すればいけるかも……なるほどね。 このフリップ・トリップのポイントがやっとわかったよ。 $0000$ から $1111$ までのすべてのビットパターンを作るんだけど、 次のビットパターンに移るときには、 《過去のビットパターンと重ならない》ようにしつつ、 しかも《一度には $1$ ビットしか反転しちゃいけない》わけだね」
ミルカ「そういうこと」
僕「え……でも、そんなことできるのかな。だって、フルトリップするためには、最後に $0000$ に戻らないといけないんだよね。 $1111$ から、 $1$ ビット反転で $0000$ にはいけないよ」
ミルカ「 $2$ 進法に引きずられている。最後の一歩手前は $1111$ とは限らない。ちょっとやってみせよう」
僕「ううん……速すぎてわからなかったけど、確かに《フルトリップ》を達成できそうなことはわかったよ」
フリップ・トリップで、スタートボタンを押してから、 $3,2,1,0$ の四つの反転ボタンをどの順番で押せば、 フルトリップできるだろうか。
この連載について
数学ガールの秘密ノート
数学青春物語「数学ガール」の中高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わいましょう。本シリーズはすでに12巻も書籍化されている大人気連載です。 （毎週金曜日更新）
