問題：1枚だけ重さの違うコインがあるとする．
(1) 全部でコインが4枚あるとして，天秤を2回使って重さの違うコインは見つけられるか．
(2)全部でコインが12枚あるとして，天秤を3回使って重さの違うコインは見つけられるか．
(3)一般化して全部でコインが(3n-1)/2枚(n>=2)あるとして，天秤をn回使って重さの違うコインは見つけられるか．
この問題の最も難しいところは重さがちがうということしか分かっていない、つまり重いのか軽いのかは分からないという所です。軽重が分かればコインが3n枚あっても簡単に出来てしまいます。
いろいろ試しても出来なかったので、これは出来ないのではないかと疑い始めたことが解答のきっかけとなりました。
1回コインを天秤にかけたあとに得られる結果は、右に傾く・左に傾く・釣り合うの3通りです。天秤をn回使った結果は3n通り考えられることになります。一方考えられる可能性はそれぞれのコインが重いか軽いかで2x(3n-1)/2=3n-1通りということになり、天秤を使った結果から得られる情報でカバーできそうに思えます。
各コインに対して3進数でn桁の番号(00...00から22...22=3n-1まで)を2つずつ割り当てる。
1枚のコインに割り当てる数字とは00...00から11...11までの数字から1つと、 その数字の各位の0と2を入れ替えた数字すなわち 22...22(3)-x である。 1つだけ使用されない数字の組が出る。
2つの数字のうち1つを採用する。
あとは、各コインを、採用された数字の上からa桁目の数字が0,1,2ならそれぞれ、a回目に「天秤の左の皿に載せる」・「天秤に載せない」・「天秤の右の皿に載せる」ようにする。
天秤がa回目に「左に傾く」・「釣り合う」・「右に傾く」ことを 上からa桁目の数字がそれぞれ0,1,2の値を取ることで示すようにして、 出た結果を3進数になおし、その数字と同じ数字が割り当てられているコインが重さの違うコインである。
ちなみに、このときの結果が割り当てた数字のうち採用された方の数字ならそのコインは他のコインよりも重く、そうでなければ軽い。ただし、11....11が割り当てられたコインについては重さが違うということがわかるのみで、軽重を知ることは出来ない。(天秤に載せることがないので当然といえば当然である。)
あとは、天秤の両側に同じ数のコインをのせることができることを示せばよい。
ある整数n(>=2)について以下の条件を満たすように、(3n-1)/2個のn桁の3進数(00...00から22...22まで)の組を作ることが出来る。
n=2のとき、(1)の解答に立ち返ってみると、 4つのコインに割り当てられる数字はそれぞれ 00 21 12 11 で 02 20 が使われない数字であるとすれば、成立する。
n=mのとき可能であるとすると、 n=m+1のとき、 n=mのときに使われているものの末尾に0,1,2を付け足したものを使用することにする。 できあがった数字は最初のm桁が相異なるので、相異なる。 また、22..222-xb(:xの末尾に0,1,2を付け足したもの。ただしxは11...11ではない。)はn=mのときに22..22-xが使われていなかったので含まれていない。
ただし、 11..110=22...222-11..112なので、 11...11には1以外には0か2かのどちらか一方しか付け足せない。 ここでは0を付け足す。
そうすると0と2の数が合わなくなるので、 使われなかった数字組の一方に対して末尾に1を付け足したものと、 その数字を22...22から引いたものの末尾に2を付け足したもの (0を付け足したものを22...222から引いたものでもある)を使い、 末尾に2を付け足したものを使わない数字とする。
これでn=m+1のときも条件を満たすように数字の組を作ることことが出来、 すべてのn(>=2,nは整数)において成り立つことが示された。