コインが本物かどうかを判別するパズルの話をします。
【起】
偽コインのパズルというと、
天秤を何回か使って重さの違う偽コインを見分けるパズルもありますが、
ここで話題にするのは重量計を1回使って偽コインの入った袋を見分けるパズルです。
ここにコインがたくさん入った袋がいくつかある。
偽コインが入った袋には偽コインだけが入っており、
本物と偽物のコインは10gと9gのように重さが異なる。
重量計を1回だけ使って、偽コインが入っている袋を判別したい。
てな感じで前提が説明され、続いて次のような2問がセットで出されます。
第1問
5袋あり、そのうちの1つだけが偽コインの袋である。
→各袋からそれぞれ1,2,3,4,5枚のコインを取りだして重さを量る。
たとえば重さが147gだったら、3枚取りだした袋が偽コインの袋。
第2問
5袋あり、その中に偽コインの袋がいくつあるかは不明である。
→各袋からそれぞれ1,2,4,8,16枚のコインを取りだして重さを量る。
たとえば重さが300gだったら、2枚と8枚取りだした袋が偽コインの袋。
よく見かけるパズルで、古典と言ってよいでしょう。
【承】
ここからが本題。
1月のパズル懇話会の例会で、
第2問の形式で各袋の中にコインが16枚も入っていない場合の話題が出ました。
ハッとしました。
何度も接するうちに条件反射のように刷りこまれてしまっていたが、
そういえば、昔々初めてこのパズルに接したときに感じた違和感。
第1問なら1,2,4,5,7、第2問なら1,10,100,1000,10000でもできる、
要は答えは他にもいっぱいある、という違和感。
第2問の形式で、各袋から取り出す枚数の最大値を減らせるんじゃないか。
偽コインの袋の出現パターンは2^N通りあって、それらが全部区別できれば良い。
寝る前にフトンの中でざっと検討したら、出てくる出てくる。
3袋は1,2,4が普通だが、同じ最大4でも2,3,4もある。
4袋は1,2,4,8が普通だが、3,5,6,7なら最大7に減らせる。
5袋は1,2,4,8,16が普通だが、3,6,11,12,13や6,9,11,12,13なら最大13に減らせる。
普通に言われている2^N枚取る方法は、全袋から取り出す枚数の合計を最小にするけど、
1つの袋から取り出す最大枚数については、決して最小にはなっていなかった。
この最大枚数は袋数が増えるに従って、1,2,4,7,13…である。
その先の検討は進んでいなかったけど、とりあえずこのことを
3月のパズル懇話会の例会で発表しました。
長くなったので【転】【結】は別の機会に。
