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

質問

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

回答No.27

stomachman

「(3^(N+1)-1)/2＞K＞(3^N-1)/2個のおもりを(N+1)回以内の計測で判定するためには、A個のおもりを天秤の左の皿に、別のA個を右の皿に乗せて、残りQ=K-2Aが(3^N+1)/2個または(3^N-1)/2個になるようにすればよい」
という事をもうちょい、厳密に仕上げてほんとにおしまいにしましょう。

・N=1の場合は4＞K≧2個のおもりを2回以内で判定せよ、というのですから、これは自明です。

したがって、N≧1の場合だけ検討すれば良い。

最初の計測で天秤に乗せないおもりの数をQとします。
(3^N+1)/2または(3^N-1)/2のどちらかは偶数で他方は奇数ですから、
(i) Kと(3^N+1)/2が共に偶数であるか、共に奇数であるとき。
　Q=(3^N+1)/2ですから、(3^N-1)/2＞A＞0
(ii) Kと(3^N-1)/2が共に偶数であるか、共に奇数であるとき。
　Q=(3^N-1)/2ですから、(3^N-1)/2≧A＞0
となります。
いずれにせよ、Q≧(3^N-1)/2、(3^N-1)/2≧A＞0です。

さて、
●もし天秤が釣り合ってしまえば、天秤に載せなかったおもりに対して定理４か定理５を適用すれば、あとN回の計測で判定できる。だから(N+1)回で判定できます。

●では天秤が傾いた場合、次にどうするかを詳しく調べましょう。

定理Ｘ：
N≧１で、正常なおもりが少なくともq=(3^N-1)/2個あるとする。
(3^N-1)/2≧A＞0のとき、
「この中に重い物はない」と分かっているおもりA個（この集合をLとする）と、
「この中に軽い物はない」と分かっているおもりA個（この集合をHとする）の中に異常な物が１個ある場合、高々N回の測定で異常なおもりを特定できる。（N≧1）

【証明】
[1]N=1の場合。
つまり正常なおもりが少なくともq=1個あって、A=1のときです。
右の皿に正常なおもり１個、左の皿に「この中に重い物はない」と分かっているおもり1個を乗せれば良い。確かに１回で判定できました。

[2]N＞1の場合。
正常なおもりが少なくともq=(3^N-1)/2個あり、(3^N-1)/2≧A＞0のときです。Aの個数によって場合分けします。
(1) (3^(N-1)-1)/2≧A＞0のとき、
集合L, Hそれぞれに正常なおもりC個を加えて(3^(N-t)-1)/2個づつにしてやる。(tは、t≧1で、(3^(N-t)-1)/2≧Aとなる最大の整数。）
これに必要なおもりは高々2C＜(3^(N-1)-1)です。さらに正常なおもりが高々3^(N-2)個あれば、定理３によって(N-t)回の測定で判定できます。
t≧1だから、つまり高々N回で判定できます。
　さて、以上の操作に必要な正常なおもりの総数rはr＜3^(N-2)+(3^(N-1)-1)であり、
q=(3^N-1)/2＞3^(N-2)+(3^(N-1)-1)
ですから、正常なおもりが不足することはありません。

(2) 3^(N-1)≧A＞(3^(N-1)-1)/2のとき、
Lをr=(3^(N-1)+3)/2個（La)と、p=A-(3^(N-1)+3)/2個(Lb)に分ける。
Hをr=(3^(N-1)+3)/2個 (Ha)と、p=A-(3^(N-1)+3)/2個(Hb)に分ける。
HbとLbのおもりの個数pはp＜(3^(N-1)-1)/2です。
（∵p=A-(3^(N-1)+3)/2≦3^(N-1)-(3^(N-1)+3)/2=(3^(N-1)-3)/2＜(3^(N-1)-1)/2）
またHaとLaのおもりの個数rは
r=(3^(N-1)+3)/2＜3^(N-1)です。
左の皿にHbとLa（合わせてA個）を乗せ、右の皿にLbと正常なおもり(3^(N-1)-1)/2個を乗せる。
もし左が下がれば、「Hbの中に軽いのはなく、Lbの中に重いのはなく、これらの内に異常な物が１個ある」ので、これらに定理Ｘを適用すれば(N-1)回で判定できる。
もし右が下がれば、「Laの中に軽いのがある」から、Laに正常なおもりを加えて3^(N-1)個にし、定理1を適用して(N-1)回で判定できる。
もし釣り合えば、「Haの中に重いのがある」から、Haに正常なおもりを加えて3^(N-1)個にし、定理1を適用して(N-1)回で判定できる。
従って、N回で判定できます。
　さて、必要な正常なおもりの数rは高々r＜3^(N-1)個であり、q≧3^(N-1)であるから、正常なおもりが不足することはありません。

(3) (3^N-1)/2≧A＞3^(N-1)のとき、
Lを3^(N-1)個（La)と、p=A-3^(N-1)個(Lb)に分ける。
Hを3^(N-1)個（Ha)と、p=A-3^(N-1)個(Hb)に分ける。
HbとLbのおもりの個数pはp≦(3^(N-1)-1)/2です。
（∵p=A-3^(N-1)≦(3^N-1)/2-3^(N-1)=(3^(N-1)-1)/2）
左の皿にHbとLa（合わせてA個）を乗せ、右の皿にLbと正常なおもり3^(N-1)個を乗せます。
もし左が下がれば、「Hbの中に軽いのはなく、Lbの中に重いのはなく、これらの内に異常な物が１個ある」ので、これらに定理Ｘを適用して(N-1)回で判定できる。
もし右が下がれば、「Laの中に軽いのがある」から、Laに定理1を適用して(N-1)回で判定できる。
もし釣り合えば、「Haの中に重いのがある」から、Haに定理1を適用して(N-1)回で判定できる。
従って、N回で判定できます。
　さて、必要な正常なおもりは3^(N-1)個であり、q≧3^(N-1)であるから、正常なおもりが不足することはありません。
（証明終わり）

これで完璧かな？