金貨問題の解答編
ビルゲイツの面接試験ネタに便乗に便乗の金貨問題に現時点で全くコメントやトラックバックが無い状態であるが、出題した以上解答編を書かなければなるまい^^;。
問題1
各袋に50枚の金貨が入っていた場合、ヘンリー君は偽造金貨の袋を判別することが可能でしょうか。
その場合の方法は?
解答
1番目の袋から1枚、2番目の袋から2枚、3番目の袋から4枚と、n番目の袋から2^(n-1)枚の金貨を取り出し、全てを重量計に載せます。その重さと、全て正規の金貨であった場合の重量との差から偽造金貨の枚数がわかります。枚数を10進法から2進法に直してみると、nの位が1か0かで、n番目の袋の金貨が偽造か否かがわかります。
なおこの方法では最後の6番目の袋からは2^(6-1)=32枚の金貨を取り出すことになります。
ちなみに偽造金貨の袋を返送するときには、重量計に載せた分の金貨も忘れずに^^。
問題2
各袋に24枚の金貨しか入っていなかった場合、ヘンリー君は偽造金貨の袋を判別することが可能でしょうか。
解答
正解は意外にも「可能である」ですが、私自身は確認していません。力技で(コンピューターを用いて)考えられる組み合わせを調べ、可能である組み合わせが存在することを確かめられるのですが、それでは解法として面白くありませんね。これ以外の、私の知らないよりエレガントな解法を継続して募集することといたします。