パズルの国のアリス

続・カードを順に積み上げろ! 飛び飛びでも同じでも(解答)

坂井 公(筑波大学)題字・イラスト:斉藤重之

 

解答例この解の基になるアイデアは,秋田県の千葉隆さんからいただいた。多少,表現を変えたところはあるが,千葉さんが連絡してくれた指示書をまず紹介しよう。なお,カードの山は左右で輪のようにつながっていると考える。つまり,右端の山の右側には左端の山があるとする。

(1)山が1つだけなら,トップカードを右へ
(2)左端だけが空いているなら,中央のトップカードを右端へ
(3)中央だけが空いているなら,右端のトップカードを左端へ
(4)右端だけが空いているなら,左端のトップカードで右端を埋める
(5)空きがないなら,トップの3枚を比べる。右端が最小か最大なら,残り2枚の小さいほうを右端へ。右端が中間のカードなら,残り2枚の大きいほうを右端へ

このパズルの考案者とされるコンウェイ(J. H. Conway)の解や,同じく4月号で紹介した富士通研究所の屋並仁史さんの解には,数値が1違いであることに着目する操作があるが,上の指示書には,大小の比較はあっても数値の差を利用する部分はない。したがって,カードに書いてある数値が飛び飛びであっても,なんら支障がないことに注目されたい。一列に並べるための基準があるものならば何でも(数学用語を使えば全順序集合の任意の要素を),各カードに書いておきさえすれば,それに従って揃えることができるということだ。

同じカードが交じっていてもうまくいくようにしたのは筆者の工夫だが,これは千葉解を知ったあとならすぐに思いつく。同じカードが出てきたときに備えて,(4)と(5)の例外として,(4’)右端だけが空きで,左端と中央のトップカードが同じなら左から中央へ(5’)空きがなく右端と同じカードが見えていれば,そのカードを右端へ。左端と中央が同じなら中央を右端へという操作を加えればよい。

上の指示書でうまくいく理由を概説しよう。まず,どんな状態から始めようと,中央が空いてなければどのカードも左から右の方向に動くだけだから,やがて 中央が空き,次に(3)によりすべてのカードが左端に集まることに注意しよう。さて,この状態のとき,左端の山のカードをトップから順に取ったa1,a2,…,am,b1,b2,…,bnで,

b1≦b2 ≦…≦bn<a1≦a2 ≦…≦am

が成り立つ最長のものをトップサイクルと呼ぶことにする。このとき目標に達していなければ,(1)で左端のトップカードが中央に移った後,再び右方向への 動きが始まるが,やがて全カードがまた左端に集まる。実際にカードを動かしてみればわかるので,厳密な議論は省略するが,このとき山の上の方だけが,

a2,…,am,b1,b2,…,bn,a1

に変化している。ただし,これはa1<a2の場合で,a1=a2 ならa2も後ろに回る。つまり,a1と同じカードがすべてトップサイクルの後ろに回るのだ。

もし,トップサイクルが左端の山全体であれば,これを繰り返すうちに,b1が先頭に出てきて目標に達する。トップサイクルが左端の山全体でなくても,その下にあるカードがやがて組み込まれて,トップサイクルが長くなるから,結局,いつかはトップサイクルが山全体になる。

 

中央の山はいったん空くと空きスペースに

元の千葉解をよく調べてみると,さらに面白いことに気がつく。つまり,中央の山は,いったん空いたあとは,カードが複数枚積まれることがない。ということ は,最初に2つの山にカードをデタラメに分けておいても,カード1枚分の空きスペースがあれば,カードを順に揃えて左の山に積むことができることを意味する。それも2つの山のトップカードと空きスペースのカード以外の情報を一切使わずに……!

筆者による修正(4’)を加えたあとでは,中央に同じカードが2枚以上積まれることがあるので,同じカードが複数枚ある場合には,そうはいかないように 見える。しかし,実は(4’)の修正はスピードアップのためにしたことで,同じカードが見えたときの操作を慎重に設計すれば,同じカードが複数枚ある場合 にも1枚分の空きスペースでうまく処理する方法がある。考えてみていただきたい。

この処理方法は情報処理の用語を使って言うなら,「2本のスタックと1つのワーキングスペースがあれば,ソートができる」ということだが,それだけでも難しいのに,それを一切記憶なしにできるというのは筆者には驚異的なことに思える。このあたり,どういうことがわかっているのか,ソートについて詳しい人 がいれば,ぜひご教授願いたい。連絡は下記のリンクからフォームを使って編集部まで。

フォームはこちらから

 

参考にした本:Peter Winklerによる次の2冊(ともに出版元はA K Peters, Ltd.)Mathematical Puzzles: A Connoisseur’s Collection(2004)Mathematical Mind-Benders(2007)ルイス・キャロルによる『不思議の国のアリス』『鏡の国のアリス』(さまざまな出版社から,さまざまな訳者による翻訳本や注釈本が出ている)

 

 

問題に戻る

 

 

 

問題はこちらです