コラッツの洞窟
コラッツ予想についての妄想。2進数で問題を表してみると面白い感じがするというネタ。
ある洞窟
このコラッツ洞窟という洞窟は一本道で、どこまでも続いている。この洞窟には頻繁にいつの間にかスライム軍団(親玉と雑魚たち)が侵入していることがあり、そのたびにハンターがスライムを退治してきた。
このスライムとハンターは以下のルールに従って動いている。
全スライムは毎ターン1マス進む。進むのと同時に、元の座標に分身を残す。分身しても親玉は先頭一人だけ。
2.進んだ先にもスライムがいたら、合体してもう1マス進める。この時は分身は残せない。進んだ先にもスライムがいたら繰り返す。
3.スライムが進んだらハンターは必ず1度銃を打つ。この銃は親玉を殺す力があるが、手下に当たると手下を一マス先に進めるだけである。この効果で進んだスライムも、2.と同様に前のマスのスライム合体して進行できる。ハンターが銃を1度打った結果、親玉だけになった場合、もう一度銃を撃って親玉を倒せる。
これを1ターンとしてひたすら繰り返す。これまでハンターは常にスライムの手下を全滅させ、親玉を倒してきた。
ではハンターがスライムを倒す様をお見せしよう。絵を描くのが面倒なのでスライムがいるマスを1、いないマスを0として数値列で表現する。先頭(左端)の1が親玉である。以下の並びは、数値列(101)に対応する。
まずルール1.に従ってスライムが進む。スライムは分身するので数値列は(1111)になる。
$$
101 \rightarrow 1111
$$
ルール3.に従ってハンターが銃を撃ち、銃弾が右端のスライム(1)にあたる。当たったらスライムは左に移動するが、そこもスライムがいるので、ルール2.に従って合体し、さらに進む。これを繰り返すと、最後に親玉と合体して、親玉が1マス進むことになる。
$$
101 \rightarrow 1111 \rightarrow(ハンター射撃) \rightarrow 10000
$$
親玉一人になったので、ハンターは銃を打ち込んで親玉を撃破した。
もう1例やってみよう。今度はスライム位置は(111)とする。(101)に対して、手下スライムがもう一匹間に入っただけである。
ターン1。スライム進行。複雑だが結果以下になる。
$$
111 \rightarrow 10101
$$
ハンターが打つ。右端の手下が進むだけとなった。親玉が見えないのでハンターは今回銃は打たない。
$$
10101 \rightarrow 10110
$$
ターン2。ハンターが打つところまで書くと
$$
10110 \rightarrow 1000010 \rightarrow 1000100
$$
ターン3。
$$
1000100 \rightarrow 11001100 \rightarrow 11010000
$$
ターン4。この辺りでハンターは経験上これは勝ちは近いと思っている。
$$
11010000 \rightarrow 1001110000 \rightarrow 1010000000
$$
ターン5。親玉1人になり、今日もハンターは勝利の引き金を引いたのだった。
$$
1010000000 \rightarrow 11110000000 \rightarrow 100000000000
$$
ハンターは経験的にこのスライムを必ず駆除できると思っている。しかし、最近スライムの配置によっては駆除できないこともあるかもしれないのではという懸念が生まれてきた。何せスライムの動きは複雑で分裂までするので、もしかしたら手下が永遠に残って消せないこともあるかもしれない。ハンターはそういうパターンがあるのか寝る前にいつも考えているが、見つけられたことはない。
コラッツ問題との対応
解説。数学の未解決問題にはコラッツの問題というものがある。
任意の正の整数 n に対して、以下で定められる操作を行う：
これを繰り返すとどんな整数から出発しても1になる、という予想がコラッツ予想と呼ばれている。
上で書いた洞窟のハンターのスライム狩りは、このコラッツ問題そのものである。
まず、スライムの配置は数値の2進数表現に対応している。スライムのいるところが1で、ほかが0である。例で出した数値列は、(101)=5, (111)=7に相当している。
ルールにおけるスライムの移動と合体のルールは、2進数上の3をかける操作に対応している。2進数では0と1しかないので、1と1が出会うと桁上げが発生して、上位側の桁に1が移動する。3をかけることは1をかけることと2をかけることを足し合わせることに対応する。1をかけるのは何もしないのに等しいので、つまり2をかけたものと、元の数を足し合わせればよい。2進数表現で2をかけることは、10進数表現の数に10をかけるのと同じく桁を左に移動すればいいだけである。つまり、スライムが1マス進んでいるのは、2をかける操作に相当する。残った分身と合体して、桁上げで1マス進んだりさせることが結局3をかけることに対応しているわけである。
ルール3.でハンターが銃を撃つことが、3かけた後1を足す操作に相当する。「コラッツ問題では奇数にしかこの操作はしない、2で割ってないではないか」と思うかもしれないが、2進数において2で割ることは、10進数で10を割るのと同じく、桁をシフトすることに過ぎない。つまり今回洞窟の例ではスライム同士の相対的な位置は何も変える必要はない。スライムがいちいち戻ってくる例としても良かったがなんとなく不自然だったのでそれはしなかった。結局スライムを戻さなくても、足す操作が再右端のスライムに対して行われれば同じ意味になるわけである。それを銃弾で表現している。終了条件も同じで、親玉だけになることが結局2のべきの数になっていることと等しく、そうなったらひたすら2で割っていくだけだから1になるのは自明である。
このように問題を見てみると、ハンターがひたすら銃を1発ずつ打ち込むと、スライムは勝手に一人になって滅びていくわけで、なんともお手軽なスライムだなと思う。ライフゲームのようにも見えてくる。一番洞窟の入り口側にいるスライムはそれ以上右側に戻ることはないから、再右端のスライムの位置と、親玉の位置は単純増加関数であり、最終的にはそれらが一致したときに手続きは終わる。この親玉の進行速度と、再右端のスライムの進行速度で、後者の方が平均的に速いから必ず終わると言えるんじゃないかと思ったが、どうもそれは導けなかった。手軽なパターンを拾ってくだけだと、基本的に親玉が逃げてく方が速いように思える。いつも親玉に追いつく時というのは、以下の並びが表れて一気に玉突きが発生するのだ。
$$
\cdots 1010101010101010101
$$
さっきの例でも、数値列101(10進数で5)の時がこのパターンで、これが出た後は1111というパターンになってハンターの銃弾で親玉以外消えていく。
だから、こうしたパターンがどういうときに出てくるのかとか、その頻度が問題に関係してそうに思えたが、結局私は数学者でないので全くこれ以上進まない。生きているうちに誰か解いてくれたらうれしい。
この記事が気に入ったらサポートをしてみませんか？