パズルの国のアリス

大部屋と1人部屋どっちが好き?(解答)

ウォーミングアップの問題は,当たり前すぎてどう手をつければよいかかえってわかりにくいかもしれない。しかし,「あるプロセスの繰り返しが永遠には続かない」というこの手の停止性問題の証明には,状況に付随して単調に変化していく量をうまく取り出し,その量がある限界を超えて減ったり増えたりしないことを示すのが有効だ。この問題に使える量としてはいろいろなものが考えられるが,まずは各部屋の住人数の平方和がわかりやすそうだ。蟻の巣に部屋がk個あるとして,各部屋の住人数をn1n2,…,nkとするとき

Sn12n22+…+nk2

という量である。i番目の部屋からj番目の部屋に蟻が引っ越すための条件はnjniであり,引っ越し後のi番目とj番目の部屋の住人数はそれぞれni−1とnj+1になる。従って,上のSの値は,この2つの部屋に関してはni2nj2

ni−1)2+(nj+1)2ni2nj2+2(njni)+2

に変わる。njniだから,引っ越し後のSの値は必ず大きくなるのがポイントだ。全員が同じ部屋に入ったときにSの値は最大になり,それ以上は大きくなれないから,この時点でプロセスは終了する。

 しかし,次の問題を解くために使うにはSは大雑把すぎるようだ。それでもまったく役に立たないわけではなく,問題の21匹の蟻の場合に適用すると,Sは最初の状況では12+22+32+42+52+62=91だったのが,全部の蟻が1つの部屋に集まることで212=441に変わることがわかる。先に見たように,Sは1回の引っ越しで最低でも2増えるから,せいぜい(441−91)/2=175回の引っ越しで全員が1つの部屋に集まることくらいはわかる。

 ところが,問題文の35回というのはそのわずか1/5であり,これを証明するにはもっと繊細な量が必要だ。その量を作るために,部屋の番号を住人の多い順に付け替えてしまおう。つまり,n1n2≧…≧nkとするのだ。そして,各蟻に自分がいる部屋の番号よりも1だけ小さい重みを持たせ,その重みの合計をTとする。つまり

 T=0・n1+1・n2+2・n3+…+(k−1)・nk

である。もし全部の蟻が1番の部屋にいるならT=0だ。

 この量Tの特徴は,住人数の同じ部屋がいくつかあるとき,それらの間で番号を付け替えてもTの値は変化を受けないことだ。引っ越しによって住人が減る部屋と増える部屋が生じるが,引っ越し前のそれらの部屋と同じ住人数の部屋がほかにある場合,引っ越し前に番号を付け替え,住人が減る部屋については同じ住人数の中で最大の番号を持つように,住人が増える部屋については最小の番号を持つようにしておく。このように付け替えても引っ越し前のTの値は変化しない。また,この付け替えによって,引っ越し後も各部屋の住人数は番号順に広義減少するようになり,かつ,引っ越しによって必ずTの値が減少するようになる。なぜなら,こうすると引っ越しは必ず大きな番号の部屋から小さな番号の部屋への移動になるので,引っ越しした蟻の重みは必ず減るからである。すると,重み合計Tは最初0・n1+1・n2+2・n3+…+(k−1)・nkの状態から始まり,1回の引っ越しごとに最低でも1減るのだから,せいぜい0・n1+1・n2+2・n3+…+(k−1)・nk回の引っ越し後には0になる。元の問題ではTは最初0・6+1・5+2・4+3・3+4・2+5・1=35だから,どのような手順でもせいぜい35回の引っ越しで全員が1つの部屋に集まるといえる。

 もちろん,35回よりも少ない引っ越し回数で全員が1つの部屋に集まることもあるが,住人数の同じ部屋がたくさんある例外的な場合を除き,1回の引っ越しではTが1しか減らないような手順が存在するから,引っ越し回数の上界はこれ以上には大きく下がらない。特に各部屋の住人数が異なりn1n2>…>nkとなっている場合,全員が1つの部屋に集まるまでにちょうど0・n1+1・n2+2・n3+…+(k−1)・nk回の引っ越しを行うような手順が存在する。各自考えてほしい。

 孤独好きの蟻の問題をいきなり証明するのは,少なくとも筆者には難しく思われるので,段階を踏んで進めよう。

 まず,どの部屋にもいつかは住人が生じることを証明しよう。もしいつまでも蟻が住み着かない部屋があったとして,それをRとしよう。Rの右隣の部屋に−9という番号を振り,以下右回りに−8,−7,…という番号を振っていくと部屋は円形につながっているのだから,9番が最後になって,またRに戻る。そこで各蟻に自分がいる部屋番号の2乗という重みを持たせ,全蟻の重みの合計をSとする。部屋Rには決して蟻が住み着かないという仮定だったので,9番あるいは−9番に蟻が2匹以上いて,そこから両隣に引っ越すということはない。つまり,引っ越しはいつも−8番から8番の部屋で起こる。n番の部屋の2匹がn−1番とn+1番の部屋に引っ越すとき,Sの値は,引っ越しをした2匹の蟻に関しては2n2から(n−1)2+(n+1)2=2n2+2に変わるから,必ずちょうど2だけ増加する。つまり,引っ越しが9番か−9番の部屋で起こらない限りSは2ずつ増加し続けることになるが,蟻は21匹で,部屋番号は−9から9までしかないのだから矛盾する。

 これでどの部屋にもやがては蟻がやって来ることが示された。次に隣り合う2部屋(仮にR1とR2と呼ぶ)について考えよう。先に見たようにR1にも必ず蟻はやって来る。次に気がつくべきは,それ以後,R1とR2のどちらにも蟻がいないということは決して起こらないということだ。なぜなら,R1から蟻がいなくなるということは,R1の蟻が2匹になり,それが両隣に引っ越した場合だけだから,必ずR2に蟻がいる。R2から蟻がいなくなる場合も同様だ。

 こうして,しばらく時間がたった後は,隣り合う2つの部屋のどちらかには必ず蟻がいることになる。そうなっても,空き部屋が10室以上あったとしたら,部屋数は全部で20なのだから,空き部屋とそうでない部屋が10室ずつ交互に並んでいるしかない。次の引っ越しは,空き部屋でないどこかで起こる。その部屋自身は空き部屋になる可能性があるが,両隣の空き部屋が消えるので,空き部屋数は必ず9以下になる。

問題はこちらです