兵士たちの大喧嘩（問題）

　3人組からお茶会の会場を奪って催されるトランプ王国の晩餐会の様子はこれまでにも何度か紹介してきたが，あるとき，無礼講だとしても話しにくいこともあるだろうからと，王侯たちが全員席をはずし，兵士40人だけにしたことがあった。ところがこれがとんでもないことになった。当然だが，兵士どうしといってもとても仲良しの場合もあれば犬猿の仲という場合もある。そのときはとても仲の悪い2人がたまたま隣り合っていて，会がさほど進まないうちに大喧嘩になってしまった。王侯がいれば多少の遠慮もあるだろうが，そういう抑止力もないせいで，喧嘩の挙げ句の果てには皿が飛び交い料理や飲み物が宙を舞うという大惨事になってしまったのだ。

　これに懲りたハートの女王は，今後二度とそういうことがないようにと，兵士たち全員に，仲が悪いので隣には座りたくない相手のリストを前もって提出させることにした。そして，その結果をアリスとグリフォンに渡し，少なくとも一方が他方を嫌っている2人が隣り合わないように40人の兵士をぐるりと並べる座席表を作れないかと依頼した。

　「ええー，そんな都合のいい座席表ができるかしら？」とアリス。

　不仲リストをじっと見ていたグリフォンがしばらくして口を開いた。「うーむ。幸い，どの兵士も仲が悪い兵士の数は19人以下だよ。『仲が悪い』とは，少なくとも一方が他方を嫌っているっていう意味だ。こういう状況の場合には，ハートの女王の希望通りに座席表が作れることは確実だから，さっそく作成に着手しようじゃないか」。

　読者への問題は，このグリフォンの言葉の正しさを証明することだ。それにはいろいろな方法がありうるが，座席表を作成するためのシステマティックな手順を考えていただくのが一番よいかもしれない。

　さらに，これだけでは物足りないという読者のためにもう1問。ハートの女王は，大勢が集まるパーティーのホステスを務めることになった。女王はパーティーの記念としてn種類の贈り物を用意していて，各客に1つずつ配ろうと考えているが，どの客Pを取っても，Pの知り合いのたかだか1/nにしかPと同じ種類の贈り物がいかないようにしたい。それは可能だろうか？

　可能ならそれを証明し，不可能なら反例を示していただきたい。なお，客どうしは互いに知り合いか知り合いではないかのどちらかで，一方だけが知っているという関係はないこととする。

答えは，2020年7月号に掲載