偽金貨を探す - いぬおさんのおもしろ数学実験室

　ブログで紹介したアメリカの刑事ドラマ『刑事コロンボ』

に「殺しの序曲」という回があります。中でパズルが出てきました。シグマ協会という団体があります。この団体への入会資格はただひとつ、知能テストの成績が世界の上位2％に入ること。ここで殺人事件が起こり、その犯人がコロンボに出題します。「金貨の入った袋が10個ある。どの袋にも50枚ずつの金貨が入っているが、あるひとつの袋だけはすべて偽の金貨である（50枚すべてが偽金貨）。本物の金貨は1枚100ｇ、偽の金貨は1枚110ｇである。このとき、台秤を1回だけ使って偽の金貨入りの袋を特定せよ」という問題です。台秤ですから、袋を乗せると重さが表示されます。体重計みたいなものですね。たまたま偽の袋を選んで乗せれば110ｇ×50＝5500ｇで、「これが偽金貨の袋だ！」と分かりますが、本物入りの袋を選んでしまうと5000ｇ、「本物だったか……」で終わり。どうしますか？　袋から金貨を出してもOKです。コロンボは考えた末、「1つ目の袋からは1枚、2つ目の袋からは2枚、……と金貨を取り出し、合計55枚（1＋2＋…＋10＝55）の重さを量る。重さが例えば5580ｇだったら8番目の袋が偽金貨の袋」という答えを出します。全部本物だったら5500ｇになるはずで、8個目の袋が偽だったら80ｇ重くなるわけです。なるほど、うまい。

　ではもう一段階難しい問題を。今度は袋の数は6個。そのうち、偽金貨の袋が何個あるか分からない。このときやはり台秤を1回だけ使って、偽の袋を特定してください。偽金貨入りの袋が3個かも知れないし、5個かも知れないわけです。それぞれの袋から何枚かずつ取り出して1回だけ重さを測り、どれとどれが偽の袋か判断する、ということです。ここでしばらく考えてください…… 。

　実は「どんな自然数も1，2，4，8，16，32，……（2の累乗）の和でひと通りに表せる」という事実があるのです。これを利用します。1つめの袋、2つめの袋、……からそれぞれ1枚、2枚、4枚、8枚、16枚、32枚を取り出せばよいのです。例えば1，3，4番目の袋が偽金貨入りなら、10＋40＋80＝130ｇ重くなります。13を2の累乗の和で表す方法は1通りですから（13＝1＋2＋8）、「130グラム重い」と分かればどの袋が偽なのか分かります。