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

質問

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

回答No.23

stomachman

大団円。になってくれると嬉しいけど....

定理6：
「余分のおもりを借りてきても、N回の計測で判定できる個数の上限は(3^N+1)/2である」

残された問題は、
「計測N回の最大手順で測れる個数がM=(3^N+1)/2 なのかM=(3^N-1)/2 なのか。」
です。

補題1：
「M個を判定できる任意の計測手順において、１回目の計測で、天秤に掛けないおもりの個数の上限は(3^(N-1)+1)/2である。」
証明：「余分のおもりを借りてきても、(N-1)回の計測で判定できる個数の上限は(3^(N-1)+1)/2である」ということから自明です。１回目で天秤が釣り合ってしまった場合、測っていないおもりが(3^(N-1)+1)/2個より多ければ判定不能になるからです。

補題２：
「余分のおもりを借りてこない任意の計測手順において、１回目の計測で、天秤に掛けるおもりの個数は偶数である。」
左右の皿に同じ個数を載せなくては計測になりませんから、これは自明です。

　仮定１：「計測N回の最大手順で測れる個数はM=(3^N+1)/2」だったとしましょう。

補題１より、１回目の計測で天秤に乗せないで済むおもりの数QはV=(3^(N-1)+1)/2以下、すなわち
Q ≦ V=(3^(N-1)+1)/2
であり、従って、左の皿に乗せるおもりの数をWとすると、右の皿にも同じ数のおもりを乗せますから、Wは(M - V)/2以上でなくてはなりません。
W ≧ (M - V)/2＝((3^(N-1))/2
ところが右辺は整数になりません。だから、
W ≧ ((3^(N-1)+1)/2
でなくてはならない。すると１回目の計測で天秤にかけるおもりの個数は
2W ≧(3^(N-1)+1
従って、天秤に掛けないおもりの数Qは
Q=M-2W ≦{3^(N-1)-1}/2
ですね。これは確かに補題１の上限を満たしています。それどころか、上限より１個少ない。

　仮定１において、(M+1)個のおもりがあったとしましょう。１回目の計測では、この追加のおもりは天秤に乗せないものとします。１回目の計測で
　(a) もし天秤が釣り合ったら：天秤に乗せなかった(3^(N-1)+1)/2個のおもりの中に異常があり、これは定理４によって(N-1)回で判別可能です。
(b) もし天秤が傾いたら：天秤に乗せなかった(3^(N-1)+1)/2個のおもりは全部正常ですから、最大手順をそのまま続ければ判定可能です。
　従って、最大手順でM+1 = (3^N+3)/2 個のおもりが判定できることが分かります。

　ところが、補題１によって、最大手順が判定できるおもりの個数の上限はは(3^(N-1)+1)/2である。つまり、矛盾が生じました。これは仮定１が誤りであることを示しています。すなわち、

補題３：
　「計測N回の最大手順で測れる個数は(3^N+1)/2ではない。」
が証明できたわけです。

以上から、

標準問題の最終定理：
「余分のおもりを借りてこないで計測N回の最大手順で判別できる最大個数はM=(3^N-1)/2 である。」

チェックとまとめは皆さんに頼っちゃおうかな?

それに、もっとスマートな証明があると良いですねえ。