1999年03月15日
まあ基本だけどねふふふん
「じぶん更新日記」の偽金貨検出問題を読んで、Santa Rosa に来てすぐの頃を懐かしく思い出してしまった。会社の同僚数人との食事中、まさにその問題が話題に出たのだ。
「１２枚のコインがある。この内１枚だけ重さの違う偽物が混ざっている。それが他のコインより重いか軽いかは分からない。天秤を３回だけ使って、どのコインが偽物か、それは重いか軽いかを当てるにはどうしたら良いか」
エンジニアは、基本的に頭脳労働者だ。それはつまり、ある程度は「こいつは頭がいい」と思ってもらわないことには同僚として尊重されない。いや、少なくとも「こいつは馬鹿ではないな」と思ってもらう必要がある。
では、その頃僕はどう思われていたか。まず、日本から来たらしい。若いので、経験はそんなに無さそうだ。話をすると、たどたどしい英語をひどいアクセントで、つっかえながら、自信無さそうに話す。時々何を言っているのかさえ分からない。つまり、普通はこんな人を「頭がいい」と思うのは非常に難しい。
そんな時に出てきたのが、この問題だった。その問題を解いて見せ、更に「３回天秤を使うことで何枚まで判別できるか？」の問題の考え方について説明した。それでいきなりすべてが変わったわけではないが、以前より技術的な討論をする機会が多くなった。そして数学的パズルが有効だと分かった僕は、その後もいろんな人にパズルを出題し、出されたものを解いて見せ、信頼を勝ち得た(?)のだ。
↓パズルの細かい内容に興味ない人はここで投票ボタンを押して下さい。有難うございます。
どうやって、何枚まで判別できるかを知るのか。
天秤を１回使うとき、予想される結果は３通りある。
1.右が下がる 2.左が下がる 3.釣り合う
つまり、もともとあった可能な答の数を、１回の試行で(ベストケースで)３分の１まで減らすことが出来る。たとえば２枚のコインＡ、Ｂがあった時、可能な答は３つある。
1.Ａが重い 2.Ｂが重い 3.同じ重さ
これを１回の試行で、１つに絞りこむことが出来る。
では２回の試行ではどうなるか。それぞれの試行には３通りの結果があり、そのコンビネーションになるので、３×３で９分の１まで絞りこめる。つまり、最大で９通りの答のバリエーションがある問題まで解くことが出来る。たとえば「９枚のコインがあり、そのうち１枚だけが他のものより重い。天秤を２回使って...」といった問題が成立する。その問題の答として考えられるのは、９枚のコインをそれぞれＡ,Ｂ,...,Ｉとすると、 「コインＡが重い」「コインＢが重い」…「コインＩが重い」の９通りなのである。これよりコインの枚数が多くなると、２回では絶対に不可能なのだ。
３回では、３×３×３で２７通りである。最初の問題である「コインが１２枚で、偽物が他より重いか軽いか分からない」で可能な答えは、「コインＡが軽い」「コインＡが重い」「コインＢが軽い」「コインＢが重い」…「コインＬが軽い」「コインＬが重い」で、１２×２の２４通りしかない、解けそうである。実際解ける。
しかし、この考え方だと、コインが１３枚でも解けそうである。１３×２＝２６で、２７より小さい。が、これは不可能なのだ。
まず、１回目の試行を考えてみよう。両方の皿に４枚ずつ(右の皿にＡＢＣＤ、左の皿にＥＦＧＨ)乗せてみる。
この時に天秤が傾けば、問題はない。たとえば右の皿が傾いたなら、可能な答は「ＡＢＣＤのどれかが重い」「ＥＦＧＨのどれかが軽い」の８通りで、次の試行で３通り、次で１通りに絞りこむことが出来る。ところが釣り合った場合、残ったコインは５枚あり、可能な答は「ＩＪＫＬＭのどれかが重い」「ＩＪＫＬＭのどれかが軽い」の１０通りになってしまう。これを２回の試行で絞り込むのは不可能である。それでは、と最初に皿に乗せる枚数を変えても、どれかのケースで必ず１０通り以上の答が残ってしまう。
問題の設定によって、きれいに１回の試行で３分の１まで絞りこめることもあれば絞りこめないこともある。この問題の場合、それぞれのコインが３通りの可能解(重い／軽い／他と同じ重さ)を持っており、天秤の上に乗せる時にそれが不可分である(重い可能性だけがあるコインと軽い可能性だけがあるコインに分けられない)ところが問題を複雑にしている。
たとえば「２７枚のコインがあり、どれか１枚が必ず重い」とか長谷川さんの最後の問題の「２６枚のコインがあり、すべて同じ重さかどれか１枚だけが重い」などの問題は、答が２７通り予想され、きれいに
２７通り→９通り→３通り→１通り
と３分の１ずつ減らすことが出来る例である。
Trackback on "まあ基本だけどねふふふん"
このエントリーのトラックバックURL:
"まあ基本だけどねふふふん"へのトラックバックはまだありません。
"まあ基本だけどねふふふん"へのコメントはまだありません。