パズルの国のアリス

チームで参加! 何でもオリンピック(解答)

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

 

解答例この問題は,パズル作家として著名で本なども出版されている稲葉直貴さんが発案して,パズル懇話会のメーリングリストに出題したものを下敷きにしているが,稲葉さん自身からの連絡によると,それより前に同じ原理の問題が某社の研修で出されたことがあるらしい。これと同様の問題を前にご覧になった方がおられればぜひ編集部にご連絡いただきたい。フォームはこちらから >>

さて,解答だが,ズルをして情報を得ない限り,個々人の当選確率は1/2を超えることはない。従ってn人チーム全員が勘だけに頼ると,全員が当たる確率は1/2nになってしまう。誰か一人でも間違えてしまうとチームで参加できなくなるのだから,間違えるならば「全員いっせいに間違える」ようにすることが戦略のポイントとなる。

このための戦略として置換の奇偶性を利用することができる。まず,簡単な2人の場合を考えてみよう。トウィードルダムとトウィードルディーの双子兄弟の 場合,ディーのゼッケンa,ダムのゼッケンb,誰のものでもないゼッケンx が問題になる。a,b,x を小さいほうから並べると次の6通りの可能性がある。

x<a<b b<x<a a<b<xx<b<a a<x<b b<a<x

ディーは自分のゼッケンがa,xのどちらかであることはわかっている。そこで,ダムのゼッケンbを見たとき,それがa,xのどちらよりも大きいかどちらよりも小さければ,自分のゼッケンはその大きいほうだと答える。bがa,xの間のゼッケンならば,小さいほうだと答える。一方,ダムにはaが見える ので,それがb,xのどちらよりも大きいかどちらよりも小さければ,自分のゼッケンはその小さいほうだと答え,b,xの間のゼッケンならば,大きいほうだと答える。

この答えと先の場合分けを照らして調べてみると,ディーは上の段の場合に正しくaと答え,下の段の場合に間違えることがわかる。また,ダムも同様に上の段の場合にのみbと正しく答える。よって,2人とも間違える確率が1/2,2人とも正しく答える確率が1/2で,これ以外の状況は生じない。

数学的にいうと,x<a<bという順に対して上の段の順が偶置換というもので,下の段の順が奇置換というものだ。どういうことかというと,上の段の順を 互換(2つの要素の入れ替え)によってx,a,bの順に並び替えようとすると,偶数回の互換が必要になるということだ。反対に下の段の順をx,a,bの順 に並び替えるには奇数回の互換が必要になる。必要な互換の回数は,入れ替えの手順によって変わりうるが,奇偶性は決して変化しないことが数学的に証明され ている。

チームの人数が大きくなってもこの奇偶性を利用することはできる。つまり,奇置換を選ぶか偶置換を選ぶかだけを最初にチーム内で相談しておき,各人がそれに矛盾のないようにゼッケンを推測すればよい。

ポーン8人のチームの場合の具体的な戦略例を述べよう。あらかじめ8人に適当に1番から番号を振る。i番のポーンのゼッケンを pi とし,誰にも割り当てられなかったゼッケンを p0 としよう。さて,1番のポーンには, p0 と p1 は見えていないので,このどちらかが自分のゼッケンであることまではわかるが,どちらかはわからない。そこで,一方を自分の番号 p1 ,他方を p0 と仮定し,それを p0 から順に並べてみる。例えば( p0 ,p1 ,…,p8 )=(63,18,5,44,82,11,37,56,90)だったとしよう。次に互換だけでこれを小さい順に並べ替えることを考えると,例えば

63 ←→5, 18 ←→11, 63 ←→18, 44 ←→37, 82 ←→44, 56 ←→63, 82 ←→63

の順で入れ替えれば5,11,18,37,44,56,63,82,90 と小さい順に並ぶ。これに要した互換の数は7回だから,最初に「偶置換を選ぶ」としてあったなら, p1 = 18 という仮定はこれに矛盾する。そこで p0 のほうに想定した63を答えとする。2番のポーンも,未知のどちらかを自分のゼッケン p2 に想定し,同じ手順で奇偶性を定め,同様に答える。他のポーンたちも同じだ。この戦略により,もし1番のポーンの63が正しく p1 ならば全員が自分のゼッケンを当て,そうでないと全員が自分のゼッケンを間違えて「18」と答えるが,その可能性は半々だ。

 

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

 

 

問題に戻る

 

 

 

問題はこちらです