8枚のコインに、1枚だけ重いものが混じっています。天秤で4枚と4枚を比べれば、候補を半分にできそうです。でも、量らないコインを残したほうが、少ない回数で見つかることがあります。
天秤パズルでは、「左が重い」「右が重い」「つり合う」の3通りを、どう使うかが手がかりになります。8枚と13枚の例で、測り方と、それより少ない回数では足りない理由を考えましょう。
目次
今回は「重い1枚」と分かっている問題
天秤の問題は、条件が違うと解き方も変わります。この記事では、次のルールを共通にします。
- 異常なコインはちょうど1枚で、正常なものより重いと最初から分かっている
- 正常なコインはすべて同じ重さ。見た目では異常を判別できない
- 重さについて使える情報は、理想的な等腕天秤の3通りの結果だけ。正確な重量や傾きの角度は読めない
- 外部のおもりは使わない。前の結果に応じて、次に量る組を変えてよい
コインには区別のためA、B……と名前を付けます。「最少回数」は、たまたま早く分かる場合ではなく、どれが重くても必ず特定するために必要な回数です。
例題1 8枚から、重い1枚を探す
A〜Hの8枚に重いコインが1枚だけあります。最大で何回、天秤を使えば必ず特定できるでしょう。回数だけでなく、結果ごとの測り方も考えてみてください。
ヒント1を見る
4枚対4枚では、必ずどちらかが重くなります。「つり合う」という結果も、候補を絞るために使えないでしょうか。
ヒント2を見る
A・B・CとD・E・Fを比べ、G・Hは天秤に載せずに残してみましょう。
答えと測り方を見る
答えは最大2回です。まず左にA・B・C、右にD・E・Fを載せます。結果に合わせて、2回目を次のように変えます。
| 1回目 | 残る候補 | 2回目 |
|---|---|---|
| 左が重い | A・B・C | A 対 B |
| 右が重い | D・E・F | D 対 E |
| つり合う | G・H | G 対 H |
候補がA・B・Cなら、A対Bで重かったほうが答えです。つり合えば、載せていないCが重いと分かります。D・E・Fの場合も同じです。
G・Hが候補なら、G対Hで重かったほうが答え。この枝では、どちらか1枚が重いので、つり合いは起こりません。
最初に3枚ずつを比べると、「つり合う」からも、残した2枚が候補だと分かります。天秤に載せなかったコインについても、情報が得られるのです。
1回では足りない理由
8枚のどれが重いかは、8通りあります。一方、天秤を1回使って返ってくる結果は最大3通りだけです。
8通りの候補を、3通りの結果にすべて別々に対応させることはできません。同じ結果になる候補が残るため、1回で必ず特定する方法はありません。2回でできる手順があり、1回ではできないので、最少回数は2回と確かめられます。
最初に4枚対4枚を量ると、重い側に4候補が残ります。残り1回の3通りの結果では4候補を区別しきれないため、この始め方では最大2回に収まりません。
例題2 13枚なら、何回あればよい？
同じ条件で、コインをA〜Mの13枚に増やします。重いコインはやはり1枚だけです。必ず特定するための最少回数と、測り方を考えてみましょう。
ヒント1を見る
最初から同じ枚数の3組に分ける必要はありません。ただし、天秤の左右には同じ枚数を載せると、結果を判断しやすくなります。
ヒント2を見る
A・B・C・DとE・F・G・Hを比べ、I・J・K・L・Mを残します。結果が出た後、4候補または5候補を、あと2回で区別できるでしょうか。
答えと測り方を見る
答えは最大3回です。1回目は、左のA・B・C・Dと、右のE・F・G・Hを比べます。
- 左が重い：2回目はA・B対C・D。重かった側の2枚を、3回目に1枚ずつ比べます。
- 右が重い：2回目はE・F対G・H。重かった側の2枚を、3回目に1枚ずつ比べます。
- つり合う：候補はI〜M。2回目はI・J対K・Lです。左が重ければ3回目にI対J、右が重ければK対Lを比べます。つり合えば、残したMが答えです。
4候補の枝では、2回目の2枚対2枚も、3回目の1枚対1枚も、どちらかが必ず重くなります。どの枝でも、残った候補の中に重い1枚があることを使っています。
Mが重い場合は、2回連続でつり合って答えが出ます。それ以外の場合は3回。すべてのコインについて、3回以内で特定できます。
13枚は、なぜ最大2回では解けない？
1回目の結果が3通りあり、それぞれの後に、2回目の結果が最大3通りあります。したがって、2回で区別できる結果の並びは最大3×3＝9通りです。
1回目の結果に合わせて2回目の測り方を変えても、それぞれの枝から分かれる結果は最大3通り。この上限は変わりません。途中で答えが分かって測定をやめても、区別できる候補が増えるわけではありません。
重い位置は13通りあるので、9通りでは足りません。つまり、必ず特定するには3回目が必要になる場合があります。先ほどの手順で最大3回を達成できるため、最少回数は3回です。この数え方は、鳩の巣原理にもつながります。
条件が変わったら、候補を数え直す
「異常な1枚が重いか軽いか分からない」問題では、天秤が左へ傾いた理由が、左の重いコインなのか、右の軽いコインなのかも考える必要があります。今回の手順を、そのまま使うことはできません。
また、3回の結果が最大27通りだからといって、条件の違う問題でも27枚を必ず区別できるとは限りません。結果の数は回数の下限を考える手がかりです。実際に解けると言うには、すべての場合に対応する測り方も必要です。
「この結果なら何が残る？」と候補を絞るのが面白かったら、作者のパズルアプリ一覧から、ほかの作品も探してみてください。
考え方の参考：MIT 6.006 Recitation 10、Problem 5「Fake coin」。天秤の3結果と分岐による下限を扱う教材です。本記事の8枚・13枚の条件と手順は、各候補を確かめて構成しました。