第109回 フリップ・トリップ(前編)

「そんなパターン、全部記憶できるの?」と僕はミルカさんに言った。
$ \newcommand{\UL}[1]{\underline{#1}} \newcommand{\BAR}[1]{\bar{#1}} \newcommand{\BAND}{\mathrel{\&}} \newcommand{\NEQ}{\neq} \newcommand{\LEQ}{\leqq} \newcommand{\LEQX}{\preceq} \newcommand{\ORX}{\vee} \newcommand{\ANDX}{\wedge} \newcommand{\CUP}{\cup} \newcommand{\CAP}{\cap} $
登場人物紹介
:数学が好きな高校生。
ミルカさん:数学が好きな高校生。のクラスメート。長い黒髪の《饒舌才媛》。
リサ:自在にプログラミングを行う無口な女子。赤い髪の《コンピュータ少女》。

双倉図書館

ここは双倉図書館。

今日、はミルカさんに呼び出されてここにやってきた。 《変幻ピクセル》のイベントはもうとっくに終わったから、 何もないはずなんだけどな。

広いイベントホールに入ると、 大きなスクリーンにオセロを切り取ったような映像が映っていた。 白と黒の石がたくさん並び、くるくると白黒反転を繰り返している。



そして、スクリーンの前にはコントローラを操作しているミルカさんが立っていた。 傍らにはリサもいる。

「何やってるの? ゲーム?」

ミルカ「おっと」

エラー音と共に ERROR! の文字が大きくスクリーンに表示された。

リサ「注意力不足」

ミルカ「ちょうどいい。彼も来たし、休憩にしよう」

「二人でゲームしていたの?」

ミルカ「いや、これは一人ゲーム。フリップ・トリップだよ。 単純といえば単純なゲームだけど、おもしろい」

「フリップ・トリップ?」

ミルカ「私は《変幻ピクセル》に来れなかったからな(第103回第104回「変幻ピクセル」参照)。 君も参加できなかっただろう? リサに機材の一部をもう一度出してもらった。いっしょに遊ぼう」

リサ「迷惑」

「《変幻ピクセル》の話はユーリから聞いたよ。(第107回第108回「コンプリメント・コンプレックス」参照) リサちゃんからコンピュータのことたくさん教えてもらったって喜んでたよ。 ありがとう」

リサ「《ちゃん》は不要……大したこと、話してない(咳)」

フリップ・トリップ

「でも、フリップ・トリップとかいうゲームについては聞かなかったなあ。これはどういうゲームなの?」

ミルカ「さっき私がやっていた《フリップ・トリップ $8$ 》は難しすぎるから、《フリップ・トリップ $4$ 》にしよう」

リサ「説明パネル」

フリップ・トリップ(基本操作)


  • 盤面には $4$ 個の石がある。表が黒、裏が白である。
  • スタートボタンを押すと、 $4$ 個の石はすべて白になる。
  • 反転ボタンが $4$ 個あり、押した反転ボタンに対応した石は白黒反転する。

「ええと? まず、スタートボタンを押すと全部白になる、と」

スタートボタンを押した直後

「そして、反転ボタンを押したら、それに対応した石は白から黒になるんだね。たとえば、反転ボタン $1$ を押すと、白白黒白ということかな」

スタートボタンを押して反転ボタン $1$ を押した

「そして反転ボタン $0$ を押すと、白白黒黒」

スタートボタン→反転ボタン $1$ →反転ボタン $0$

ミルカ「白なら黒になるが、黒なら白になる」

「ということは、もう一度ボタン $0$ を押すと、白白黒白に戻るんだね」

スタートボタン→反転ボタン $1$ →反転ボタン $0$ →反転ボタン $0$

が反転ボタン $0$ を押すと、 エラー音が響いてスクリーンにERROR!の文字が表示された。

ミルカ同じパターンを出してしまったらエラーになる。スタートしてから、白白黒白は出た。もう一度それを出したからエラーになった。 それがフリップ・トリップ」

リサ「説明パネル」

フリップ・トリップ(エラーとフルトリップ)


  • スタートボタンを押してから現れた石のパターンは、すべて記録されている。
  • 反転ボタンの操作で石のパターンを作ったとき、過去に登場したパターンを作ってしまったら、エラーでゲーム終了となる。この場合、プレイヤーの負けである。
  • ただし、すべてのパターンを尽くして白白白白に戻れたなら、フルトリップでゲーム終了となる。この場合、プレイヤーの勝ちである。

「過去に登場したパターンを作ってしまったらエラー……ということは、同じパターンを作らないように反転ボタンを操作して、 全部のパターンを作るってこと?」

ミルカ「端的に言えば、そうなるな」

リサ「重複パターン禁止」

「うーん……そうか、さっきは「白白白白→白白黒白→白白黒黒→白白黒白」と操作してしまったからエラーになったんだ。 白白黒白が二回出たから。 待てよ、 $4$ 個の石があって、それぞれ白黒二通りあるんだから、 全部で $16$ 個のパターンがある。 ということは、これまで出たパターンを最大 $16$ 個記憶しなくちゃいけないってことか」

ミルカ「まあ、記憶したければ」

「いやいや、簡単か。だって、 $2$ 進法を使って数えるのと同じことをすればいいからね」

ミルカ「というと?」

「白を $0$ として、黒を $1$ として考えると、 $0000,0001,0010,0011,0100,0101,\ldots$ のように、 $2$ 進法で数を数えていくようにビットパターンを作っていけばいい。 そうすれば、 $4$ ビットのビットパターンすべてを尽くせるから……おっと! それじゃだめか」

ミルカ「だめだね」

$4$ ビットのビットパターン( $2$ 進法で数えていく)
$$ \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$ とは限らない。ちょっとやってみせよう」

ミルカさんはそういうと、フリップ・トリップのスタートボタンを押し、 すごいスピードでボタンを押した。 $16$ 回の後、 $4$ 個の石はすべて白に戻り、 スクリーンにはFULL TRIP!と表示された。

「ううん……速すぎてわからなかったけど、確かに《フルトリップ》を達成できそうなことはわかったよ」

問題
フリップ・トリップで、スタートボタンを押してから、 $3,2,1,0$ の四つの反転ボタンをどの順番で押せば、 フルトリップできるだろうか。

(読者のあなたも、考えてみませんか?)

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

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

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

人気の連載

おすすめ記事

ケイクス

この連載について

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

結城浩

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

この連載の人気記事

関連記事

関連キーワード

コメント

aramisakihime 自分の解答とは違いましたが納得。むしろ、そっちの回と繋がるのか、と驚きました。> 約2年前 replyretweetfavorite

tkab1100 ハッセ図にしたらハミルトン閉路問題と同値になるなって思った 約2年前 replyretweetfavorite

ysdkz グレイコード? 約2年前 replyretweetfavorite

Shift255 「ああ、宇宙人のやつね。知ってる知ってる。」と思っただけで、定規に至れない辺り、私も訓練が足りないな。 約2年前 replyretweetfavorite