パズルの国のアリス

いつまで続く?変身ショー(解答)

 初の問題は,赤,青,緑の3色に黄色が加わって4色になったこと以外に2009年11月号と大きな差はないので,同号の解答と類似のアイデアが適用できる。

 赤,青,緑,黄のカメレオンの匹数をそれぞれrbgyとし,その状態を(rbgy)と表記する。この状態から赤,青,緑の1匹ずつが一斉に黄色に変身したとすれば,新しい状態は(r−1,b−1,g−1, y+3)になる。注目すべきは,各色のカメレオン数の差の変化だ。青と赤の差は変身後もbrと変わらない。黄と赤の差はyrからyr+4と4だけ増えている。差が変わらないか4だけ変化することは,どの2色であっても,また変身が赤,緑,黄から青へであってもいえる。従って,変身がどのように進もうと,どの2色をとってもカメレオン数の差はいつでも4の倍数しか変化しない。例えば,ある手順で全員が黄色になることができたとしよう。その結果は(0,0,0,y’)と表記できるが,この状態が(rbgy)から作られたとすればbrgr≡0−0=0(mod 4),つまりbgr(mod 4)が成り立っていなければならない。どの色でも全員が同じ色になる場合は,同様に他の色の匹数を4で割った余りがどれも等しくなることが必要である。

 この条件は完全な十分条件ではないが,最初にカメレオンが2色しかいないような特殊な場合を除いて,うまく手順を踏めば大概全員が同じ色になれるから,同色になるためのほとんど十分な条件といえる。詳細は読者自身で検討されたい。

 次の問題は16匹のカメレオンの配置と色変わりの手順を1つ構成するだけだから,試行錯誤で何とか解決できそうだが,ポイントがわかっていないと意外に面倒かもしれない。ここでは,いきなり配置を与えてしまおう。英語の頭文字をとって,R,B,G,Yがそれぞれ,赤,青,緑,黄を表すことにして,次のような色配置を考える。

RRYBBBRGGGBYYYGR

なお,左端と右端は輪になって隣り合っている。下線を引いてある部分が色違いの3色並びになっているが,これらの部分を一斉でも順次でもよいから,別の色に変化させると次のようになる。

RGGGBYYYGRRRYBBB

読者はこの新しい配置が最初の配置から6匹分左にずれたものでしかないことを確認されたい。従って,また同じように色変わりを行えば,さらに6匹分ずれた配置になり,この色変わりショーはいつまでも続けられることがわかる。

 この配置を得るうえでのポイントを説明するには,最後の問題と一緒に考えるほうが都合がよさそうだ。例によってこの種の問題は,不変量を考え出すことが課題になることが多い。同じ色の隣り合ったカメレオンの対を「同色ペア」と呼ぶことにする。n匹のカメレオンが一列に並んでいる場合はn−1対の, 輪になっている場合はn対の同色ペア候補がいるが,同色ペアの数をPとすると,まずPが色変わりに関して非減少であることに気づくことが重要だ。左からk番目のカメレオンの色をCkとし,Ck−2Ck−1CkCk+1Ck+2kを中心として,色変えを行ったとしよう。当然CkCk−1CkCk+1だから,新しい同色ペア(k−1,k)と(kk+1)が2つできる。一方Ck−2Ck−1あるいはCk+1Ck+2だった場合,同色ペアだった(k−2,k−1)と(k+1,k+2)が同色でなくなるから同色ペアは最大で2減り,他のペアは影響を受けない。従って,色変えによって同色ペアの数Pは非減少であるが,列の場合は最大でn−1個,輪の場合でも最大でn個しかペアは存在しないから,もしいつまでも色変えが可能だとしたら,どこかでペア数は最大値に達して,それ以上には増えなくなる。

 逆にいえば,色変わりをいつまでも続けるには,同色ペア数が最大値に達した後,ずっとその最大値をキープし続けることが必要だ。上でみたように3匹並びが色変わりを起こすと,そこに新しい同色ペアが2組生じる。だから,同色ペアが増えないためには,その3匹並びの両脇の同色ペアが色変わりによって同色でなくなる必要がある。どの色変わりも常にこの条件を満たすように慎重に各色のカメレオンを配置して得られたのが先に述べた16匹の輪である。4色を対称的に配置できるから,16匹での構成が一番簡単とは思うが,もっと短い輪ではわずか6匹の構成のRRRBBGというのもある。これは変身できる3匹並びがいつも1カ所しかないので,色変わり手順に迷うことはないが,輪の長さが短すぎるし同時に見える色は3色だけなので,ショーとしての華やかさに欠けるかもしれない。他にも様々な長さの輪で構成が可能と思うので,見栄えのする美しいショーの検討は読者にお任せしよう。

 ところで,輪でなくて列の場合に色変えをいつまでも続けられないのはどうしてだろうか。それは,もちろん左端と右端がつながっていないので,Cn−1CnC1CnC1C2などの色変えが不可能だからであるが,その事情を説明するには同色ペア番号の2乗和をもう1つの不変量として持ちだすのが簡単なようだ。ペアの数が最大に達してから後を考える。ペアの左のカメレオンの番号をペアの番号として,その2乗の総和をSとする。ペアの数はもう増えなくなっているから,ある色変えでk−1番とk番が同色ペアになったとしたら,k−2番とk+1番が同色ペアから外れているに違いない。

k−1)2k2 −(k−2)2−(k +1)2=−4

だから,Sは色変えのたびに4減少する。2乗の和だからS は正の値しかとれないが,いつまでも色変えが続くようなら,Sは負の値になってしまい矛盾する。

問題はこちらです