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

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

No.32 回答者： stomachman 回答日時： 2003/01/31 22:13

　論理や式ばっかりでは詰まらないんで、ミソを解説してみようと思います。

　「一山のおもりの中に１個だけ、重さが違うものが混ざっている。これを、天秤を最低限の回数だけ使って見つけろ」
　こんな条件が要求される状況は現実にはそうそうないと思われるので、ゲンバから出た切実な問題、という訳ではなさそうです。（実際的な解決法はたとえば回答No.6でしょう。）このパズルは昔からあるけれど一体どのぐらい歴史を遡れるものなのか知りません。しかしまた、完全な解を見たこともなかったのです。（もちろん、とっくの昔の文献に書いてあるのかも知れません。）

　「一山のおもりの中に１個だけ、他より軽いものが混ざっている。」という問題はしばしば見掛けます。これですと、回答No.1（あるいは回答No.30の定理１）の発想で良い。易しいだけでなく、解が綺麗で鮮やかですね。
　第一のポイントは「おもりの幾つかを天秤に掛け『ない』ことによって、かえって少ない回数の計測で判定できる」という逆説的な面白さです。たとえば２７個のおもりがあるとすると、９個ずつ左右の皿に乗せ、残り９個は乗せない。天秤が傾けば、上がった皿に乗せたものの中に軽いものが混ざっていると分かる。そして、天秤が釣り合ったら「２７個のおもりの中に１個だけ、他より軽いものが混ざっている」んだから、天秤に掛けなかった残り９個の中に軽いものがあると分かる。
　「２７個のおもりの中に１個だけ、他より軽いものが混ざっている」という知識が、１回の計測によって「９個のおもりの中に１個だけ、他より軽いものが混ざっている」に変わった。それでまた同様にして３個ずつ左右の皿に乗せて測ればよい。このように（数が少なくなったけれど）元の問題と全く同じ形をした問題に帰着されるところが面白いですね。つまり第二のポイントは「再帰性」です。これは数学的な発想の特徴とも言えるでしょう。数学的帰納法の基本的考え方であり、アルゴリズムの基本でもあります。

　異常なおもりが重いか軽いか分からない、ということになると格段に難しくなります。最もシステマティックなアプローチは、回答No.11でstomachmanが出題し、回答No.12でsiegmund教授が解決している問題：「異常なおもりが１個だけ必ず混じっている。てんびんをＮ回使ってこれを見分けよ。ただし、各測定に際しててんびんの左右の皿にどのおもりを乗せるかはあらかじめ決めて置かねばならず、測定結果によって変えることは許さない」でしょう。
　天秤が「釣り合う、右が下がる、左が下がる」の３通りの測定結果を出すことを符号でそれぞれ0,1,2と表すことにし、例えば４回の計測なら４桁の３進数であると考える。そして、この３進数が「どのおもりが異常か」を示すコード（つまりおもりに付けておくべき番号）になるようにしてやる訳です。種を明かせばstomachman、３進法を使えば手順固定でも判定できるということを、ある新聞の日曜版に載った懸賞問題（もちろん天秤の問題）を解くときに見つけたという経験を持っていたのです。
　またこの問題は「実験計画法」という分野と直接の関係があり、符号理論や直交級数展開（たとえばウォルシュ＝アダマール変換）とも関連を持ちます。一見全然関係がなさそうな分野と話が繋がるという所が、数学っぽいですね。
　「手順を変えてはいけない」という一見厳しい条件は、実は解法を強く示唆するヒントになっています。それにしてもさすがsiegmund先生、早かったですね。ビックリしました。

　回答No.12のような手順固定のやり方は、半端な個数（たとえば35個）のおもりを判定する場合にすんなり適用できない、という弱点を持っています。もっと柔軟な「手」を用意しておきたい。そこで回答No.16では（回答No.2でご紹介があったような、あるいは回答No.4でstomachmanが示したような）計測結果を見ながら測り方を選んでいく手順を一般化したものを、体系的に示しました。
　ここでポイントになるのは、１回目の計測結果から「これらのおもりの中には異常なものは入っていない」と保証できるおもりが幾つか得られる。そういう正常と分かったおもりを２回目以降の計測で旨く利用する、という点です。正常と分かっているおもりは、比較対象として、あるいは左右の皿に乗せるおもりの数が同じになるように調節してやるために、非常に重要なのです。
　またもうひとつのポイントは「『この中には軽いおもりはない』と分かっているような一群のおもり」という概念です。これは「この一群のおもりは(1)全部正常であるか、あるいは(2)異常なものが含まれていて、その異常なものは正常よりも重い」ということを意味します。そして、ひとたびこの言語表現に行き当たれば、手順を作る問題は案外易しいのです。
　ここでは「答は一通りではない。とても美しいものやゴチャゴチャしたものがある。また問題を拡張するのに適した答と、それには向かない答がある」というあたりが面白いかと思います。
　
　回答No.9、No.10における情報量からのアプローチは、本質的には「天秤が出力できる計測結果のパターンがこれだけの数しかないとすれば、判定できるおもりの個数はそれによって限定される」という考え方です。この重要なアイデアは回答No.30の定理６に使われ、「天秤を４回使って４２個以上のおもりを判定する方法はない」ということを、具体的な手順を一切検討することなく証明しています。いかにも数学らしい「不可能であることの証明」の例です。
　
　ところで具体的な計測手順を示せたのは、回答No.14, 回答No.16, 回答No.17にある通り、「天秤を４回使うのだとすると４０個のおもりを判定できる」という事です。ですから、４０個なら手順が分かっている。４２個以上なら不可能だと分かっている。では「４１個のおもりを４回の測定で判定することは可能なのか、不可能なのか。」これが次なる問題です。回答No.12のやり方を拡張する（回答No.17のように）という方針ではちょっと出来そうにありませんけれど、でも「毎回の測定結果を見てどのおもりを測るか、その手順を変えても良い」のなら可能なのかも知れない。いや、やはり不可能なのかも知れない。
　
　このわずか１個の違いを決着するために随分大がかりな考察が必要でした。回答No.18以降No.25まで考察は錯綜しましたけれど、結論は「不可能」。従って、４１個を判定する具体的手順を構成して見せる、というやり方では証明できません。あらゆる測り方全部を相手に、「そのどれもが４１個を判定できない」ということを示さねばならない訳です。
　その証明を、余計な脇道を削ぎ落としてまとめ直したのが回答No.30の補題１, 補題２, 定理7です。（無論、脇道は脇道なりに面白いのですが。）
　ここでポイントになったのは「天秤は左右の皿に同数のおもりを乗せなくては計測できない」という当たり前のような前提でした。この条件を考慮することで回答No.30の定理７が得られ、４回の測定では４１個のおもりを判定できないことが証明できました。
　定理７の証明は帰謬法（背理法）を使っています。具体的には「４回の測定で４１個を判定できる方法があると仮定すれば、それがどんな方法であれ、ちょっと手直しすれば４２個だって判定できる。ところが定理６によって、４１個より多くは無理だと分かっている。これは矛盾だ。だから仮定は間違いで、４回の測定で４１個を判定できる方法はないんだ」という論法です。これも数学っぽいですね。

　あとに残ったのは「じゃあ４０個より少ないおもりなら何個でも４回以内で判定できるのか？」という問題です。これを検討した回答No.27には一部間違いがありました。結局（２個のおもりの場合を除いて）回答No.30の定理８～１０でその具体的手順が示されていますが、これが案外単純には行かない。定理1～5（回答No.16を整理したもの）を組み合わせるだけではまだちょっと不足で、大変長い証明が必要になってしまいました。
　ここでポイントになるのは、正常と分かっているおもりが手順の途中で足りなくなったりしないか、という点です。基本的には「最初の計測のあと、正常と分かったおもりを適当な個数追加して、問題を４０個を判定する場合の手順の一部に帰着したい」訳ですが、おもりの個数によって場合分けし、どんな手順に帰着させるかを切り替える必要がありました。もっと美しい解法はないものか、と思っています。

　回答No.30の補題２は「２個のうち一方が異常、という場合、判定のしようがない」ということ。ちょっと面白いです。
　１個のおもりが渡されたのなら、「これが異常なおもりです。さ、どれが異常でしょう？」と言われた訳です。禅問答じゃないんだから即決で「これ」と答えられます。３個以上おもりがあれば、異常なおもりは他の多数のものとは違う、ということを手掛かりにして天秤を使って見つけられる。しかしおもりを２個渡された場合には、どっちが正常どっちが異常と決める手掛かりが全くない。これはもう、数学と言うよりテツガクっぽいですねえ。

No.31 回答者： siegmund 回答日時： 2003/01/11 02:02

siegmund です．

しかし，まあ，stomachman さん，凄い回答ですね．
パワーには脱帽です．
これは読むのも大変です(検討して書いた人がいるのに情けない話ですが...)
最近忙しく，じっくり読む時間がなかなか取れません．
(前にもそんなこと書いたな～)．

No.30 回答者： stomachman 回答日時： 2003/01/10 01:15

天秤問題。

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個のおもりを判定できる」。
（証明終わり）

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

No.29 回答者： siegmund 回答日時： 2001/04/10 23:59

変形を考えればいくらでもありますね．

でも，典型的問題に対して完全解決を見たというのは
stomachman さんの業績ですよ．
前に「素人が偉大な理論を構築したら 」という質問がありましたが，
誰もやっていなければ論文になるんじゃ....？

> 例を調べたり、予想を立てたり、ズルを考えたり、色々な観点で評価をしたり、
> 関連する別の問題を考えたり、相互に関連する定理の体系を作ったりと、
> 数学の問題を解いたり作ったりする過程を
> 図らずも多面的にデモしたスレッドになりましたねえ。

おっしゃるとおりです．
これだけのスレッドはなかなかないでしょう．

誰か，天秤問題ＨＰなんて作らんかな～．

なかなかまとまった時間がとれなくて，stomachman さんの解が落ち着いて
読めません．

ところで，フィールズ賞は４０歳以下という制限がありますが，
stomachman さんは大丈夫ですか？
私はもう資格がありません(^^;)

雑談で失礼しました．

No.28 回答者： stomachman 回答日時： 2001/04/10 14:42

天秤問題完全解決、と言うのはやっぱり早計ですね。

まだまだいろんな問題が考えられますから。
●K個のおもりに対して、計測の平均回数が最小になるような手順は？
●K個のおもりに対して、あらかじめ計測の手順を決めておくとしたときの手順は？
●K個のおもりに対して、秤に乗せるおもりの平均延べ個数を最小にする手順は？
●幾つか異常なおもりが混ざっているとしたら？
●一度に秤に乗せられるおもりの数に制限があるとしたら？
などなど....本当に多様で、天秤学が展開できてしまいそう。（フィールズ賞用のピンクの水玉のタキシードは注文中です。）

例を調べたり、予想を立てたり、ズルを考えたり、色々な観点で評価をしたり、関連する別の問題を考えたり、相互に関連する定理の体系を作ったりと、数学の問題を解いたり作ったりする過程を図らずも多面的にデモしたスレッドになりましたねえ。
なお、間違いやもっと良い解を見つけた場合、質問が閉じられた後ですら管理者様に申請すれば追加回答が可能ですんで....siegmund先生はじめご来場の皆様、チェック宜しく。

No.27 回答者： stomachman 回答日時： 2001/04/09 20:46

「(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)であるから、正常なおもりが不足することはありません。
（証明終わり）

これで完璧かな？

No.26 回答者： siegmund 回答日時： 2001/04/08 00:28

stomachman さん，お久しぶりです．

siegmund です．

とうとう完全解決ですか．
すごいことになりましたね．
これで，ノーベル賞，stomachman さん常備のタキシードの出番？
あ，ノーベル数学賞ってのはないんだった．

心の隅に引っかかってはいたのですが，もう大分忘れてしまったし....
最初から読み直さんとわからんな～．
ちょっと時間ができたら読ませていただきます．

No.25 回答者： stomachman 回答日時： 2001/04/07 03:14

うー。

どなたも閉めてくださらないようなので、責任とります。

では、一般に(3^(N+1)-1)/2> K > (3^N-1)/2個のおもりの場合の手順を示す問題を片づけます。
この3^N通りの場合についてそれぞれ手順を示す必要があり、これらの場合いずれも少なくとも(N+1)回の計測が必要であることは既に証明されました。
さらに、いずれも(N+1)回の計測で済む、というのがこれから検討する予想です。
方針としては、最初の１回の計測の結果に基づいて、N回天秤を使う場合の定理１～5に帰着してやれば良い。

[A]始めにN=1の場合を考えます。すなわち
4 > K > 1
つまりK=2か３です。
K=2の場合には判定は不可能です。天秤は必ず傾きますが、どっちが異常なのか決められません。
K=3なら定理１で２回で判定可能。
ついでにK=4なら、N=2とした場合の定理５によって、２回で判定可能です。

[B]次にN>1の場合を考えます。
左右の皿にA個づつ乗せて、残りK-2A個を乗せません。このとき、
K-2A = (3^N-1)/2もしくは(3^N-1)/2-1を天秤に乗せないというのが旨いやり方のようです。

一般に(3^(N+1)-1)/2> K > (3^N-1)/2の場合、
最初の１回の計測において、天秤の左右の皿にそれぞれA個(K/2>A>0)のおもりを乗せて、K-2A個は乗せないものとします。ここでK-2A = (3^N-1)/2もしくは(3^N-1)/2-1とします。
(a) 天秤が釣り合った場合
乗せなかったK-2A個のおもりの中に異常なものがある。そして2A個(2A>0)の正常なおもりが手に入りました。そうしたら、調べたいK-2A個のおもりに、必要ならあと１個正常と分かったおもりを加えて(3^N-1)/2個にし（K > (3^N-1)/2だから必ずこれは可能です）、そして
定理5：余分の正常なおもりを借りられなくても、「この中に異常な物が１個ある」と分かっているおもり(3^N-1)/2個（この集合をXとする）の内から、N回の測定で異常なおもりを特定できる。(N≧1)
を使うとN回で計測が可能になります。最初の１回の計測と合わせて(N+1)回で判定できました。

(b)天秤が釣り合わない場合はどうでしょうか。
(3^(N+1)-1)/2> K
です。そして
K-2A = (3^N-1)/2もしくは(3^N-1)/2-1
となるようにしたのですから、
K-2A = (3^N-1)/2　　∴2A=K-(3^N-1)/2<3^N-1　
あるいは
K-2A = (3^N-1)/2-1 ∴2A=K-(3^N-1)/2+1<3^N+1
です。つまりいつでも
A≦(3^N-1)/2、余分の正常なおもりはK-2A ≧(3^N-1)/2-1
となります。
定理3：余分の正常なおもりを借りられるとしたとき、
「この中に重い物はない」と分かっているおもり(3^N-1)/2個（この集合をLとする）と、
「この中に軽い物はない」と分かっているおもり(3^N-1)/2個（この集合をHとする）の中に異常な物が１個ある場合、N回の測定で異常なおもりを特定できる。（N≧1）
を使うためには、
・N>1の場合、余分の正常なおもりが3^(N-1)個必要です。ところがN>1ならば必ず
3^(N-1)≦(3^N-1)/2-1
ですから、正常なおもりが不足する心配はありません。念のために確かめますと
(3^N-1)/2-1-3^(N-1)=3^(N-1)-3/2
ここでN>1より
3^(N-1)≧3
だから、
(3^N-1)/2-1-3^(N-1)＞0
ゆえに
3^(N-1)＜(3^N-1)/2-1
です。
かくて、天秤が釣り合わない場合にもN回で判定が可能であり、最初の１回と合わせて(N+1)回で判定できました。

また、(3^N-1)/2= Kの場合にN回で判定する手順は定理5に示されています。
以上をまとめると、
・K=1個の場合には測定なしで判定できる。
・K=2個の場合には判定が不可能である。
・K=3個の場合には高々２回の計測で判定できる。（定理1参照）
・K=4個の場合には高々２回の計測で判定できる。（定理5参照）
・N>1について、
(3^(N+1)-1)/2> K > (3^N-1)/2の場合には、(N+1)回の計測で判定できる。
その手順は、
左右の皿に同数のおもりをのせて、残りが(3^N-1)/2もしくは(3^N-1)/2-1個になるようにする。
(a)もし釣り合ったら、秤に乗せなかったおもりの数を(3^N-1)/2になるようにし、定理５を適用。
(b)もし釣り合わなかったら、定理３を適用。
です。
K=(3^(N+1)-1)/2の場合には(N+1)回の計測で判定できる。（定理5参照）

以上でこの問題は完全解決を見ました。おめでとう！！

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

さて、まだもうちょっと終わらないです。

標準問題において、N回の計測で判別できる最大個数については、解決したとしても、「完全な解決」と言うために残されている問題があります。

「正常なおもりを借りてくることなく、N回の計測で丁度K個のおもりを判別する手順を求む。ただし
(3^N-1)/2 ≧K＞(3^(N-1)-1)/2
である。」

です。(3^N-1)/2 ＞K＞(3^(N-1)-1)/2のとき、stomachmanの証明では、定理2,3において（既に正常と分かったおもりのうちから）正常なおもりを使いますから、その際に正常なおもりが不足するかも知れませんし、またsiegmund先生の３進法もおもりの数が足りないとそのままでは成り立ちません。

なお、この問題についてはstomachmanはしばらくお休みします。

No.23 回答者： stomachman 回答日時： 2001/01/26 18:39

大団円。

になってくれると嬉しいけど....

定理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 である。」

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

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