続・カードを順に積み上げろ！ 飛び飛びでも同じでも（問題）

お茶会のテーブルは賑わっていた。いつもの3人に加え，アリス，グリフォン，ドードー鳥，芋虫も加わり，4月号でグリフォンが発見したカード積みに関するヤマネの指示書のことで，話に花が咲いている。グリフォンがさらにカードの枚数を任意に増やしてもうまくいく指示書を設計したというのだ。「カードを順に積み上げろ」の答えの欄でコンウェイ（J.H.Conway）による一般解として紹介したものだ。

問題と解を簡単に復習しよう。それぞれ1からnまでの数値が書かれたn枚のカードがある。最初は適当に3つの山に分けておくが，それを左端に上から1， 2，…，nとなるように積み直したい。ただし，やってよいのは，ある山のトップカードを別の山のトップに移動させることだけ。普通の記憶力があれば簡単だ が，今自分がしたことやトップカードの下に何があったかをすべて忘れてしまうヤマネにこれをさせたい。つまり，指示は，トップカードだけを頼りにし，それが同じなら下がどうなっているかにかかわらず，同じ操作をするようなものでなければならない。

この問題に対して，グリフォンは次のような解（Conway解）を発見した。以下，カードの山は循環していて右端の山のさらに右に左端の山があると考える。また，最大のカードというのは，トップカードの中で最大という意味だ。

不思議の国の住民たちは，おのおの適当にカードを3つの山に分けて，指示書どおりに動かして確かめている。お茶会3人組は，ヤマネだけにやらせて，本当に揃うかどうかを2人が半信半疑で観察している。

「結局，一番大きいカードは，左の山の一番下に行かなければダメなのよね」とドードー。「あら，そう言ってたら一番大きいカードが出てきたわ。なるほ ど，このカードの上には，他のカードが簡単には載らないようになっているのね。なかなかうまいわね。おや，左端が空いて，そこに移動したわ。だけど，その上に他のカードがうまく積み上がるのかしら。」

「そう簡単じゃないさ。ほらせっかく左の底に納めたカードが，真ん中の山に行っちまった」と水ぎせるの煙とともに芋虫の声があがった。

「いいからどんどん続けたらどうだい。ほら，腕組んで煙なんか吐いてないで」とグリフォンが促す。

「そうかな。こんなことでうまくいくとは……あれれ，また揃ってきおった」

やがて，お茶会3人組，すなわち無言でもくもくと作業を進めているヤマネとそれを疑わしげに見守っていた三月ウサギと帽子屋のサイドから驚きの声があがった。「おい，本当だ。揃っちまったよ」。

その後も続々と成功の報告があったが，アリスだけが，「変ね。どうしても揃わない。それに，なんだか同じことを繰り返してるような気がする」。

「そんなはずはないと思うけどね」とグリフォン。「いったい，何枚でやってるんだい？　動かし方，間違えてない？」

「6枚よ。この通り」

ドードーが「私なんか8枚でももう揃ったのに」と言いながら，のぞき込んで調べ始めた。とたんに「あんた，ほんとに間抜けね。5が抜けていて3が2枚あるじゃないの」

「えっ」とアリスが見直してみると，確かにその通りだ。ヤマネだけは気の毒そうに見ているが，「やはり，この子はオッチョコチョイね」と言わんばかりの視線を周囲からいっせいに浴びて真っ赤になり，負けず嫌いのアリスは，思わず口走っていた。

「そ，そ，そうなのよ。グリフォンさんの指示書はとても良くできてるけど，こういう場合にはうまくいかないわ。でも，もっと巧妙な指示書を作れば，数値が飛び飛びでも同じカードが何枚かあってもうまくいくと思うの」

苦労して解を見出したグリフォンがまっさきに不信を表明した。「そんな方法があるとは思えないけどね。まあ，考えてみるといいさ」。さて，アリスが汚名を返上するために，書いてある数値に抜けや重複があるような場合にも通用する指示書を考えて頂きたい。指示のさい頼りにできるのは トップカードだけだという条件は同じだ。目標はもちろん，トップから順に大きくなるように左端に全部のカードを積み上げることだ。

編集部注：今回の問題は秋田県の千葉隆さんからいただいた答えをもとに作成しました。