パズル～9枚の金貨

今回は、いきなりパズルを出題しましょう。有名なパズルなので、解き方を知っている人も多いかと思います。しかし、重要なのは答をさっと提示できるかどうかではなく、どうやってその答えにたどり着いたのか？　という「考える過程」です。

問）
9枚の金貨があります。その中の1枚は偽物ですが、あまりにそっくりに作られているので、見分けがつきません。ただ、偽物は本物よりわずかに軽いことだけが判っています。　天秤式の秤（はかり）を使って、最も少ない回数で偽物を見付けるには、どうすればよいでしょう？

-------- Let's think! ----

答）
以下の手順が考えられます。

9枚の金貨を3枚ずつ3組に分けます。各組をA、B、Cとします。
秤にA組の3枚とB組の3枚を左右の皿に乗せます。
秤が釣り合えば、AとBはすべて本物だと分かるので、残るC組の3枚に偽物が混じっていることになります。
もし秤が釣り合わなければ、上がった方の皿（AまたはBのどちらか）に偽物が混じっていることになります。
これで、偽物の混じった金貨は3枚に絞れます。
3枚の金貨の中から2枚を取り出し、左右の皿に乗せます。
秤が釣り合えば、残る1枚が偽物です。
釣り合わなければ、上がった皿に載せた金貨が偽物です。

結果、2回の計測で偽物が判別できます（図1）。

図1：金貨3枚に分ければ2回で偽物が見付かる

1枚ずつの計測は無駄が多い

この問題を考える過程を追ってみましょう。

単純に考えれば「金貨を1枚ずつ皿に乗せる」という方法が思い浮かびます。この方法では、まず1枚の金貨を一方の皿に乗せ、残った8枚の金貨を1枚ずつ順番にもう一方の皿に乗せていかなければなりません。

すると、運がよければ最初の1回で偽物が分かることもありますが、運が悪ければ最後の1枚まで分からないこともあります。この場合、7回目の計測で8枚すべてが本物だとわかるので、残った最後の1枚を皿に乗せる必要はありません。よって7回の計測が必要になります。

よって、最小で1回、最大で7回の計測が必要だということになります。

TOP

2枚ずつでも非効率

次に、金貨を2枚ずつ皿に乗せることを考えてみましょう。

この場合、最初の2枚ずつで釣り合わないことがあります。すると、上がった方の2枚を1枚ずつ皿に乗せて量れば、2回目で偽物が分かります。

最悪の場合は、2枚ずつの組を3回計測しなければなりません。3回目の計測で釣り合わなければ、上がった方の2枚を1枚ずつ皿に乗せて量ります。

よって、最小で2回、最大で4回の計測が必要だということになります。

TOP

偶然に頼ってはいけない

これらの方法では、運がよければ最小1回で判別できます。しかし、何番目の計測で偽物を皿に乗せるか――といったことは、偶然でしかありません。それに対して、金貨を3枚×3組に分けた場合は、どのような場合でも2回の手間で済みます。

処理にかかる手間――オーダーには、偶然に頼ることなく、異なる状況で繰り返し実行した結果、平均して少なくて済むことが求められます。

TOP

NEXT PAGE >>

【質問１】コラムをどれくらい読みましたか？

熟読した途中でやめたさっと目を通した印刷してこれから読む

【質問２】役に立つ内容でしたか？

参考になった参考にならなかった

ご自由にコメントを記入してください