じぶん更新日記

1997年5月6日開設
Copyright(C)長谷川芳典



11月のインデックスへ戻る
最新版へ戻る

　夕食後の散歩時によく見かける猫。津山線の線路の上を移動したり、真夏は橋の上で寝ていたりする。夜間は上り下りそれぞれ１時間に１本程度の運行なので、列車が近づいた時だけ避ければのんびりできるようだ。

2015年11月28日（土）

【思ったこと】
151128（土）刑事コロンボ「殺しの序曲」の偽金貨クイズとその拡張(2)

　昨日の続き。まず、
ここに金貨の入った袋が数個あります。袋の数はいくら多くてもよろしい。それぞれの袋に複数の金貨が入っているがこの金貨の数もいくらでもよろしい。しかし１つの袋だけは全部偽造の金貨が入っておりこれは重量が違っている。３回の計量で偽造の袋を見分ける方法は？
という拡張問題についての復習。本当に３回の計量だけでニセ金貨の袋を見つけ出せるのかどうかを具体例で確認してみよう。ホンモノとニセモノの金貨１枚の重さは分からない、但し異なる重さであることだけは分かっているものとする。ここでは、袋が５つあるものとして、「袋１」〜「袋５」という番号をつけておく。
  1. 【計量１】袋１から金貨１枚を取り出して計量する。結果として100ｇであったとする。この段階では、これがホンモノなのかニセモノなのかは分からない。
  2. 【計量２】袋２〜袋５から金貨１枚ずつを取り出してまとめて計量。この重さは400ｇ（平均すると100ｇ）より重いか軽いかいずれかとなる。（平均して100ｇジャストだったとするとニセ金貨は１枚も存在しないことになり矛盾）。ここでは総重量が420ｇだったとする。この【計量２】によって、「ホンモノ100ｇ、ニセ金貨120ｇ」（袋１がホンモノであった場合）、もしくは、「ホンモノ105ｇ、ニセ金貨100ｇ」（袋１がニセ金貨であった場合）のいずれかとなる。
  3. 【計量３】袋２から２枚、袋３から３枚、袋４から４枚、袋５から５枚の金貨を取り出してまとめて計量。金貨は合計14枚となる。もし袋１がニセ金貨であったとすると、この時の総重量は105×14＝1470ｇとなるはず。つまり1470ｇであった時は袋１がニセモノであると確定する。また、そうでない場合は、袋１はホンモノであり、ホンモノの重さは100ｇとなる。この場合の計量結果は、袋２がニセモノであった場合は、100ｇ×12枚+120ｇ×2枚＝1440ｇになるはず。以下、袋３、袋４、袋５がそれぞれニセモノであった場合の総重量は、1460ｇ、1480ｇ、1500ｇとなるので、どの数値に対応しているのかによって、ニセモノの袋がどれであるのか分かる。


　上記の方法は袋の数がいくら多くても判定可能。もちろん、それぞれの袋の中に莫大な数の金貨があり、かつ、秤がどのような重さでも正確に計測できるということが前提にはなる。



　次に、この問題をさらに拡張して次のようにしたらどうなるだろうか？
外見は見分けがつかないが重さの異なる金貨Ａと金貨Ｂがあります。そのいずれかを入れた袋がｎ個あります。袋の数はいくら多くてもよろしい。それぞれの袋に複数の金貨が入っているが、いずれも金貨Ａのみ、または金貨Ｂのみであって、混ざって入っている袋は１つもない。３回の計量ですべての袋を、金貨Ａの袋と金貨Ｂの袋に分けるにはどうすればよいか？
　これについて、上記と同じやり方を試みたとする。但し、ホンモノ、ニセモノという区別ではなく、重さの異なる金貨Ａ、金貨Ｂの区別ということになる。Ａ、Ｂの付け方は任意なので、ここでは袋１の金貨をＡと決めておく。そうすると、
  1. 【計量１】袋１から金貨１枚を取り出して計量する。結果として100ｇであったとする。すなわち金貨Ａの重さは100ｇであると確定。
  2. 【計量２】袋２〜袋５から金貨１枚ずつを取り出してまとめて計量。この重さが400ｇであった場合はすべての袋は金貨Ａが入っていたことになる。いっぽう総重量が420ｇだったとする。
というところまでは上記と同一であるのだが、この段階では420ｇになった原因が、金貨Ｂが何枚含まれていたことによるのか、また金貨Ｂの重さが何ｇなのかということは確定できない。つまり、要するに、
  • １つの袋だけが金貨Ｂであった時は金貨Ｂの重さは120ｇ
  • ２つの袋が金貨Ｂで２つの袋が金貨Ａの場合は、金貨Ｂの重さは110ｇ
  • ３つの袋が金貨Ｂで１つが金貨Ａの場合は、金貨Ｂの重さは320/3ｇ
  • 袋２〜袋５の４つの袋すべてが金貨Ｂであるなら、金貨Ｂの重さは105ｇ
などというように複雑になる。【計量３】ですべての組合せに一対一に対応した数値が出てくればよいのだが、実際には、
  • 袋２〜袋５がすべて金貨Ｂであった場合は、105ｇ×14枚＝1470ｇ
  • 袋３と袋４だけが金貨Ｂであった場合は、金貨Ｂは110ｇ、7枚なので合計770ｇ、また袋２と袋５からは100ｇの金貨Ａを合計7枚取り出しているので700ｇ、よって合計1470ｇ
となって、見分けがつかなくなる。

　これを避けるには、【計量３】において、「袋の番号ｎと同じ数だけ取り出す」かわりに、「袋の番号ｎに対応して２n-1個取り出す」という方法が考えられる。要するに、各袋に二進数で、1、10、100、1000、．．．という番号をふり、その番号に対応した個数（二進数表記）を取り出すというやり方であり、計量結果から自動的に、二進数表記の「1」と「0」に、金貨Ａと金貨Ｂの袋を対応させることが可能になるはず【但し未検証】。



　最後に元の問題をさらに拡張し、
外見は見分けがつかないが重さの異なる金貨Ａと金貨Ｂと金貨Ｃがあります。そのいずれかを入れた袋がｎ個あります。袋の数はいくら多くてもよろしい。それぞれの袋に複数の金貨が入っているが、いずれも金貨Ａのみ、金貨Ｂ、または金貨Ｃのみであって、混ざって入っている袋は１つもない。できるだけ少ない回数の計量ですべての袋を、金貨Ａ、金貨Ｂ、金貨Ｃの袋に分けるにはどうすればよいか？
というように３種類、さらにはｍ種類の金貨がある場合を考えてみたが、頭が働かなくなった。ひょっとして完全数の問題にも関連するのかという気もするがよくワカラン。

　ちなみに上記は不可能問題ではない。ｎ個の袋があるなら、順番に１個ずつ金貨を取り出して計量すれば、最大ｎ回で事足りることは分かっている（金貨の種類が何種類あろうともｎ回で十分）。

　次回に続く。