贋金の問題１

 　第２次世界大戦も終りに近づいた1945年、アメリカの数学雑誌『American Mathematical Monthly』に次のような問題が載った。出題者はバージニア州アーリントンのE.D.Schell（シェル）という人である。曰く、「同種のコイン８枚と天秤が１台ある。コインのうち１枚は贋金で、他のものよりも目方が軽い。天秤を２回使うだけで、贋金の存在を確認し、それをみつけだすことができるだろうか？」
　普通のやり方だと、天秤の左右のさらに４枚ずつを載せて重さを較べ、軽い方を２枚ずつに分けて、再度主さを較べる。そして、最後にその軽いほうの２枚の重さを比較して、軽いほうを贋金とする。しかし、このやり方だと３回量る必要がある。それを２回で済ますにはどうしたらよいだろうか。
　この問題は大きな反響を呼び起こし、解答が続々と編集部宛に寄せられ、その解答は８～９月号に発表されたという。皆さん方は、ここで１度このブログを読むのをやめて、しばらく自分で考えて戴きたいものだ。
 
　正解は左図で示すようになる。４枚ずつ測らずに、　（枚数＋１）÷３、つまり３枚ずつ測るのが妙手である。このようにすると、Ｎ枚のコインがあって、Ｎが　３ｎ―１≦ Ｎ ＜ ３ｎ 　である場合は、ｎ回の測定で贋金を見つけだすことができる。ただし、にせがねが混ざっていることが確実で、その確認をする必要がなければ、Ｎが　３ⁿ⁻¹ ＜ Ｎ ≦ ３ⁿ 　のときにｎ回の測定で贋金を指摘することが可能なのである。
　このコイン８枚から１枚の軽いものを選別するのに、次のような機械的方法でも選別することが出来る。８枚のコインにそれぞれ１～８まで番号をつけ、
（Ⅰ）（１、２、３）――（４、５、６）
（Ⅱ）（１、４、７）――（２、５、８）
の２回の試行をおこなう。右側が軽い時はＬ（Light）、左右が釣り合った時はＳ（Same）、右側が重い時はＨ（heavy）で表わすことにすると、
　試行結果　ＬＬ　ＬＨ　ＬＳ　ＨＬ　ＨＨ　ＨＳ　ＳＬ　ＳＨ
　贋　　　金　　１　　２　　３　　４　　５　　６　　７　　８
のように出来る。