パズルの国のアリス

トランプ王室晩餐会の席順(解答)

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

 トランプ王国の晩餐会が数夜連続で開かれることになった。前回は帽子屋のたくらみでナプキンにあぶれる者が続出したが,今回は席順で頭を悩ませることになった。

 晩餐会の2晩目,ハートの女王が苦言が呈した。「昨晩は自分から7席右にダイヤの6が座っていたのだが,今晩もまたそうだ。せっかく懇親のために会を設けているのだから,それはけしからん。どの2人の位置関係も前の晩とは違っていなければならん」。
 早速,前の晩の席順を調べ,今晩はどういう順に座るのがよいかをアリスとスペードのエースが中心になって計画した。

 まず最初の問題は,アリスたちを助けて,2晩目の席次表を作っていただくことだ。考えやすいように,1晩目は,アリスから右にスペードのエース,2から10,ジャック,女王,王の順に,あとは同じ順にハート,ダイヤ,クラブと並んでアリスに戻ってくる席順だったとしよう。ハートの女王の考えによると,2人を隔てる席数が同じであっても左右が異なっていれば,位置関係は異なるということだ。

 2晩目に関する最初の問題は,気がつきさえすれば非常に簡単な解がある。客同士の位置関係は,隔たりが同じでも左右が異なれば違うと考えるのだから,2晩目は単に逆順に座ればよい。全人数が偶数の場合は,逆順に座っても対面同士は同じ位置関係になってしまうが,53人は奇数だから同じ位置関係の客2人が生じるおそれはない。

 しかし3晩目は,客が53人もいるので,やみくもにやろうとするとかなり面倒だろう。53人から2人を選び出す組み合わせの数は(53×52)/2=1378組もあるので,各ペアについて前2晩とは位置関係が異なっているということを確認するだけでも大仕事だ。

 この種のことは,当然だが,システマティックにやるのが一番だ。まず,考慮しなければならないのは各客の位置関係だけだから,全員を一律に左右にずらしても構わない。そこで,たとえばアリスはいつも同じ座席に着席すると考えることができる。その席を0番とし,それから右へ1番,2番と進めぐるりと52番まで数えて,アリスの席に戻ってくるとする。ここまでで,勘のよい読者はもう解の構成がおわかりであろう。各席は53で割ったときの余りの数値を考えればよい。座席の位置関係についてもそうである。

 ここからは,各客がk晩目に座る座席を一気に指定してしまうほうが簡単だろう。最初の晩にi番目の座席に座った客がk晩目に座る座席をikとする。ikは53を超えていることもあろうが,その場合はもちろんそれを53で割った余りの数値が指定する座席に座る。

 まず,k晩目の指定が正しく座席指定になっているかを考えよう。つまり,それによって2人が同じ座席に割り当てられることがないかだが,幸い53が素数なので,k=1,2,…,52についてはその心配はない。よく知られているように,もしikjk(mod 53)ならば,ij(mod 53)であることが示されるからだ〔ab(mod x)は,aおよびbxで割ったときの余りの数が等しいことを示す〕。

 次に,ある2晩kk′で2人の座席の位置関係が同じになることがあるかだが,そういうことがある場合,その2人の最初の晩の席をijとするなら,ik−jkik′−jk′(mod 53)が成り立ち,kk′(mod 53)が導かれる。だから,1晩目から52晩目までは,ハートの女王の要求を満たしたまま,晩餐会を続けられるということになる。実際,最初の解で示した逆順に並ぶというのは,上の解構成での52晩目の座席順に他ならない。

 最後に14人での晩餐会を考えよう。14は素数でないから,上のような解の構成はできない。実際,最初に座席iに座った人を翌日ikに座らせようとすると,i=7の場合にうまくいかない。kが偶数の場合,アリスと座席がぶつかってしまうし,kが奇数の場合でも,7k≡7(mod 14)だから,アリスとの位置関係は対面同士のまま変わっていないことになる。というわけで,他のやり方で客をうまく配置できるかいろいろと試してみると,どうしてもどれか1組くらいのペアは初日と同じ位置関係になってしまい,うまくいかない。どうしてだろうか?

 実は,これは14人に限ったことではなく,偶数人の場合には避けられないのだ。それを証明しよう。今,客数を2nとし,初日に座席iに座った人の翌日の座席番号をσ(i)としよう。もしどのペアも初日と2日目の位置関係が異なるとしたら,異なるijについてはij≡/σi)−σ(j)(mod 2n)だ。つまりiσi)≡/jσj)(mod 2n)だが,これは0−σ(0),1−σ(1),…,(2n−1)−σ(2n−1)を2nで割った結果の余りがすべて異なるということで,余りには0から2n−1が1回ずつ出てくるということに他ならない。そこでこれらの総和を考えると,

である。ところがσ(0),σ(1),…,σ(2n−1)にも0から2n−1が1回ずつ出てくるのだから,

となり,矛盾する。

こうして人数が偶数の場合は,ハートの女王の要求を満たすような晩餐会を連夜開催することは不可能だと示された。また,人数が奇素数pの場合,先と同様な議論によりp−1夜連続で開催することが可能だとわかる。人数が奇数の合成数の場合は,初日と逆順にすることで2晩目まではOKだが,連続で何夜まで開催可能だろうか? この問題の検討は読者におまかせしよう。

参考にした本
Mathematical Puzzles:A Connoisseur's Collection(2004),
Mathematical Mind-Benders(2007) P. Winkler。
邦訳は『とっておきの数学パズル』(2011年),『続・とっておきの数学パズル』(2012年),ピーター・ウィンクラー著,坂井公・ 岩沢宏和・小副川健訳,日本評論社。

問題はこちらです