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

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

No.22 回答者： stomachman 回答日時： 2001/01/26 16:09

siegmund先生< 的確な総括を有り難うございます。

　(3^N+1)/2 個が上限であることの証明の中では、標準問題において「余分の正常なおもりを借りてきてはいけない」という条件が全く使われていません。
　つまり、この上限は「余分の正常なおもりを借りて来ることを許す」という場合の最大判定可能な個数が(3^N+1)/2 個である事を示している。そして、No.94164の定理4、これがその上限の具体的手順（下限）です。だから
「余分の正常なおもりを借りて来ることを許す標準問題」は完全に解決（上限=下限）されています。

さて、定理4の証明を見ればお分かりのように、借りなくてはならない余分の正常なおもりは１個だけなんです。ですから、
(A) 正常なおもりを借りずに(3^N+1)/2 個の判定ができる手順を示す（下限の改良）か、あるいは、
(B)最大手順ではどうしても余分のおもりが必要であることを示す（上限の改良）、
このどちらかが出来れば、標準問題は解決する訳ですね。

　少なくとも、Nが小さい場合には総当たりによって(A)は否定されます。また(B)は、まだ「余分の正常なおもりを借りて来ることを許さない」という条件を使わないで得られた上限でしかない。当然(B)が狙い目です。

No.21 回答者： siegmund 回答日時： 2001/01/26 00:48

siegmund です．

一日半他へ出かけていて，帰ってきてさて書き込もうと思ったら
もう stomachman さんの書き込みが...(^^;)

stomachman さんの証明の主要部分は３部からなっています．

○ No.94164
(3^N-1)/2 を約３等分する．
すなわち，N=5 なら 121 個を，40,40,41 に分けるんですね．
で，単純に N の１つ小さい問題への還元とはいかず，
正常おもりを借りてこられる場合の吟味が必要です．
私は面倒になってやめちゃったんですが，
(面倒以外に，他のやりかたでできたということもある)
stomachman さんはパワーがありますね．

○ No.94177
これは私も本質的に同じことを考えました．
(本当は，誰かが発表した後に自分も同じこと考えたよ，
というのは反則なんですが)．
私の３進法だと，(3^N-3)/2 までが異常おもりの軽重まで
判定可能でした．
(3^N-3)/2 の３進表現は，３進Ｎ桁で
(111・・・110) ⇔ (111・・・112)
になっています．左が正回転表現(重)，右が逆回転表現(軽)です．
(3^N-3)/2 の次の (3^N-1)/2 は３進表現が (111・・・111) ですから，
正回転と逆回転の区別がありません．
で，(3^N-1)/2 番目(すなわち最後)のおもりだけ取り除いて３進手順を行うと，
取り除いたおもりが正常おもりのときは，
前の手順通り異常おもりを軽重まで特定できます．
取り除いた(3^N-1)/2 番目(すなわち最後)のおもり異常のときは，
天秤はいつも釣り合っているので，
天秤の測定結果から得られる３進表現のすべての桁が１．
これはすぐ上で述べたように (3^N-1)/2 を意味します．
正回転逆回転の区別がないことがちょうど軽重判定不能に対応していますね．
多少表現方法が違いますが，本質的に stomachman さんと同じです．

結局，(3^N-1)/2 個の判定には手順固定でＯＫということですね．
stomachman さんも書かれているように，
軽重判定をやめても１個しか増えませんね．
これは天秤の特性ですよね．
傾いてもどちらが異常かはわからない．
そのとき，異常おもりを特定することは軽重まで判定することと同価値．
唯一違うのは，他のおもりが全部正常と判定された場合だけで，
これが１個増える，に対応しているんですね．

○ No.94246
いや～，これは脱帽ですね，さすが stomachman さん．．
手順固定でなくてよいとすると枝分かれがありますから，
上限の評価は難しいと思っていたんですが...

○ そうすると
(a) (3^N-1)/2 個は判定可能で，明快な固定手順も示された．
(b) (3^N+1)/2 個が上限であることが示された．
ですね．
完全解まであと１個ですか．

「中学数学をなめてはいけないなぁ・・・」
がすごいことになってきましたね．

○ No.93362 で，正回転逆回転の区別を最初の２桁の数字の変化で判別，
と書いたのですが，
最初の２桁が同じときは２桁目から３桁目への変化で判定します．
それも同じなら，３桁目から４桁目への変化，以下同様です．

No.20 回答者： stomachman 回答日時： 2001/01/24 23:31

毎度の事ながら、stomachman間違えてしまいました。

> 「最大手順であるならば、どの枝においても無測定おもりが丁度１個ある」
は間違い。

> 「最大手順であるならば、どの枝においても無測定おもりが少なくとも１個ある」

が正解です。なおこれによって、他の部分の論理に訂正は生じません。

No.19 回答者： stomachman 回答日時： 2001/01/24 23:14

さて、直前の回答で概要を示した上限の証明において、

「最大手順は丁度１個のおもりを取り除けておかなければならない」
という表現が曖昧であり、解説が必要だと思いますので補足します。

　最大手順は途中の計測結果によって次の計測の仕方を変えて構わない。いろいろな枝分かれがあって良いのです。（その枝分かれの様子をちょっとイメージしてください。）

●もし「どの枝においても、M個のおもりのどれもが少なくとも一度は天秤に乗る。」というのであれば、（このM個の中に異常なものがあれば）どの枝においても少なくとも一度は天秤が傾くので、もう１個別のおもり（一度も天秤に乗せない）が正常だと分かる。逆にM個全部が正常なら１度も天秤が傾かない。従ってもう１個別のおもり（一度も天秤に乗せない）の異常が判定できる。いずれにせよ、合計(M+1)個を判定できる手順が作れてしまう。これでは最大手順ではない訳です。

●従って最大手順なら「少なくとも一つの枝において、一度も天秤に乗らないおもりが存在する」。以後「ある枝において一度も天秤に乗らないおもり」のことをその枝の「無測定おもり」と呼びましょう。
　最大手順で、一度も天秤が傾かない枝においては、（異常が判定可能であるためには）無測定おもりは２個以上であってはならない。逆に０個だったらM個の中に異常がないことになり、無測定おもりを１個追加しても構わない。だから、この枝において無測定おもりは丁度１個で、あとの(M-1)個は一度は天秤に乗っています。
　最大手順で、一度は天秤が傾くような枝においては、無測定おもりは全部正常だと分かります。もし無測定おもりが０個なら、あと１個おもりを追加してそれを無測定おもりにしても、その追加分は正常と判定できる。しかし２個以上追加すると、もし「一度も天秤が傾かない枝」に行ってしまったときに手順全体がダメになります。
　以上から、「最大手順であるならば、どの枝においても無測定おもりが丁度１個ある」ということになります。ただし、それぞれの枝ごとに無測定おもりが違っていてもかまわない。

●さて、最大手順の各枝の各測定において、天秤に乗せないおもりの選び方を適当に入れ替えることによって、どの枝にも共通に、同じ一つのおもりPが無測定おもりになるようにできます。
　最初の測定において、天秤に乗らないおもりの内のひとつをPとします。（どの枝にも無測定おもりがあるから、少なくとも１個のおもりは天秤に乗らない筈です。）この測定結果によって、３通りの状態<1回目=右下がり><1回目=左下がり><1回目=釣り合い>のどれかへ進むことになります。
　状態<1回目=右下がり>を調べます。どの枝にも無測定おもりがあるから、２度目の測定においても、少なくとも１個のおもりは天秤に乗らず、しかもそのおもりは最初の測定でも天秤に乗っていません。もしそれがPであれば問題なし。しかし、Pとは別のおもりQであったとしましょう。PもQも最初の測定で天秤に乗っていないのですから、２回目の測定で「どうしてもQを天秤に乗せず、Pを乗せねばならない」という理由はありません。そこで状態<右下がり>において２回目に測るおもりの選び方を訂正し、PとQを入れ替えてしまいます。そしてこの状態に繋がる３回目以降の測定におけるおもりの選び方も一斉に訂正します。この訂正によって、手順自体の判定能力が全く損なわれないことは自明でしょう。
　次に、状態<1回目=右下がり>に繋がる一つの状態、たとえば<1回目=右下がり, 2回目=釣り合い>を調べます。この状態で行う３度目の測定においても、少なくとも１個のおもりは天秤に乗らず、しかもそのおもりは１回目、２回目の測定でも天秤に乗っていません。もしそれがPであれば問題なし。違うQであれば、３回目に測るおもりの選び方を訂正し、PとQを入れ替えてしまいます。そしてこの状態に繋がる４回目以降の測定におけるおもりの選び方も訂正します。
　このようにして、全ての状態で無測定おもりが共通(P)になるように手直しをすることが出来ます。

●それで、「最大手順は丁度１個のおもりを取り除けておかなければならない」という命題の正確な意味は、
「最大手順は判定能力を全く損なうことなく『丁度１個のおもりPをあらかじめ決めて、取り除けておく』という形に書き換えることができる。」
という事なんです。

No.18 回答者： stomachman 回答日時： 2001/01/24 19:57

stomachmanです。

いよいよ仕上げに掛かりましょう。標準問題の計測可能なおもりの個数の上限の話です。

　１回の計測で、どちらかに傾くか釣り合うかの３通りの結果があります。従ってN回天秤を使うと、3^N通りの計測結果が出ます。これで判定可能なおもりの最大個数をM個とします。そのような、最大個数を判定できる計測手順（「最大手順」と名付けましょう）の性質を調べてみましょう。

●最大手順において、一度も天秤に乗せないで済む（取り除けておける）おもりの個数は高々１個です。残り(M-1)個のおもりは必ず１度は天秤に乗ったことがある。
　＊なぜなら、もし２個以上のおもりを取り除けておいたとすれば、N回全ての計測で天秤が釣り合った場合に、取り除けておいたうちのどれが異常なのか判定できず、従って、これは最大手順ではない。矛盾です。

●逆に、最大手順では少なくとも１個を取り除けておかねばなりません。
　＊なぜなら、取り除けたおもりがないとすると、N回全ての計測で天秤が釣り合った場合には、おもりM個の中に異常がないことが分かる。従って、(M+1)個が判定できる別の手順が作れます。すなわち
　手順Ｘ：「(M+1)個のうち、１個を取り除けておく。残りM個に対して最大手順を適用する。もし、天秤が一度も傾かなければ、取り除けた１個が異常。」
　ゆえに、最大手順よりも沢山のおもりが判定できる手順Ｘが存在することになり、最大手順の定義と矛盾します。

●だから最大手順では、必ず丁度１個を取り除け、残りの(M-1)個は少なくとも１度は天秤に乗せます。そして最大手順では、
「天秤が少なくとも１度傾く」⇔「取り除けなかった(M-1)個のおもりの中に異常なのがある」
この二つの命題は等値です。N回の計測で天秤が少なくとも１度傾くというケースは(3^N-1)通りあります。

●次に最大手順において、天秤が少なくとも１度傾いた、という場合に限って考えます。N回の計測の結果、(M-1)個中のどれが異常であるかが分かった訳です。（分からなければ最大手順じゃないですね。）
　そして、ある計測１回について
　「天秤が傾いた」⇔「その異常なおもりが天秤（のどちらかの皿）に乗っていた」
この二つの命題は等値ですね。ですから、異常であると分かったおもりが、天秤が傾いた計測（少なくとも１度ある）の際にどっちの皿に載っていたのかを（N回の計測が終わったあとで）調べれば、その異常なおもりが重いのか軽いのかまで（嫌でも）分かってしまいます。

●以上から、「取り除けなかった(M-1)個のおもりの中に異常なのがある」という場合については、そのどれが異常なのか、そしてそれが重いのか軽いのかを含めて(M-1)×2通りがあります。N回の計測で生じうる、天秤が少なくとも１度傾くケースは(3^N-1)通りであり、これで(M-1)×2通りを区別する必要があるのだから、
(M-1)×2 ≦(3^N-1)
従って、
M ≦(3^N+1)/2
です。

この証明、いかがでしょう？

No.17 回答者： stomachman 回答日時： 2001/01/24 18:42

stomachmanです。

　今度はsiegmund先生の３進法をちょこっといじって、やはりN回の計測で(3^N-1)/2個が判定可能であることを示すことにします。

　siegmund先生の方法をよく見ると、N回の計測のうち、どのおもりも１度は天秤に乗っています。だから、異常なおもりが１個あるのなら、必ず１度は天秤が傾く筈ですね。
　逆に、もし１度も天秤が傾かなかったら、異常なおもりがないことが示される訳です。

　従って、(3^N-1)/2個から一つだけ取りのけておき、残りの(3^N-3)/2個に対してsiegmund先生の方法を適用し、もし１度も天秤が傾かなかったら、取りのけて置いた１個が異常（重いか軽いかは分からない）であることになります。（証明終わり。）

No.16 回答者： stomachman 回答日時： 2001/01/24 18:25

stomachmanです。

標準問題の４回の測定の場合については、siegmund先生が構成的に証明を示されました。任意のN≧1の場合については以下の定理5の通りです。（これが現時点での下限ですが、しかし「これより多いおもりは判定できない」ということはまだ証明できていませんね。）

●定理1
余分の正常なおもりを借りられなくても、
「この中に軽い(重い)物が１個ある」と分かっているおもり3^N個（この集合をLとする）の内から、N回の測定で異常なおもりを特定できる。(N≧0)
●証明：N=0の場合は自明。N>0の場合、左右の皿に3^(N-1)個ずつ乗せ、残り3^(N-1)は乗せない。釣り合えば乗せなかった集合、釣り合わなければ軽か(重か)った集合、について定理１を適用する。 （証明終わり)

●定理２
余分の正常なおもりを借りられるとしたとき、
「この中に重い(軽い)物はない」と分かっているおもり(3^N+1)/2個（この集合をLとする）と、
「この中に軽い(重い)物はない」と分かっているおもり(3^N-1)/2個（この集合をHとする）の中に異常な物が１個ある場合、N回の測定で異常なおもりを特定できる。(N≧0)
●証明：N=０の場合、Lは１個、Hは０個であるから自明。
Lのおもりを1こずつ左右の皿に乗せる。釣り合えばHが重く、さもなければ軽かった方が軽い。
(N>０の場合)
Lを3^(N-1)個（Laとする）と{3^(N-1)+1}/2個（Lbとする）に分ける。
Hを3^(N-1)個（Haとする）と(3^(N-2)-1)/2個（Hbとする）に分ける。
左の皿にHbとLaを乗せ、右の皿にLbと正常のおもり(3^(N-1)+1)個を乗せる。
もし左が下がれば、「Hbの中に軽いのはなく、Lbの中に重いのはなく、これらの内に異常な物が１個ある」ので、これらに定理２を適用。
もし右が下がれば、「Laの中に軽いのがある」からLaに定理1を適用。
もし釣り合えば、「Haの中に重いのがある」からHaに定理1を適用。（証明終わり）

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

●定理4
余分の正常なおもりを借りられるとしたとき、
「この中に異常な物が１個ある」と分かっているおもり(3^N+1)/2個（この集合をXとする）の内から、N回の測定で異常なおもりを特定できる。(N≧1)
●証明：N=1の時はXは２個である。その内の１個を左の皿に、正常なもの１個を右の皿に乗せる。釣り合えば乗せなかったものが異常で、さもなければ乗せた物が異常である。
(N>1の場合）
Xを(3^(N-1)+1)/2個（Xaとする）、(3^(N-1)-1)/2個（Xbとする）、(3^(N-1)+1)/2個（Xcとする）に分ける。Xaを左の皿に、Xbと正常のおもり１個を右の皿に載せる。
もし釣り合えば「Xcの中に異常な物が１個ある」から定理４を適用。
もし左が下がれば「Xaの中に軽い物はなく、Xbの中に重い物はなく、どちらかに異常なものが１個ある」から定理２を適用。
もし右が下がれば「Xaの中に重い物はなく、Xbの中に軽い物はなく、どちらかに異常なものが１個ある」から定理２を適用。（証明終わり）

●定理5（標準問題）
余分の正常なおもりを借りられなくても、
「この中に異常な物が１個ある」と分かっているおもり(3^N-1)/2個（この集合をLとする）の内から、N回の測定で異常なおもりを特定できる。(N≧1)
●証明：N=1の時はXは１個であるから測らなくても分かる（し、測りたくても比べる相手がない）。
(N>1の場合）
Xを(3^(N-1)-1)/2個（Xaとする）、(3^(N-1)-1)/2個（Xbとする）、(3^(N-1)+1)/2個（Xcとする）に分ける。Xaを左の皿に、Xbを右の皿に載せる。
もし釣り合えば「Xcの中に異常な物が１個ある」から定理４を適用。
もし左が下がれば「Xaの中に軽い物はなく、Xbの中に重い物はなく、どちらかに異常なものが１個ある」から定理３を適用。
もし右が下がれば「Xaの中に重い物はなく、Xbの中に軽い物はなく、どちらかに異常なものが１個ある」から定理３を適用。（証明終わり）

No.15 回答者： stomachman 回答日時： 2001/01/24 15:28

余分の正常なおもりがあればCeiling(3^N/2), なければFloor(3^N/2)というのが予想になってきたみたいですね。

punchan_jpさんの与えられた上限Floor(3^N/2)は「異常なのが重いか軽いかまで判定する」という条件付きですから、まだホントの上限は分かっていない。

それにしても、手順を固定して、さらに異常なのが重いか軽いかまで決める、という条件を追加しても、なお判定できる最大個数が１個しか増えないというのは、実に面白いと思いませんか？

No.14 回答者： siegmund 回答日時： 2001/01/24 10:35

私の３進法方式が正しいとすると，

もともとの標準問題
「手順非固定，異常おもりの軽重は判定しなくて良い」で，
４回で４０個までＯＫなのは具体的手順と共に簡単に示せます．

最初の天秤のときに，G(1,1)のグループに４０番目を
入れておけばいいのです．
４０の３進表現は (1111) ですから，分類上もちょうどよい．
で，G(1,0) と G(1,2) を比べる．

(A) 天秤が傾いた場合．
天秤に乗せなかったグループ {G(1,1)＋４０番目} は正常ですから，
４０番目を取り去ってしまって差し支えない．
あとは前の手順通りで，この場合は異常おもりの軽重まで判定できます．

(B) 天秤が釣り合った場合．
天秤に乗せなかったグループ {G(1,1)＋４０番目} に異常おもりがあります．
したがって，
【３回で１４個，ただし正常おもりが与えられている】
に帰着します．
これは stomachman さんが言われるように，判定可能です．

したがって，標準問題は４回で４０個まで可能なことが
具体的手順と共に示されました．

これは Naka さんが書かれている上限 floor(3^4 / 2) ですから，
４０個が限界でしょう．

stomachman さん，書いちゃいました，ごめんなさい．

No.13 回答者： stomachman 回答日時： 2001/01/24 03:22

元の問題の条件（標準問題）において、

K(n)：異常が重いか軽いか分かっていて、n回で判定できる最大個数
L(n)：異常としか分からなくて、n回で判定できる最大個数（ただし正常１個を借りる）
L'(n)：異常としか分からなくて、n回で判定できる最大個数（ただし正常１個を借りない）

とすると、
K(n) = 3^(n-1) は自明でしょう。そして、システマティックなやり方で、少なくとも
L(n) = K(n-1)+L(n-1)、
L'(n) = L(n)-1
とできます。したがって、L(0)=1を用いると、
L(1)=1+1 = 2
L(2)=3+2 = 5
L(3)=9+5 = 14
L(4)=27+14=41
L(5)=81+41=122
となります。だから、Nakaさん、4回で判定できる最大個数は少なくとも L(4)-1=40個だと思います。
　このやり方の詳細は、ちょっと待って（いや、もちろん誰か書いちゃってもいいです。）

　siegmund先生の（計測手順固定の問題における）きれいな解析は、40個以下なので問題なさそう。という事になります。