パズルの解答
まず、前回の宿題から片付けましょう。次のような問題でした。
【問題】
前回紹介したパズル「9枚の金貨」は、9枚の中に1枚だけ軽い偽物が入っている状態で、同じ重さで釣り合う天秤秤を使って、最も効率的に偽物を見つけ出す方法を考える──というものでした。その場合には、金貨を3枚の組に分けることで2回の計測で偽物を発見できました。
では、偽物を含む金貨が10枚あった場合には、どのような手順を採れば効率的に偽物を見つけ出せるでしょう？
【解答】
3枚×2組＋4枚に分ける
金貨が9枚の場合には、それを3枚×3組に分けることで、1回目の計測で偽物の入っている1組（3枚）を特定できました。すると、あと1回の計測で偽物が判明します。
金貨が1枚増えて10枚になると、3枚×2組＋4枚という分け方が考えられます。この場合、うまくいけば1回目の計測でどちらか一方が軽いとわかり、9枚の場合と同じように2回の計測で偽物が判明します。
しかし、1回目の計測で2組が釣り合った場合には、残る金貨が4枚となるため、2枚ずつ秤に乗せて調べなければなりません。このときには必ずどちらか一方が軽いとわかるので、軽い方の組を1枚ずつ秤に乗せて3回目の計測を行うことになります。
つまり、最短2回、最長3回の計測が必要です。
5枚×2組に分ける
次に、10枚を5枚×2組に分けることが考えられます。この場合は、1回目の計測で偽物の混じった方が必ず軽くなります。これで、対象は5枚に絞られました。
この5枚を2枚×2組＋1枚に分けます。2枚の組同士を秤に乗せて釣り合えば、残った1枚が偽物です。もし釣り合わなければ、軽い方の2枚を1枚ずつに分けて秤に乗せます。この3回目の計測で偽物がわかります。
つまりこの場合も、最短2回、最長3回の計測が必要となります。
どちらも同じ手間だけれど……
単純に考えれば、どちらも同じ回数で偽物を見つけられることになります。が、ここで『対象が少なければ手数が減る→見付かる可能性が高くなる』ことに着目すれば、金貨の分け方によって以下のような違いのあることになります。
・5枚×2組の場合
1回目の計測で必ず不均衡となるため、2回目にはどちらか一方の5枚が対象になります。
・3枚×2組＋4枚の場合
1回目の計測で天秤に乗せた3枚同士が釣り合うか不均衡になるかは不確定ですが、どちらにせよ2回目の計測対象は3枚または4枚に絞り込めます。
5枚の中から1枚を見付けるより、3枚または4枚の中から見付ける方が手数が少なくなるはずです。
さらに、1回目の計測対象となる3枚×2組＝6枚の中に偽物が混じっている可能性の方が、残る4枚に混じっている可能性より若干高いので、2回目に3枚が対象となる場合の方が高くなります。すると当然、2回目の計測で偽物を見付けられる可能性が高くなります。
どちらが正解──ということではありません。こうやってあれこれと考え、頭の体操をすることが大切なのです。
|
|
|
TOP