偽物の銀貨を当てろ・その2:偽物の重さがわからない場合

問題を解く前に改めて述べると,100枚の銀貨の中に偽物(本物と重さだけが異なる)が1枚混ざっていて,それを天秤だけを使って当てるというものでした。ただし,天秤は5回までしか使うことができません。

前回は,偽物の銀貨が本物より重いことがわかっているという条件のもとで,それが可能だということを,具体的な方法を示すことによって証明しました。

そして今回は,偽物の銀貨が本物より重いか軽いかわからないという条件のもとで,しかし天秤は同じく5回使うだけで偽物を当てることが可能であることを,やはり具体的な方法を示すことによって証明します。

この場合で鍵になるのは,銀貨が12枚のときです。そのときは,天秤を3回使うだけで必ず偽物を見つけることができて,それが重いか軽いかまでわかるのです。その難関さえクリアしてしまえば,前節の方法論を適用することができて上手くいくのです。

前回と同様に,最初のステップでは,銀貨の全体から天秤に乗せるものの集合 AB を取り出します。それらは互いに交わりがなく,必ず同じ枚数の銀貨からなるものとします。残りの銀貨の集合を C とします。C が含む銀貨の枚数は A のそれと異なる場合もあります。銀貨の集合を分けたら,A を左の皿に,B を右の皿に乗せて,天秤を1回使います。

銀貨12枚ならば天秤3回で十分

この場合は銀貨の集合が3等分できるので,その通り ABC それぞれに4枚ずつ銀貨を分けます。そして,天秤で1回目の測定を行います。

f:id:azapen6:20191210085419p:plain

今回は偽物の重さが本物と異なることしか事前情報がないため,測定結果から判断できることは次の通りです:

  1. \gt ならば,偽物は A または B の中にある。C の銀貨はすべて本物
  2. \lt ならば,偽物は A または B の中にある。C の銀貨はすべて本物
  3. = ならば,偽物は C の中にある。AB の銀貨はすべて本物

今回のような重さがわからない状況では,偽物を特定するために本物であることがわかっている銀貨を利用することが重要となります。前節の100枚の場合に,本物とわかっている銀貨はその場にある限り自由に使ってよいということを議論しました。そのために,先の比較では,すべて本物であることがわかっている集合にも言及しました。

偽物が C の中にある場合

まずは当たりがついている場合について,偽物を当てる方法を示します。C の銀貨に名前をつけて c_1c_2c_3c_4 とします。ただし,この時点では C の銀貨のどれも区別できていないことを断っておきます。

2回目の測定では,本物とわかっている銀貨を再利用します。C の中から3枚 c_1c_2c_3 を取り出して左の皿に,「A の中から3枚」取り出して右の皿に乗せます。

f:id:azapen6:20191226085237p:plain

  1. \gt ならば偽物は c_1c_2c_3 のどれかである。偽物の方が重い
  2. \lt ならば偽物は c_1c_2c_3 のどれかである。偽物の方が軽い
  3. = ならば偽物は c_4 である。重さについてはわからない

この結果を順に読んでいきましょう。以下,天秤の図では各場合について本物と確定した(ている)ものを橙色で,偽物と確定したものを紫色で表します。

Case \gt or \lt

この時点ではまだ偽物を特定できていないのですが,重さという重要な情報が得られています。ここまで来てしまえばもう答えも同然でしょう。

続く3回目の測定では,前節の9枚の場合の2回目と全く同じようにして,c_1c_2c_3 の中から偽物を一意に特定することができます。ここで偽物が重いか軽いかが判っていることが効いてきます。

Case =

この場合は,なんともう偽物が c_4 であることが特定できてしまいました。c_1c_2c_3 の重さが本物3個と同じであるということは,それらが本物であることを意味します。よって,一度も皿に乗せていないのもかかわらず,消去法で c_4 が偽物だとわかるのです。

続く3回目の測定では,本物1個(c_1c_2c_3 のどれでもよい)と比較して,偽物の c_4 が本物より重いか軽いかを判定します。

このようにして,1回目の比較で偽物が C の中にあるとわかっているときは,天秤を3回使うだけで偽物を当てることができます。加えて本物より重いか軽いかがまでわかるのです。

1回目の結果が \gt だった場合

簡単な方が片付いたので,1回目の比較で1と2,すなわち,偽物を含む集合を特定できていない場合に取り掛かります。以下では A の方が B より重い場合だけについて議論します。逆の場合は記号を入れ替えるだけで全く同じ議論ができます。ここでも便宜上,銀貨に名前をつけて,A の銀貨を a_1a_2a_3a_4 とし,B の銀貨を b_1b_2b_3b_4 とします。

2回目の測定では,AB から3枚ずつ取り出して比較します。ここでひと捻り加えて,a_3a_4 を右の皿に移し替えて,b_4 以外を天秤から下ろします。左の皿には「本物を1枚,C の中から」加えて数を合わせます。この操作の後では,左の皿には a_1a_2 と本物1枚,右の皿には a_3a_4b_4 が乗っています。天秤に乗っていないのは b_1b_2b_3です。そして,2回目の測定を行います。

f:id:azapen6:20191226085712p:plain f:id:azapen6:20191226085822p:plain

この結果を慎重に読んでいきましょう。なお,左の皿に本物を加えて数合わせしたことは比較結果に影響しないことを断っておきます。ここでも各場合について本物と確定した(ている)ものを橙色で,偽物と確定したものを紫色で表します。

Case =

天秤が釣り合ったということは,両皿に乗っている銀貨はすべて本物であると確定します。よって,偽物は天秤から下ろした b_1b_2b_3 のどれひとつです。また偽物の方が本物より軽いことが確定します。

続く3回目の測定では,その1の9枚の場合の2回目と全く同じようにして,b_1b_2b_3 の中から偽物を一意に特定することができます。

f:id:azapen6:20191226085854p:plain

Case \lt

結果が1回目と逆転したということは,反対の皿に移し替えたものに偽物が混ざっていたことを意味します。よって,a_1a_2 は本物で,a_3 または a_4 のどちらか一方が偽物です。また,どちらの場合も偽物の方が本物より重いことが確定します。A の方が B より重い場合について考えていることを思い出してください。

続く3回目の測定では a_3 を本物1枚(a_1a_2 のどちらでもよい)と比較します。それで釣り合わなかったならば,a_3 が偽物であり,逆に釣り合ったならば a_4 が偽物であることがわかります。

Case \gt

結果が1回目と同じだったということは,移し替えた a_3a_4 および,天秤から下ろした b_1b_2b_3 はすべて本物であることが確定します。よって,偽物は a_1a_2b_4 のどれかひとつです。

続く3回目の測定では,左の皿に a_1b_4,右の皿には本物を2枚(b_1b_2b_3 のどの2枚でもよい)を乗せます。そして,3回目の測定を行います。

f:id:azapen6:20191226085946p:plain

結果を読むにあたって重要なことは,左の皿に乗せた組が本物より重いか軽いかで,どちらが偽物かわかるということです。a_1 の重さは b_4 より重いか,あるいは,どちらも本物のときだけ同じです。よって,左の方が重い \gt とわかった時点で a_4 が偽物であることが確定します。逆に左の方が軽い \lt とわかれば b_4 が偽物であることが確定します。どちらでもなく釣り合った = ならば,両皿に乗っている銀貨はすべて本物であることが確定し,天秤から下ろした a_2 が偽物であることが確定します。これらをまとめると:

  1. \gt ならば a_1 が偽物で,本物より重い
  2. \lt ならば b_4 が偽物で,本物より軽い
  3. = ならば a_2 が偽物で,本物より重い

以上ですべての場合を網羅できました。本節の結論を述べると,銀貨が12枚の場合は,偽物が本物より重いか軽いかわからないとしても,天秤を3回使うだけで偽物を当てることができる。また,偽物が本物より重いか軽いかもわかる。

いやぁ,大変大変。こういうのを sleight of hand と言うのですね。ただ,これさえ片付けば後は楽勝です。

銀貨36枚ならば天秤4回で十分

前節より銀貨が3倍に増え,天秤はもう1回使ってよいことになりました。前節の結果さえわかっていれば,この場合は驚くほど簡単にできます。

方法論は,銀貨3枚を1組にして銀貨1枚と同様に扱うというものです。36はもちろん3等分できて12組に分けることができますね。もし偽物の銀貨1枚が本物より重いとすると,それを含む銀貨3枚の組も,本物だけからなる他のどの組よりも重いこと,そして,そのような組が1組しかないことが言えます。偽物が本物より軽い場合も同様です。これより,銀貨3枚の12組を「超銀貨」12枚と見なしても全く同じ議論ができるのです。

そして,12枚の超銀貨に前節の方法を適用すると,天秤を3回使うだけで偽物の超銀貨を当てることができて,同時にそれが本物の超銀貨より重いか軽いかまで確定できます。

あとは,偽物の超銀貨を3枚の銀貨(1枚だけ偽物を含む)に戻して,残りの1回で偽物の銀貨1枚を当てるだけです。ここで,偽物の銀貨の方が本物より重い/軽いということが,最後の天秤を使う前に確定していることは決定的です。それがわかっているからこそ,1回で偽物を当てることができるのです。

結論を述べると,銀貨が36枚の場合は,偽物が本物より重いか軽いかわからないとしても,天秤を4回使うだけで偽物を当てることができる。また,偽物が本物より重いか軽いかもわかる。

銀貨100枚ならば天秤5回で十分

ついに本題の銀貨が100枚の場合です。ここまで来れば決着も同然と思ったのですが,意外にも足を取られるところがありました。それはさておき,結論を先に述べておくと,天秤を5回使うだけで偽物を当てることができます。偽物の方が重いか軽いかもわかります。

前節の「超銀貨」を思い出すと,100枚の銀貨を12枚の超銀貨(9枚1組)に分ければいいと見当がつきます。ところが,100は12で割り切れないので,そのままでは通らないこともわかります。その場にない銀貨は使えないので,8枚足して煩悩の数にして12で割り切らせることは不可能です。どうする?ツリメデス? ここで足踏みしているうちに,王の気が変わってしまうかもしれないぞ!

というわけで,一時的なものとして,9枚組より少ない組を「不完全超銀貨」として数に加えて,12枚の場合をシミュレートできるかについて考えます。なぜそれを認めていいかというと,最初の比較の時点では,天秤に乗せない銀貨の集合 C は9枚1組の「完全超銀貨」に分けられなくても問題ないからです。もし最初の比較で C の中に偽物があるとわかったならば,天秤に乗せていた本物の銀貨を不完全超銀貨に充当して,次のステップでは完全超銀貨として扱ってやればいいのです。

ここで12枚の場合を思い出すと,最初のステップでは,銀貨を4枚ずつ3つの集合に分けて,うち2つの集合 AB の8枚の銀貨を天秤に乗せ,残りの4枚の銀貨の集合 C を天秤に乗せないとしました。もし9枚1組の超銀貨で同じことをしようとするならば,AB はちゃんと9枚1組の完全超銀貨4枚,つまり36枚ずつでなければなりません。そうすると C には28枚の銀貨が含まれることになります。これを,8枚の完全超銀貨3枚(27枚の銀貨)と,1枚の銀貨だけを含む不完全超銀貨1枚と見なします。

さて,1回目の比較で偽物の超銀貨が AB の中にあるとわかったならば,その後で C の超銀貨を何枚使うかを見直さなければなりません。この方法が上手くいくためには,C の中の本物の完全超銀貨は3枚までしか使えません。というわけで上にスクロールして見るると……「本物を1枚,C の中から」という部分だけで C の銀貨を利用していました。他で本物が必要になった場合はすべて AB の中にあった銀貨を再利用しています。

これより,偽物の超銀貨が AB の中にあった場合は,後のステップでも不完全超銀貨に触れることなく,天秤を3回使うだけで,偽物の超銀貨を当てられることがわかりました。

次に,1回目の比較で偽物の超銀貨が C の中にあったときは,AB の中の本物の完全超銀貨(本物の銀貨だけからなる9枚組)1枚を崩して,C の中の不完全超銀貨に加えて完全超銀貨(偽物である可能性は残る)にしてやります。そうすると,C は揃った超銀貨4枚,うち1枚が偽物の超銀貨で,ちょうど1枚の偽物の銀貨を含む,という集合になります。この後で AB の中の7枚の本物の完全超銀貨を何枚使うかを再び上にスクロールして見ると……「A の中から3枚」だけ利用していました。つまり,この場合も天秤を3回使うだけで偽物の超銀貨を当てられることがわかりました。

以上,元の銀貨100枚を9枚1組の超銀貨12枚に分け,不足分は一時的に不完全超銀貨として扱い,後で本物の銀貨で埋めて完全超銀貨として扱ういう,大変回りくどい方法で上手くいくことがわかりました。

ここまででわかったことは,100枚の銀貨の中から天秤を3回だけ使って偽物の超銀貨,つまりは偽物を含む9枚の銀貨の集合にまで絞ることができる,同時に,偽物の銀貨が本物より重いか軽いかもわかる,ということです。あとは,天秤を2回使ってその偽物を当てるだけです。それは既にその1で片付いています。

以上ですべてが片付きました。結論を改めて述べると,銀貨が100枚の場合は,偽物が本物より重いか軽いかわからないとしても,天秤を5回使うだけで偽物を当てることができる。また,偽物が本物より重いか軽いかもわかる。

かくして,ツリメデスは王を驚かせ,死刑を免れたのでした。めでたしめでたし。