予約注文開始アーキテクトという職種ビル・ゲイツの面接試験-宿題の解答2005.06.10先日、宿題に出しておいた金貨クイズ、今回は計4名が正しい答えを送ってきた。予想に反して、そのどれもが私が用意していた答えと異なるものであった。予想外だったもので、検証に手間取ってしまったが、どれも正しく偽造品を見つけることの出来る手順であった。[模範解答]まず考えやすくするために、中間ゴールとして、2回天秤を使ったところで、後1回で偽金貨が分かる状態にまで持って行くことにする。その状態には、(a)2つの金貨のうちどちらかが偽造品だ判明している状態、(b)3つの金貨に偽造品が含まれていることが判明しており、かつ、すくなくともそのうち2つが偽造品だった場合に本物より重い(もしくは軽い)のが分かっている状態、の2通りがある。(a)の場合には、片方の金貨を本物の金貨と比べて見れば良いし、(b)の場合にはそのうち偽造品だった場合に本物より重いのか軽いのかが分かっている二個の金貨の重さを比べれば良い。金貨を4個ずつ天秤に乗せて比べる(1回目)。このとき、左の皿に置いたコインを【ABCD】、右の皿に置いたコインを【EFGH】、残りの5つを【VWXYZ】と呼ぶ。1.釣り合った場合、【VWXYZ】の中に偽造品があることが判明。【VWX】と【ABC】を比べる(2回目)。(a)2.【ABCD】が重い場合、【VWXYZ】の中に偽造品がないこと、【ABCD】の中に偽造品がある場合には重い偽造品、【EFGH】の中に偽造品がある場合には軽い偽造品であることが判明。【ABCEF】と【VWXYZ】を比べる(2回目)。(b)3.【ABCD】が軽い場合は、2と全く同じ操作で良いので省略(「重い」と「軽い」を入れ替えて考えれば良い)。この問題につまずく人はたいてい、既に本物だと判明した金貨をリファレンスとして使えるということに気がつかないために苦労するようだ。ステップ2に至った段階で、「せっかく13個から8個に絞ることが出来たのだから」と、【VWXYZ】を頭の中から除いて考えてしまうようだ。ちなみに、模範解等を考えているうちに、この問題にある工夫をすると、14個の金貨の中からでも偽造品を見つけられることが判明した。TypepadTop。