ビルゲイツの面接試験ネタに便乗に便乗の金貨問題に現時点で全くコメントやトラックバックが無い状態であるが、出題した以上解答編を書かなければなるまい^^;。
問題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枚の金貨しか入っていなかった場合、ヘンリー君は偽造金貨の袋を判別することが可能でしょうか。
解答
正解は意外にも「可能である」ですが、私自身は確認していません。力技で(コンピューターを用いて)考えられる組み合わせを調べ、可能である組み合わせが存在することを確かめられるのですが、それでは解法として面白くありませんね。これ以外の、私の知らないよりエレガントな解法を継続して募集することといたします。 金貨問題の解答編
in Uncategorized
ビルゲイツの面接試験ネタに便乗に便乗の金貨問題に現時点で全くコメントやトラックバックが無い状態であるが、出題した以上解答編を書かなければなるまい^^;。
問題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枚の金貨しか入っていなかった場合、ヘンリー君は偽造金貨の袋を判別することが可能でしょうか。
解答
正解は意外にも「可能である」ですが、私自身は確認していません。力技で(コンピューターを用いて)考えられる組み合わせを調べ、可能である組み合わせが存在することを確かめられるのですが、それでは解法として面白くありませんね。これ以外の、私の知らないよりエレガントな解法を継続して募集することといたします。 4 Responses to “金貨問題の解答編”
Leave a Reply
ひとつだけ「金貨チョコ」だったら、
灼熱の砂漠にちょっとおけば、
偽金貨が分かりますね。
こんにちは♪
お〜marinaさんですねいらっしゃいませ〜。
ねとらじ放送marina radio 200回祭りどうもおつかれさまでした。
金貨チョコを砂漠に置くときはチョコっとにしておくと、後で食べるのに便利ですねネ^^。
ぴにおんが発見して参上しましたＹＯ
えーと、三つの引き出しがあって、１つには本物の金貨が、１つには偽物の金貨が、もう一つはカラッポです。そんでなんたらかんたら、という数学的論理クイズがありましたが答えを忘れましたｗ。
容量の定まった２種類の容器の水を上手く移し変えたり、捨てたりして無理そうな容積を正確に測る数学クイズもありましたが、具体的なクイズの内容すら忘れましたｗ。
ぴにおんさんいらっしゃいませ〜。
引き出しという設定からすると、その問題は情報と確率に絡んでいそうですね。
いずれにしても引き出しは多いに越したことはありません^^。