パズルの国のアリス

トランプ兵士たちの相愛図(問題)

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

 不思議の国のトランプ王国で晩餐会がまた開かれる。今や三月ウサギの家の前で行うのが当たり前になったが,たまのことなのでお茶会3人組もあきらめて会場を提供している。ハートの女王は親睦という口実でいつも席順にこだわるのだが,今回は席決めに口を出さず,はやりのアウトソーシング(外部委託)ということだろうか,芋虫探偵局に依頼した。外部委託は初めてということもあり,条件は細かくない。仲の良い兵士どうしが近くにかたまらないようにというものだ。兵士たちの関係はおおむね良好で仲が良いが,王侯たちはその条件の対象にならないので,ところどころに王侯を配置すれば,適当に並べてもさほど問題のない席順が作れそうだ。

 ところが,必要なさそうなときに限って妙に張り切ってしまうのが局長の芋虫だ。さっそく40人の兵士全員に意識調査を実施することにした。調査目的を伏せて(かつ回答内容は第三者に提供しないとの約束のもとに),各兵士に自分が友達と思っている兵士全員をリストアップしてもらった。兵士たちはみな正直に回答してきたが,リストを集めてみると,結果には意外な面もあった。ある兵士が別の兵士を友達と思っていても,逆は必ずしもそうでなかったのだ。兵士のペアは40C2=780組あるが,相思相愛ペアは401組しかいなかったのだ。

 結局,王侯を間に挟まなくても相愛ペアが隣り合わないようにすることができ,依頼自体は簡単に達成できたのだが,その話を聞いた助手のグリフォンが,リストから作った相愛図を見たわけでもないのに,妙な独り言をつぶやいた。「ふむ。相愛ペアが意外に少ないということは,仲良し3人組は存在しないということかな? いや,そんなことはないな。……うむ,仲良しペアが401組もあれば,確かにその中に仲良し3人組が存在するぞ」。

 読者の皆さんには,このグリフォンの独り言の根拠を考えていただきたい。なお,仲良しn人組とは,n人のグループで,その中のどの1人をとっても,他のnー1人全員を友達と思っている場合をいう。余力のある読者はさらに,仲良しペアが401組存在する場合に仲良し3人組が少なくとも20組存在することを証明していただきたい。

解答はこちらです