|
時計台と文学部越しに眺める半田山の黄葉。半田山も岡大の敷地に含まれているので、借景式ではなく、敷地内風景ということになる。 |
じぶん更新日記1997年5月6日開設Copyright(C)長谷川芳典 |
12月のインデックスへ戻る
最新版へ戻る
|
|
時計台と文学部越しに眺める半田山の黄葉。半田山も岡大の敷地に含まれているので、借景式ではなく、敷地内風景ということになる。 |
|
【思ったこと】 151205（土）刑事コロンボ「殺しの序曲」の偽金貨クイズとその拡張(3) 先週に続いて、ニセ金貨問題の拡張についての考察。この種のパズルの解法はネットで調べればちゃんと紹介されているであろうが、ここではあくまで自力で解く楽しみを味わっていきたいと思う。 さて、前回拡張した問題は以下の通りであった。 外見は見分けがつかないが重さの異なる金貨Ａと金貨Ｂ（ここでは重いほうの金貨をＢとする）があります。そのいずれかを入れた袋がｎ個あります。袋の数はいくら多くてもよろしい。それぞれの袋に複数の金貨が入っているが、いずれも金貨Ａのみ、または金貨Ｂのみであって、混ざって入っている袋は１つもない。３回の計量ですべての袋を、金貨Ａの袋と金貨Ｂの袋に分けるにはどうすればよいか？ なお、前回は、袋の番号を１から順番につけることとしていたが、今回からは０（ゼロ）から順番につけることとする。理由は、最初の１つの袋（袋０）と残りの袋（袋１〜袋n-1）を区別して扱う際、残りの袋番号の最小値を１(すなわち袋番号は１〜n-1）にしたほうが分かりやすいと考えたからである。 まず【計量１】と【計量２】は以下のように行う。
さて、前回、【計量３】の方法として、 【計量３】「袋の番号ｎに対応して２n-1個取り出す」という方法が考えられる。要するに、各袋に二進数で、1、10、100、1000、．．．という番号をふり、その番号に対応した個数（二進数表記）を取り出すというやり方であり、計量結果から自動的に、二進数表記の「1」と「0」に、金貨Ａと金貨Ｂの袋を対応させることが可能になるはず【但し未検証】。と記した。 この方法は、
ここで、２種類の金貨の重さの差をdとする。金貨Ａ（軽い方）のn-1倍と【計量２】との差は、 d×（【計量３】に含まれていた金貨Ｂの枚数） となる。この時の金貨Ｂの総数は、袋１〜袋n-1を右から順に一列に並べて金貨Ｂが入っている袋に「１」、金貨Ａが入っている袋に「０」の印をつけた時の二進数表記の数と同一になる。 例えば、袋１〜袋４のうち、袋２と袋４に金貨Ｂが入っていた場合、右から袋を次のように並べると、 袋４、袋３、袋２、袋１ に対応して、 １、０、１、０ というように印がつけられる。これに対応した二進数は（1010）2となる。この時の【計量３】の結果は、金貨Ａのn-1倍に d×（1010）2 を加えた重さとなる。上記の例で言えば、（1010）2は十進法の10であるので【計量３】は金貨Ａ4枚分に加えて、d×10だけ重くなっていることになる。 重要な点は、「０」または「１」の印をどのようにつけるかというパターンと【計量３】の重さが一対一に対応している点である。よって、【計量３】の重さから自動的にどの袋に金貨Ｂが入っているのかを見分けることができるという次第。 ちなみに、この論法は、二進数でなくて、三進数、四進数、．．ｎ進数いずれでも構わない。但し、ｎの数が多ければ多いほど、【計量３】に乗せる金貨の枚数は莫大となり、ついには地球の重さを超えてしまうかもしれない。 さて、次のステップは、２種類の金貨の１枚あたりの重さの差が分かっておらず、金貨Ａと金貨Ｂの袋の数も分からないという場合である。【計量１】の金貨のn-1倍と【計量２】の結果の差をSとすると、１枚あたりの金貨の重さの差dは、
d×（1010）2 というような増量分の値がすべて異なる値をとりうるかという点にある。もし、異なるpであるのに同じ値をとるとすると、【計量３】だけでは、いくつの袋に金貨Ｂが入っているのかを同定することができなくなる。 次回に続く。 |