パズルの国のアリス

チェス王室の払い下げ品(解答)

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

 答えは,赤の女王からの提案だということからだけでも容易に推測できるように,「赤に有利」というものだ。実際,名前のリストを作るのは赤の女王なのだから。問題は,白の女王が最初に白ラベルをどういうふうに貼ろうと,名前のリストをうまく調整すれば赤の王室が売り上げの半分以上を得られるということの証明だ。

 入札者の全体をUとする。今,リストを1つ決めたとき,その中に出てくる入札者の集合をXとしよう。XUの部分集合だ。Xの中で物品aに対して入札した人の集合をXaとすると,容易にわかるように,Xaの要素数が奇数であれば,最終的にaのラベルの色は最初とは反対になり,偶数であればラベルの色は変化しない。

 誰も入札しなかった品bについては,名前のリストをどう調整してもXbは空集合だからラベルの色を変えることはできないが,これらの品は売り上げに貢献しないので無視してよい。残りの品は,入札者が少なくとも1人いるので,名前のリストによりラベルの色が変わり得ることに注意したい。

 さて,赤の女王は名前のリスト,すなわち集合Xを自由にできるので,このXをさまざまに変えた場合を考えてみよう。入札者がいる品aを固定して考えてみると,Xaの要素数はXによって奇数になったり偶数になったりするが,Uの部分集合全体の中では,Xaの要素数が奇数になるものと偶数になるものとが,半々になることに気がつくのがポイントだ。そのことは直感的にもわかると思うが,もし厳密な証明がほしいというのであれば,次のように考えるといい。aには入札者がいるということが前提なので,その1人xUを任意に固定し,Uの部分集合全体を,xを含むものとxを含まないものに分けてみると,それらは半々になる。特に集合Yxを含まないとき,Yと集合ZY∪{x}を対にして考えると,xaへの入札者だったから,YaZaの要素数は,一方が奇数なら他方は偶数である。

 つまり,XUの部分集合全体にわたって動かしてみると,aの価格が白の収益になる場合と,赤の収益になる場合とはちょうど半々であることがわかる。他の物品についても,入札者がいれば事情は同じだから,売上総額についても同じことがいえる。

 もし,Uのどんな部分集合Xをとっても,白の収益のほうが赤の収益より多いとしたら,それは上の事実に明らかに矛盾する。ということは,名前のリストをうまく作れば,必ず赤の収益を半分以上にできるということだ。むしろ,よほど特殊な状況になっていない限り,白の王室は確実に損をしてしまうといえる。最初のラベルを自由に貼れてさえそうなのだから,白ラベルが最初半分以下という制限がついた赤の女王の提案は,白にとってなおさら不利であり,まったく問題にならない。

参考にした本
Mathematical Puzzles:A Connoisseur's Collection(2004)
Mathematical Mind-Benders(2007) P. Winkler著

問題はこちらです