中学数学をなめてはいけないなぁ・・・

質問

12個のおもりがあって、そのうち１つだけ重さの違うおもりがまぎれています。
それを、てんびんを３回だけ使って見分ける方法を教えてください。
ただし、重さの違うおもりは他のおもりより重いか軽いかわかりません。
わかった方は至急おしえてください。おねがいします。

回答No.30

stomachman

天秤問題。stomachmanの証明はあっちこっち枝葉が錯綜してる上に小さい誤りやミスタイプが結構多いので、訂正し不要な部分を削り不足を補い表現を整えてみました。（まだミスタイプあるかもしれませんが…）一部の定理は順番を入れ替えてもいます。そうしたら、詰まらない教科書風になっちゃいました。逆にいえば、一見詰まらない教科書の記載の背後には、実はてんやわんやの思索・試行があったのかも、ってことでしょうね。

標準問題：
M個のおもりが与えられ、その中に丁度１個だけ他のおもりとは重さが異なる（異常である）ものがある。異常なおもりを天秤を使って特定する。このとき、高々N回天秤を使って判定できるようなMの範囲、および判定の手順を求む。
（与えられたM個以外の、正常とわかっているおもりを幾つか借りてくる、ということは許さない。）

なお「N回の測定で判定する」とは、どのおもりが異常であるかを天秤をN回使って特定することを指します。また、「重いもの」とは、正常なおもりよりも重い異常なおもりのことであり、「軽いもの」とは、正常なおもりよりも軽い異常なおもりのことであり、「異常なもの」とは、異常なおもりのことです。
また(3^N+c)という表記は((3^N)+c)すなわち「3をN乗したものに、cを加える」を意味し、(3^(N+c))ではありません。

●定理１
(1)正常と分かっているおもりがなくても、「この中に軽いものが１個ある」と分かっているおもり3^N個（この集合をLとする）をN回の測定で判定できる。
(2)正常と分かっているおもりがなくても、「この中に重いものが１個ある」と分かっているおもり3^N個（この集合をLとする）をN回の測定で判定できる。
●証明：
(1)を証明する。
★N=0の場合
「この中に軽いものが１個ある」と分かっているおもりが3^N=１個だけ与えられたのだから、そのおもりが軽いと分かる。従って0回の測定で判定できる。
★N≧1の場合
左右の皿に3^(N-1)個ずつ乗せ、残り3^(N-1)個は乗せない。
☆もし天秤が釣り合えば、
「天秤に乗せなかったおもり3^(N-1)個の中に軽いものが１個ある」と分かったから、定理１を適用できる。
☆もし天秤が傾けば、
「軽かった側の皿に乗せたおもり3^(N-1)個の中に軽いものが１個ある」と分かったから、定理１を適用できる。
いずれにせよ、あとN-1回の測定で判定できる。 ゆえに都合N回の測定で判定できる。
(2)の証明は(1)の証明と同様であり、自明。
（証明終わり)

●定理２
(1) N≧1であって、正常と分かっているおもりが少なくとも(3^(N-1)-1)個あるとき、「この中に重いものはない」と分かっているおもり(3^N+1)/2個（この集合をLとする）と、「この中に軽いものはない」と分かっているおもり(3^N-1)/2個（この集合をHとする）があって、これらのうちに異常なものが１個あると分かっている場合、N回の測定で判定できる。
(2) N≧1であって、正常と分かっているおもりが少なくとも(3^(N-1)-1)個あるとき、「この中に軽いものはない」と分かっているおもり(3^N+1)/2個（この集合をLとする）と、「この中に重いものはない」と分かっているおもり(3^N-1)/2個（この集合をHとする）があって、これらのうちに異常なものが１個あると分かっている場合、N回の測定で判定できる。
●証明：
(1)を証明する。
★N=1の場合
Lは2個、Hは1個、正常と分かっているおもりは0個である。Lのおもりを左右の皿にひとつづつ乗せる。
☆もし天秤が傾けば、皿が上がった方のおもりが軽いと分かる。
☆もし釣り合えばHのおもりが重いと分かる。
ゆえに１回の測定で判定できる。
★N≧2の場合
Lを3^(N-1)個（Laとする）と(3^(N-1)+1)/2個（Lbとする）に分け、
Hを3^(N-1)個（Haとする）と(3^(N-1)-1)/2個（Hbとする）に分けることができる。
左の皿にHbとLaを乗せ、右の皿にLbと正常と分かっているおもり(3^(N-1)-1)個を乗せることができる。
☆もし左が下がれば、
正常と分かっているおもりは少なくとも(3^(N-1)-1)個ある。(3^(N-1)-1)＞(3^(N-2)-1)である。
「(N-1)≧1であり、正常と分かっているおもりが少なくとも(3^(N-2)-1)個あり、Hb（(3^(N-1)-1)/2個）の中に軽いものはなく、Lb（(3^(N-1)+1)/2）の中に重いものはなく、これらの内に異常なものが１個ある」ことが分かったので、定理２を適用できる。
☆もし右が下がれば、
「La（3^(N-1)個）の中に軽いものがある」ことが分かったので、定理１を適用できる。
☆もし釣り合えば、
「Ha（3^(N-1)個）の中に重いものがある」ことが分かったので、定理１を適用できる。
いずれにせよあとN-1回の測定で判定できる。ゆえに都合N回の測定で判定できる。
(2)の証明は(1)の証明と同様であり、自明。
（証明終わり）

●定理３
N≧1であって、正常と分かっているおもりが少なくとも3^(N-1)個あるとき、「この中に重いものはない」と分かっているおもり(3^N-1)/2個（この集合をLとする）と、「この中に軽いものはない」と分かっているおもり(3^N-1)/2個（この集合をHとする）があって、しかもLかHの中に異常なものが１個あると分かっている場合、N回の測定で判定できる。
●証明：
★N=1の場合
L、Hは共に１個であり、正常と分かっているおもりが1個ある。左の皿にLを、右の皿に正常なおもり１個を乗せる。
☆天秤が釣り合えばHが重く、
☆天秤が傾けばLが軽い。
ゆえに１回の測定で判定できる。
★N≧2の場合
Lを3^(N-1)個（Laとする）と(3^(N-1)-1)/2個（Lbとする）に分け、
Hを3^(N-1)個（Haとする）と(3^(N-1)-1)/2個（Hbとする）に分けることができる。
左の皿にHbとLaを乗せ、右の皿に正常と分かっているおもり3^(N-1)個とLbを乗せる。
☆もし左が下がれば、
「(N-1)≧1であって、正常と分かっているおもりが少なくとも3^(N-2)個あり、Hb（(3^(N-1)-1)/2個）の中に軽いものはなく、Lb（(3^(N-1)-1)/2個）の中に重いものはなく、これらの内に異常なものが１個ある」と分かったので、定理３を適用できる。
☆もし右が下がれば、
「La（3^(N-1)個）の中に軽いものがある」と分かったので、定理１を適用できる。
☆もし釣り合えば、
「Ha（3^(N-1)個）の中に重いものがある」と分かったので、定理１を適用できる。
いずれにせよ、あとN-1回の測定で判定できる。ゆえに都合N回の測定で判定できる。
（証明終わり）

●定理４
N≧1であって、正常と分かっているおもりが少なくとも１個あるとき、「この中に異常なものが１個ある」と分かっているおもり(3^N+1)/2個（この集合をXとする）は、N回の測定で判定できる。
●証明：
★N=1の場合
Xのおもりは２個である。その内の１個を左の皿、正常と分かっているおもり１個を右の皿に乗せる。
☆もし天秤が釣り合えば、乗せなかったものが異常だと分かる。
☆もし天秤が傾けば、乗せたものが異常だと分かる。
ゆえに１回の測定で判定できる。
★N≧2の場合
Xを(3^(N-1)+1)/2個（Xaとする）、(3^(N-1)-1)/2個（Xbとする）、(3^(N-1)+1)/2個（Xcとする）に分けることができる。
Xaを左の皿に、正常と分かっているおもり１個とXbを右の皿に乗せる。
☆もし天秤が釣り合えば
「(N-1)≧1であって、正常だと分かっているおもりが少なくとも１個あり、Xc（(3^(N-1)+1)/2個）の中に異常なものが１個ある」と分かったのだから定理４を適用できる。
☆もし天秤が傾けば
Xcの(3^(N-1)+1)/2個は正常だと分かるから、初めに与えられたものと合わせて、正常と分かっているおもりは少なくとも(3^(N-1)+1)/2+1個ある。そして(3^(N-1)+1)/2+1＞3^(N-2)-1である。
・もし左が下がったのであれば
「(N-1)≧1であって、正常だと分かっているおもりが少なくとも(3^(N-2)-1)個あり、Xa（(3^(N-1)+1)/2個）の中に軽いものはなく、Xb（(3^(N-1)-1)/2個）の中に重いものはなく、どちらかに異常なものが１個ある」と分かったのだから定理２を適用できる。
・もし右が下がったのであれば
「(N-1)≧1であって、正常だと分かっているおもりが少なくとも(3^(N-2)-1)個あり、Xa（(3^(N-1)+1)/2個）の中に重いものはなく、Xb（(3^(N-1)-1)/2個）の中に軽いものはなく、どちらかに異常なものが１個ある」と分かったのだから定理２を適用できる。
いずれにせよ、あとN-1回の測定で判定できる。ゆえに都合N回の測定で判定できる。
（証明終わり）

●系４－１
N≧1のとき、
1≦M≦(3^N+1)/2であり、正常と分かっているおもりが少なくとも(3^N-1)/2個あるとき、高々N回の測定で「この中に異常なものが１個ある」と分かっているおもりM個を判定できる。
●証明
★M=1の場合
測定をしなくても、そのおもりが異常であることがわかる。
★M≧2の場合
(3^N+1)/2≧M≧2より、0≦(3^N+1)/2-M＜(3^N-1)/2である。
ゆえに、「この中に異常なものが１個ある」と分かっているおもりM個に、正常と分かっているおもり(3^N+1)/2-M個を加えて丁度(3^N+1)/2個にすることができる。すると正常と分かっているおもりがまだ少なくとも１個余る。
すなわち「N≧1であって、正常と分かっているおもりが少なくとも１個あり、「この中に異常なものが１個ある」と分かっているおもり(3^N+1)/2個がある」のだから定理４を適用でき、N回の測定で判定できる。
（証明終わり）

●定理５（標準問題の判定手順～その１）
N≧1のとき、正常と分かっているおもりがなくても、「この中に異常なものが１個ある」と分かっているおもり(3^N-1)/2個（この集合をXとする）は、N回の測定で判定できる。
●証明：
★N=1の場合
Xは(3^N-1)/2=１個のおもりからなる。測定をしなくても、そのおもりが異常であることがわかる。ゆえに高々1回の測定で判定できる。
★N≧2の場合
Xを(3^(N-1)-1)/2個（Xaとする）、(3^(N-1)-1)/2個（Xbとする）、(3^(N-1)+1)/2個（Xcとする）に分けることができる。Xaを左の皿に、Xbを右の皿に乗せる。
☆もし天秤が釣り合えば
XaとXb合わせて(3^(N-1)-1)個が正常だと分かる。N≧2より(3^(N-1)-1)＞1である。
「(N-1)≧1であり、正常と分かっているおもりが少なくとも１個あり、Xc（(3^(N-1)+1)/2個）の中に異常なものが１個ある」と分かったのだから、定理４を適用できる。
☆もし天秤が傾けば
Xcの(3^(N-1)+1)/2個が正常だと分かる。(3^(N-1)+1)/2＞3^(N-2)である。
「(N-1)≧1であり、正常と分かっているおもりが少なくとも3^(N-2)個あり、下がった皿に乗せたもの(3^(N-1)-1)/2個の中に軽いものはなく、上がった皿に乗せたもの(3^(N-1)-1)/2個の中に重いものはなく、どちらかに異常なものが１個ある」と分かったのだから、定理３を適用できる。
いずれにせよ、あとN-1回の測定で判定できる。ゆえに都合N回の測定で判定できる。
（証明終わり）

●定理６
「この中に異常なものが１個ある」と分かっているM個のおもりをN回の測定で判定できるならば、
M≦(3^N+1)/2
である。
●証明：
　「この中に異常なものが１個ある」と分かっているM個のおもりをN回の測定で判定できる手順について考える。
　天秤を１回使うたびに、右の皿が下がるか、左の皿が下がるか、釣り合うか、の３通りの測定結果が生じるのだから、天秤をN回使った時に生じうる測定結果の組み合わせは全部で3^N通りある。
　うち１通りはN回の測定ですべて天秤が釣り合った場合である。このときには異常なおもりが正常より重いものなのか軽いものなのかを判定できない。
　残りの(3^N-1)通りについては、少なくとも一度は天秤が傾く。N回の測定の結果異常なおもりが１個特定され、また、その測定の途中で天秤が少なくとも一度は傾いたとする。すると天秤が傾いたのはその異常なおもりが天秤（のどちらかの皿）に乗っていたからである。ゆえに、異常であると分かったおもりが、天秤が傾いた測定（少なくとも１度ある）の際にどっちの皿に乗っていたのかを（N回の測定が終わったあとで）調べれば、その異常なおもりが正常なおもりに比べて重いのか軽いのかまで（嫌でも）分かる。
　ゆえに、測定結果の組み合わせのうち天秤が一度でも傾くもの(3^N-1)通りについては、必然的に異常なおもりが正常より重いのか軽いのかが判定される。
　つまり、この手順がM個のおもりを判定できるとすると、この手順は少なくとも(2(M-1)+1)通りの判定結果が出せなくてはならない。従って、
2(M-1)+1≦3^N
でなくてはならない。すなわち、N回の測定で判定できるおもりの個数は高々(3^N+1)/2個である。
またこれが、「手順の１回目の測定をする際に、正常と分かっているおもりを利用できるかどうか」とは関わりなく成り立つことは、以上の議論から明らかである。
（証明終わり）

●補題１
N回の測定でM個のおもりを判定できる任意の手順において、１回目の測定で天秤に掛けないおもりの個数は高々(3^(N-1)+1)/2個である。
●証明：
　N回の測定でM個のおもりを判定できる手順であって、しかも１回目の測定で天秤に掛けなかったおもりがR個であり、R＞(3^(N-1)+1)/2であるような手順が存在すると仮定する。
　この手順において１回目の測定で天秤が釣り合った場合、天秤に掛けなかったおもりR個の中に異常なものが１個あると分かる。ところが、定理６により（正常と分かっているおもりが幾つあろうとも）(N-1)回の測定で判定できるおもりの個数は高々(3^(N-1)+1)/2である。R＞(3^(N-1)+1)/2だから、この手順ではN回の測定でM個のおもりを判定できない。これは矛盾であり、ゆえに最初の仮定は誤りである。
（証明終わり）

●補題２
正常と分かっているおもりがないとき、「この中に異常なおもりが１個ある」と分かっている２個のおもりを判定できる手順は存在しない。
●証明：
　測定を行わなければどちらのおもりが異常か分からないので、測定を行う必要がある。
　正常と分かっているおもりはないのだから、測定を行うためには、左右の皿にそれぞれ１個づつおもりを乗せる以外の測り方はない。このとき
☆天秤が傾けば、「上がった皿に乗っているおもりが軽いか、下がった皿に乗っているおもりが重い」ことが分かるが、そのどちらであるかは分からないので、判定できない。
☆天秤が釣り合うことはない。
　ゆえに、正常と分かっているおもりなしで2個のおもりを判定できる手順は存在しない。
（証明終わり）

●定理７
N≧1であって、正常と分かっているおもりがないとき、「この中に異常なおもりが１個ある」と分かっている(3^N+1)/2個のおもりを、N回の測定で判定できる手順は存在しない。
●証明：
★N=1の場合
N=1より、(3^N+1)/2=2である。補題２により、２個のおもりを判定できる手順は存在しない。
★N≧2の場合
仮定１：「正常と分かっているおもりなしに、「この中に異常なおもりが１個ある」と分かっているM=(3^N+1)/2個のおもりをN回の測定で判定できる手順Ｐが存在する」と仮定する。
　手順Ｐにおいては、補題１より、１回目の測定で天秤に乗せないおもりの数Qは(3^(N-1)+1)/2個以下である。すなわち
Q≦(3^(N-1)+1)/2
である。左の皿に乗せるおもりの数をWとすると、右の皿にも同じW個のおもりを乗せるから、
W=(M-Q)/2
である。そしてQ≦(3^(N-1)+1)/2であるから、
W≧(3^(N-1))/2
である。ところが右辺は整数にならないので、Wは「(3^(N-1))/2より大きい最小の整数」以上である。すなわち
W≧(3^(N-1)+1)/2
である。すると手順Ｐの１回目の測定で天秤にかけるおもりの個数は
2W ≧(3^(N-1)+1)
であり、従って、１回目の測定で天秤に掛けないおもりの数Qは
Q≦(3^(N-1)-1)/2
であることが分かる。
　さて、手順Ｐを１回目の測定についてだけ変更した手順Ｐ’を以下のように構成する。
　判定の対象となるおもりを１個追加して(M+1)個に増やし、手順Ｐ’の１回目の測定ではこの追加のおもりは天秤に乗せないものとする。すると１回目の測定で天秤に乗せないおもりの数はQ+1個であり、１回目の測定で天秤に乗せるおもりの個数は手順Ｐと同じ2Wである。
手順Ｐ’では、１回目の測定の結果、
・もし天秤が釣り合ったら
天秤に乗せなかったQ+1個のおもりについて系４－１を適用する。
・もし天秤が傾いたら
追加した１個のおもりを取り除け、残りのM個について「手順Ｐの１回目の測定を行ったところ、天秤が傾いた」という状態が発生したものと見なして、手順Ｐを継続する。

　すると手順Ｐ’によって、N回の測定でM+1=(3^N+3)/2個のおもりが判定できる。なぜならば、手順Ｐ’の１回目の測定において、
☆もし天秤が釣り合ったら
天秤に乗せなかったQ+1個（Q+1≦(3^(N-1)+1)/2）のおもりの中に異常なものがあり、また正常とわかったおもりが2W個（2W≧(3^(N-1)+1)≧1）ある。従って、
「N≧2であり、正常と分かっているおもりが少なくともK個（K≧(3^(N-1)+3)/2）あり、(3^(N-1)+1)/2≧Q+1＞0であり、Q+1個のおもりの中に異常なものが１個ある」と分かるから、系４－１が適用でき、高々(N-1)回の測定で判定できる。つまり、都合N回の測定で判定できる。
☆もし天秤が傾いたら
天秤に乗せなかった(3^(N-1)+1)/2個のおもりは全部正常だとわかるから、追加した１個のおもりもまた正常である。従ってこのおもりを取り除けて、判定手順Ｐをそのまま続ければ都合N回で判定できる。

　以上のように、「この中に異常なものが１個ある」と分かっている(3^N+3)/2個のおもりをN回の測定で判定できる手順Ｐ’が構成できた。
　ところが、定理６によればN回の測定で判定できるおもりの個数は高々(3^N+1)/2であるから、手順Ｐ’は存在しえない。これは矛盾である。
　ゆえに仮定１は誤りである。すなわち、
N回の測定で(3^N+1)/2個のおもりを判定できる手順は存在しない。
（証明終わり）

●系７－１
N≧1のとき、「正常と分かっているおもりがなくても「この中に１個異常なものがある」と分かっているおもりをN回の測定で判定できる」ようなおもりの個数は高々(3^N-1)/2個である。
●証明
定理６により、「この中に１個異常なものがある」と分かっているおもりをN回の測定で判定できるようなおもりの個数は高々(3^N+1)/2個である。また定理７により、N≧1のとき、正常と分かっているおもりなしに、「この中に１個異常なものがある」と分かっている(3^N+1)/2個のおもりをN回の測定で判定できるような手順は存在しない。
（証明終わり）

●定理８
N≧1で、正常と分かっているおもりが少なくともq=(3^N-1)/2個あって、
(3^N-1)/2≧A＞0のとき、
「この中に重いものはない」と分かっているおもりA個（この集合をLとする）と、
「この中に軽いものはない」と分かっているおもりA個（この集合をHとする）があって、これらの中に異常なものが１個あると分かっている場合、高々N回の測定で判定できる。
●証明：
★[1]N=1の場合、
正常と分かっているおもりが少なくともq=1個あって、A=1である。
右の皿に正常なおもり１個、左の皿にHのおもり1個を乗せる。
☆もし天秤が釣り合えば、Lのおもりが軽い。
☆もし天秤が傾けば、Hのおもりが重い。
こうして１回の測定で判定できる。

★[2]N≧2の場合、
さらに以下のように場合分けする：
(1) (3^N+1)/4≧A＞0のとき、
(2) 3^(N-1)≧A＞(3^N+1)/4のとき、
(3) (3^N-1)/2≧A＞3^(N-1)のとき。

☆(1) (3^N+1)/4≧A＞0のとき
LとHを合わせたおもりの個数をMとすると、M=2Aだから、
(3^N+1)/2≧M≧1
を満たす。すなわち、「N≧1であり、1≦M≦(3^N+1)/2であり、正常と分かっているおもりが少なくとも(3^N-1)/2個あり、M個のおもりの中に異常なものが１個あると分かっている」ので、系４－１が適用でき、高々N回の測定で判定できる。

☆(2) 3^(N-1)≧A＞(3^N+1)/4のとき、
N≧2より、A＞(3^N+1)/4＞(3^(N-1)+1)/2
である。だから、
Lをr=(3^(N-1)+1)/2個（La）と、p=A-r個（Lb）に分け、
Hをr=(3^(N-1)+1)/2個（Ha）と、p=A-r個（Hb）に分けることができる。
3^(N-1)≧A＞(3^N+1)/4であるから、(3^(N-1)-1)/2≧p＞0である。
さて、正常と分かっているおもりは少なくともq=(3^N-1)/2個あり、q＞rである。よって、左の皿にHbとLa（合わせてA個）を乗せ、右の皿にLbと正常と分かっているおもりr個（合わせてA個）を乗せることができる。
なお、N≧2より、q=(3^N-1)/2＞(3^(N-1)-1)/2≧1である。
・もし左が下がれば、
「(N-1)≧1で、正常と分かっているおもりが少なくとも(3^(N-1)-1)/2個あって、(3^(N-1)-1)/2≧p＞0で、Hb（p個）の中に軽いものはなく、Lb（p個）の中に重いものはなく、これらの内に異常なものが１個ある」と分かったので、定理８を適用でき、高々(N-1)回の計測で判定できる。
・もし右が下がれば、
「Laの中に軽いものがある」と分かる。つまり、「(N-1)≧1であり、正常と分かっているおもりが少なくとも１個あり、La（(3^(N-1)+1)/2）個の中に異常なものが１個ある」と分かるので、定理４を適用でき、高々(N-1)回の計測で判定できる。
・もし釣り合えば、
「Haの中に重いものがある」と分かる。つまり、「(N-1)≧1であり、正常と分かっているおもりが少なくとも１個あり、Ha（(3^(N-1)+1)/2）個の中に異常なものが１個ある」と分かるので、定理４を適用でき、高々(N-1)回の計測で判定できる。
以上から、いずれにせよ都合高々N回の計測で判定できる。

☆(3) (3^N-1)/2≧A＞3^(N-1)のとき、
Lをr=3^(N-1)個（La）と、p=A-r（Lb）に分け、
Hをr=3^(N-1)個（Ha）と、p=A-r個（Hb）に分けることができる。
(3^(N-1)-1)/2≧p＞0
である。また、
q=(3^N-1)/2≧(3^(N-1)-1)/2
である。
従って、左の皿にHbとLa（合わせてA個）を乗せ、右の皿にLbと正常と分かっているおもりp個を乗せることができる。
・もし左が下がれば、
「(N-1)≧1であり、正常と分かっているおもりが少なくとも(3^(N-1)-1)/2個あり、(3^(N-1)-1)/2≧p＞0であり、Hb（p個）の中に軽いものはなく、Lb（p個）の中に重いものはなく、これらの内に異常なものが１個ある」と分かるので、定理８を適用でき、高々(N-1)回の測定で判定できる。
・もし右が下がれば、
「La（3^(N-1)個）の中に軽いものがある」と分かるから、定理１を適用でき、高々(N-1)回の測定で判定できる。
・もし釣り合えば、
「Ha（3^(N-1)個）の中に重いものがある」と分かるから、定理１を適用でき、高々(N-1)回の測定で判定できる。
従って、いずれにせよ都合高々N回の測定で判定できる。
（証明終わり）

●定理９（標準問題の判定手順～その２）
N≧2であり、(3^N-1)/2＞M＞(3^(N-1)-1)/2、M≠2であるとき、正常と分かっているおもりがなくても、「この中に異常なものが１個ある」と分かっているM個のおもりを高々N回の測定で判定できる。
●証明：
★[1] N=2の場合
4＞M＞1, M≠2であるからM=3である。
おもりにa, b, cと名前をつける。天秤の右の皿にa、左の皿にbを乗せる。
☆天秤が釣り合った場合、
　cが異常であると分かる。
☆右が下がった場合、
cは正常であり、aは軽いものではなく、bは重いものではないと分かる。
　天秤の右の皿にa、左の皿にcを乗せる。
　・天秤が釣り合った場合、bが軽いと分かる。
　・天秤が傾いた場合、aが重いと分かる。
☆左が下がった場合、
cは正常であり、bは軽いものではなく、aは重いものではないと分かる。
　天秤の右の皿にb、左の皿にcを乗せる。
　・天秤が釣り合った場合、aが軽いと分かる。
　・天秤が傾いた場合、bが重いと分かる。
こうして、高々２回の測定で判定できる。

★[2] N≧3の場合
☆M=(3^(N-1)+1)/2の場合
左右の皿に１個ずつおもりを乗せる。
・天秤が傾いた場合、
上がった皿に乗せた１個は重いものではなく、下がった皿に乗せた１個は軽いものではなく、これら２個の中に異常なものが１個あり、残り(3^(N-1)-3)/2個は正常なおもりであることが分かった。
N≧3より、(3^(N-1)-3)/2≧3であるから、正常と分かっているおもりが少なくとも３個ある。ゆえに定理３が適用でき、高々１回の測定で判定できる。つまり都合高々２回の測定で判定できる。
・天秤が釣り合った場合、
天秤に掛けた２個は正常であり、天秤に掛けなかった残り(3^(N-1)-3)/2個の中に異常なものが１個あることが分かった。そこで、正常だと分かっているおもり１個を、天秤に掛けなかったおもりに加えて(3^(N-1)-1)/2個にする。すると定理５が適用でき、高々(N-1)回の測定で判定できる。
いずれにせよ、都合高々N回の測定で判定できる。
☆(3^N-1)/2＞M＞(3^(N-1)+1)/2の場合
１回目の測定で天秤に乗せないおもりの数をQとする。そして１回目の測定で左右の皿にそれぞれA個のおもりを乗せることにする。すなわちQを決めれば
A=(M-Q)/2
と決まる。
さて、(3^(N-1)+1)/2または(3^(N-1)-1)/2のどちらかは偶数で他方は奇数である。そこで
(i) Mと(3^(N-1)+1)/2が共に偶数であるか、共に奇数であるとき、
　Q=(3^(N-1)+1)/2とする。ゆえに(3^(N-1)-1)/2＞A＞0
(ii) Mと(3^(N-1)-1)/2が共に偶数であるか、共に奇数であるとき、
　Q=(3^(N-1)-1)/2とする。ゆえに(3^(N-1)-1)/2≧A＞0
このようにAとQを決定する。いずれにせよ、Q≧(3^(N-1)-1)/2、(3^(N-1)-1)/2≧A＞0となる。
そして、左右の皿にA個ずつおもりを乗せて１回目の測定を行う。
・天秤が釣り合った場合、
天秤に乗せなかったおもりQ個の中に異常なものがある。
正常と分かっているおもりが少なくとも2A個(2A＞1)ある。天秤に乗せなかったおもりQ個に対して定理４(Q=(3^(N-1)+1)/2の場合)か定理５(Q=(3^(N-1)-1)/2の場合)を適用すれば、高々(N-1)回の測定で判定できる。だから都合高々N回の測定で判定できる。
・天秤が傾いた場合、
(N-1)≧1であり、正常と分かっているおもりが少なくともq=(3^(N-1)-1)/2個ある。
さらに、(3^(N-1)-1)/2≧A＞0であって、上がった側の皿に乗っているおもりA個については「この中に重いものはない」と分かっており、下がった側の皿に乗っているおもりA個については「この中に軽いものはない」と分かっており、これらの中に異常なおもりが１個あることが分かっている。そこで定理８が適用でき、高々(N-1)回の測定で判定できる。だから都合高々N回の測定で判定できる。
（証明終わり）

●系９－１
(3^N-1)/2≧M＞2であるとき、正常と分かっているおもりがなくても、「この中に異常なものが１個ある」と分かっているM個のおもりを高々N回の測定で判定できる。
●証明：
★N≦1の場合、
(3^N-1)/2≧M＞2を満たすMは存在しない。ゆえに系９－１は真である。
★N≧2であって、M=((3^K)-1)/2 （1≦K≦N）となるKが存在する場合、
定理５によってK回の測定で判定できるから、高々N回の測定で判定できる。
★N≧2であって、M=((3^K)-1)/2 （1≦K＜N）となるKが存在しない場合、
((3^K)-1)/2＞M＞(3^(K-1)-1)/2となるKが存在し、1≦K≦Nである。またM≠2である。すなわち「K≧2であり、((3^K)-1)/2＞M＞(3^(K-1)-1)/2, M≠2であり、「この中に異常なものが１個ある」と分かっているM個のおもりがある」のだから、定理９が適用でき、高々K回の測定で判定できる。だから高々N回の測定で判定できる。
（証明終わり）

●定理１０（標準問題の最終定理）
　正常と分かっているおもりがないとき、「この中に１個異常なものがある」と分かっているM個のおもりを高々N回の測定で判定できるならば、Mは条件「(3^N-1)/2≧M＞2　または M=1」を満たす。
また、この条件を満たす任意のMについて、正常と分かっているおもりなしに「この中に１個異常なものがある」と分かっているM個のおもりを高々N回の測定で判定できる。
●証明：
[1] 「正常と分かっているおもりがなくても、「この中に１個異常なものがある」と分かっているM個のおもりをN回の測定で判定できる」ならば、Mが条件「(3^N-1)/2≧M＞2　または M=1」を満たすことを証明する。
まず、「この中に１個異常なものがある」と分かっているM個のおもりがあるのだから、M≧1である。
★N=0のとき
　定理６により、0回の測定で判定できるおもりの個数は高々1個である。ゆえに任意のMについて、
もし「正常と分かっているおもりがなくても、「この中に１個異常なものがある」と分かっているM個のおもりを0回の測定で判定できる」ならば、M=1であり、すなわち
(3^N-1)/2≧M＞2　または M=1
を満たす。
★N≧1のとき
　系７－１により、N≧1のとき、「正常と分かっているおもりがなくても「この中に１個異常なものがある」と分かっているおもりをN回の測定で判定できる」ようなおもりの個数は高々(3^N-1)/2個である。
　さらに、補題２によって、M=2の場合には（何回測定を許しても）判定は不可能である。
　従って、任意のMについて、
もし「正常と分かっているおもりがなくても、「この中に１個異常なものがある」と分かっているM個のおもりをN回の測定で判定できる」ならば、Mは
(3^N-1)/2≧M＞2 または M=1
を満たす。
[2] Mが条件「(3^N-1)/2≧M＞2　または M=1」を満たすならば「正常と分かっているおもりがなくても、「この中に１個異常なものがある」と分かっているM個のおもりをN回の測定で判定できる」ことを証明する。
　系９－１により、任意のMについて、(3^N-1)/2≧M＞2であるならば、正常と分かっているおもりがなくても高々N回の測定でM個のおもりを判定できる。
　またM=1の場合、「この中に１個異常なものがある」と分かっている１個のおもりが与えられたのであるから、0回の測定で判定が可能である。
　ゆえに、任意のMについて、
もしMが
(3^N-1)/2≧M＞2 または M=1
を満たすならば、「正常と分かっているおもりがなくても、高々N回の測定でM個のおもりを判定できる」。
（証明終わり）

●系１
天秤を最大３回使って判定できるおもりの個数は１，３，４，５，…，１３である。
●証明：最終定理より自明。
●系２
天秤を最大３回使っても判定できないおもりの個数の最小値は２である。
●証明：最終定理より自明。