金貨問題の解答編

in Uncategorized
img082.jpg ビルゲイツの面接試験ネタに便乗に便乗の金貨問題に現時点で全くコメントやトラックバックが無い状態であるが、出題した以上解答編を書かなければなるまい^^;。 問題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 “金貨問題の解答編”

  1. marina。

    ひとつだけ「金貨チョコ」だったら、
    灼熱の砂漠にちょっとおけば、
    偽金貨が分かりますね。
    こんにちは♪

  2. かわうそ

    お〜marinaさんですねいらっしゃいませ〜。
    ねとらじ放送marina radio 200回祭りどうもおつかれさまでした。
    金貨チョコを砂漠に置くときはチョコっとにしておくと、後で食べるのに便利ですねネ^^。

  3. ぴにおん

    ぴにおんが発見して参上しましたYO
    えーと、三つの引き出しがあって、1つには本物の金貨が、1つには偽物の金貨が、もう一つはカラッポです。そんでなんたらかんたら、という数学的論理クイズがありましたが答えを忘れましたw。
    容量の定まった2種類の容器の水を上手く移し変えたり、捨てたりして無理そうな容積を正確に測る数学クイズもありましたが、具体的なクイズの内容すら忘れましたw。

  4. かわうそ

    ぴにおんさんいらっしゃいませ〜。
    引き出しという設定からすると、その問題は情報と確率に絡んでいそうですね。
    いずれにしても引き出しは多いに越したことはありません^^。

Leave a Reply

*


14個金貨問題

in Uncategorized
重さの異なる1個の偽造金貨を見つけるために、天秤を最小回数使う問題です。このブログサイトを立ち上げるきっかけになったLife is beautifulからの出題。 13個問題の方は私の考えと同サイトの模範解答がほぼ同じでした。 14個問題の方の模範解答をまだ見てませんが私は以下のように考えました。 金貨を5個ずつ天秤にのせて比べるが、そのうち1つは本物を使う。(1回目) のせた金貨をそれぞれ[RABCD](Rは本物)と[EFGHI]、のせなかった金貨を[JKLMN]とする。 つり合った場合の解法は13個問題と同じ。 どちらかに傾いた場合は以下の組み合わせで天秤にかける。(2回目) [RJKLMN][ABCEFG] 傾けば偽造金貨が重いか軽いかがわかり、かつ[ABC]か[EFG]のどちらかにあるかがわかる。よって3回目でわかる。 つり合えば[DHI]の中に偽造金貨があるので[H][I]で天秤にかける。これも3回目でわかる。 13個問題を解いた経験があればかなり考え易いということですね。

Leave a Reply


神田川の桜がピーク

in Uncategorized
家の前の神田川の桜がピークを迎えております。 この桜並木を見るにつけ思うのは、これだけの桜を植えようと企画した人の想像力。素晴しい景色になるだろうことも、それをあらかじめ想像し、企画構想する人がいなければこの世のものとして現れてくることができません。現れてきたものを素晴しいと鑑賞することはたやすいことで、無いものを想像できた先人の能力とセンスこそ賛えられてしかるべきですね。

Leave a Reply