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

このQ&Aに関連する最新のQ&A

A 回答 (32件中1~10件)

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



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

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

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

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

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

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

siegmund です.



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

天秤問題。

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

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

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

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

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

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

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

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

●定理5(標準問題の判定手順~その1)
N≧1のとき、正常と分かっているおもりがなくても、「この中に異常なものが1個ある」と分かっているおもり(3^N-1)/2個(この集合をXとする)は、N回の測定で判定できる。
●証明:
★N=1の場合
Xは(3^N-1)/2=1個のおもりからなる。測定をしなくても、そのおもりが異常であることがわかる。ゆえに高々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であり、正常と分かっているおもりが少なくとも1個あり、Xc((3^(N-1)+1)/2個)の中に異常なものが1個ある」と分かったのだから、定理4を適用できる。
☆もし天秤が傾けば
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個の中に重いものはなく、どちらかに異常なものが1個ある」と分かったのだから、定理3を適用できる。
いずれにせよ、あとN-1回の測定で判定できる。ゆえに都合N回の測定で判定できる。
(証明終わり)

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

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

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

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

 すると手順P’によって、N回の測定でM+1=(3^N+3)/2個のおもりが判定できる。なぜならば、手順P’の1回目の測定において、
☆もし天秤が釣り合ったら
天秤に乗せなかった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個のおもりの中に異常なものが1個ある」と分かるから、系4-1が適用でき、高々(N-1)回の測定で判定できる。つまり、都合N回の測定で判定できる。
☆もし天秤が傾いたら
天秤に乗せなかった(3^(N-1)+1)/2個のおもりは全部正常だとわかるから、追加した1個のおもりもまた正常である。従ってこのおもりを取り除けて、判定手順Pをそのまま続ければ都合N回で判定できる。

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

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

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

★[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個のおもりの中に異常なものが1個あると分かっている」ので、系4-1が適用でき、高々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個)の中に重いものはなく、これらの内に異常なものが1個ある」と分かったので、定理8を適用でき、高々(N-1)回の計測で判定できる。
・もし右が下がれば、
「Laの中に軽いものがある」と分かる。つまり、「(N-1)≧1であり、正常と分かっているおもりが少なくとも1個あり、La((3^(N-1)+1)/2)個の中に異常なものが1個ある」と分かるので、定理4を適用でき、高々(N-1)回の計測で判定できる。
・もし釣り合えば、
「Haの中に重いものがある」と分かる。つまり、「(N-1)≧1であり、正常と分かっているおもりが少なくとも1個あり、Ha((3^(N-1)+1)/2)個の中に異常なものが1個ある」と分かるので、定理4を適用でき、高々(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個)の中に重いものはなく、これらの内に異常なものが1個ある」と分かるので、定理8を適用でき、高々(N-1)回の測定で判定できる。
・もし右が下がれば、
「La(3^(N-1)個)の中に軽いものがある」と分かるから、定理1を適用でき、高々(N-1)回の測定で判定できる。
・もし釣り合えば、
「Ha(3^(N-1)個)の中に重いものがある」と分かるから、定理1を適用でき、高々(N-1)回の測定で判定できる。
従って、いずれにせよ都合高々N回の測定で判定できる。
(証明終わり)

●定理9(標準問題の判定手順~その2)
N≧2であり、(3^N-1)/2>M>(3^(N-1)-1)/2、M≠2であるとき、正常と分かっているおもりがなくても、「この中に異常なものが1個ある」と分かっている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回の測定で判定できる。

★[2] N≧3の場合
☆M=(3^(N-1)+1)/2の場合
左右の皿に1個ずつおもりを乗せる。
・天秤が傾いた場合、
上がった皿に乗せた1個は重いものではなく、下がった皿に乗せた1個は軽いものではなく、これら2個の中に異常なものが1個あり、残り(3^(N-1)-3)/2個は正常なおもりであることが分かった。
N≧3より、(3^(N-1)-3)/2≧3であるから、正常と分かっているおもりが少なくとも3個ある。ゆえに定理3が適用でき、高々1回の測定で判定できる。つまり都合高々2回の測定で判定できる。
・天秤が釣り合った場合、
天秤に掛けた2個は正常であり、天秤に掛けなかった残り(3^(N-1)-3)/2個の中に異常なものが1個あることが分かった。そこで、正常だと分かっているおもり1個を、天秤に掛けなかったおもりに加えて(3^(N-1)-1)/2個にする。すると定理5が適用でき、高々(N-1)回の測定で判定できる。
いずれにせよ、都合高々N回の測定で判定できる。
☆(3^N-1)/2>M>(3^(N-1)+1)/2の場合
1回目の測定で天秤に乗せないおもりの数をQとする。そして1回目の測定で左右の皿にそれぞれ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個ずつおもりを乗せて1回目の測定を行う。
・天秤が釣り合った場合、
天秤に乗せなかったおもりQ個の中に異常なものがある。
正常と分かっているおもりが少なくとも2A個(2A>1)ある。天秤に乗せなかったおもりQ個に対して定理4(Q=(3^(N-1)+1)/2の場合)か定理5(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個については「この中に軽いものはない」と分かっており、これらの中に異常なおもりが1個あることが分かっている。そこで定理8が適用でき、高々(N-1)回の測定で判定できる。だから都合高々N回の測定で判定できる。
(証明終わり)

●系9-1
(3^N-1)/2≧M>2であるとき、正常と分かっているおもりがなくても、「この中に異常なものが1個ある」と分かっているM個のおもりを高々N回の測定で判定できる。
●証明:
★N≦1の場合、
(3^N-1)/2≧M>2を満たすMは存在しない。ゆえに系9-1は真である。
★N≧2であって、M=((3^K)-1)/2 (1≦K≦N)となるKが存在する場合、
定理5によって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であり、「この中に異常なものが1個ある」と分かっているM個のおもりがある」のだから、定理9が適用でき、高々K回の測定で判定できる。だから高々N回の測定で判定できる。
(証明終わり)

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

●系1
天秤を最大3回使って判定できるおもりの個数は1,3,4,5,…,13である。
●証明:最終定理より自明。
●系2
天秤を最大3回使っても判定できないおもりの個数の最小値は2である。
●証明:最終定理より自明。
    • good
    • 0

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


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

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

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

誰か,天秤問題HPなんて作らんかな~.

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

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

雑談で失礼しました.
    • good
    • 0

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

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

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

「(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です。

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

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

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

【証明】
[1]N=1の場合。
つまり正常なおもりが少なくともq=1個あって、A=1のときです。
右の皿に正常なおもり1個、左の皿に「この中に重い物はない」と分かっているおもり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)個あれば、定理3によって(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の中に重いのはなく、これらの内に異常な物が1個ある」ので、これらに定理Xを適用すれば(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の中に重いのはなく、これらの内に異常な物が1個ある」ので、これらに定理Xを適用して(N-1)回で判定できる。
もし右が下がれば、「Laの中に軽いのがある」から、Laに定理1を適用して(N-1)回で判定できる。
もし釣り合えば、「Haの中に重いのがある」から、Haに定理1を適用して(N-1)回で判定できる。
従って、N回で判定できます。
 さて、必要な正常なおもりは3^(N-1)個であり、q≧3^(N-1)であるから、正常なおもりが不足することはありません。
(証明終わり)

これで完璧かな?
    • good
    • 0

stomachman さん,お久しぶりです.


siegmund です.

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

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

うー。

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

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

[A]始めにN=1の場合を考えます。すなわち
4 > K > 1
つまりK=2か3です。
K=2の場合には判定は不可能です。天秤は必ず傾きますが、どっちが異常なのか決められません。
K=3なら定理1で2回で判定可能。
ついでにK=4なら、N=2とした場合の定理5によって、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の場合、
最初の1回の計測において、天秤の左右の皿にそれぞれ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個のおもりに、必要ならあと1個正常と分かったおもりを加えて(3^N-1)/2個にし(K > (3^N-1)/2だから必ずこれは可能です)、そして
定理5:余分の正常なおもりを借りられなくても、「この中に異常な物が1個ある」と分かっているおもり(3^N-1)/2個(この集合をXとする)の内から、N回の測定で異常なおもりを特定できる。(N≧1)
を使うとN回で計測が可能になります。最初の1回の計測と合わせて(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とする)の中に異常な物が1個ある場合、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回で判定が可能であり、最初の1回と合わせて(N+1)回で判定できました。

また、(3^N-1)/2= Kの場合にN回で判定する手順は定理5に示されています。
以上をまとめると、
・K=1個の場合には測定なしで判定できる。
・K=2個の場合には判定が不可能である。
・K=3個の場合には高々2回の計測で判定できる。(定理1参照)
・K=4個の場合には高々2回の計測で判定できる。(定理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になるようにし、定理5を適用。
(b)もし釣り合わなかったら、定理3を適用。
です。
K=(3^(N+1)-1)/2の場合には(N+1)回の計測で判定できる。(定理5参照)

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

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



標準問題において、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先生の3進法もおもりの数が足りないとそのままでは成り立ちません。

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

大団円。

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

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

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


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

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

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

補題1より、1回目の計測で天秤に乗せないで済むおもりの数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
でなくてはならない。すると1回目の計測で天秤にかけるおもりの個数は
2W ≧(3^(N-1)+1
従って、天秤に掛けないおもりの数Qは
Q=M-2W ≦{3^(N-1)-1}/2
ですね。これは確かに補題1の上限を満たしています。それどころか、上限より1個少ない。

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

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

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

以上から、

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

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

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

このQ&Aに関連する人気のQ&A

1  2  3  4 次の回答→

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Qリンゴ1個の重さはミカン一個の重さの3倍で、リンゴの方が100グラム多いです。リンゴの1個の重さはな

リンゴ1個の重さはミカン一個の重さの3倍で、リンゴの方が100グラム多いです。リンゴの1個の重さはなんグラムですか?

とゆう、娘の宿題が分かりません。

答えを教えて下さい

Aベストアンサー

関係を図にしてみましょう。
ミカン2個分が100グラムだとわかります。
ミカンは1個は50グラム、リンゴは150グラムです。

Q選ばれた5個の数字のうち3個だけあたる確率

1から50までの数字のうち、5個の数字が当選番号として選ばれます。
その数字のうち3個だけ当たる確率というのは、
どのように計算すればいいのでしょうか?
5個の数字すべてが当たる確率は
1/50*49*48*47*46 (50*49*48*47*46分の1ということです。)
だと思うのですが、3個だけというのは2個は外れてもいいので、
1/50*49*48
だと違う気がするんですが・・・
(3/48)*(2/47)*(1/46)でしょうか???
よろしくお願いします。

Aベストアンサー

「1~50までの整数の中から,5つの当選番号が選ばれる.今,5つの整数を選んだときに,その中の3つだけ当たる確率はいくつか」という質問でよろしいでしょうか.
以下,そのような前提で解説しますね.

例えば,質問者さんが1,2,3,4,5の5つの数を選んだとします.
このとき,1,2,3が当たりで4,5が外れの確率は,
(1があたり)*(2もあたり)*(3もあたり)*(4ははずれ)*(5もはずれ)
=(5/50)*(4/49)*(3/48)*(45/47)*(44/46)
となります.これを(A)としますね.

ところで,3つだけ当たるパターンとしては,例えば1,2がはずれで,3,4,5が当たりという別のパターンも考えられますよね?このような「別のパターン」がどのくらいあるのかも考えなければなりません.

では,5つの数字の中から「あたり」になる3つの数字を取り出す場合の組み合わせの数を考えましょう.
まず,5つの数字から「順番を考えて」3つの数字を取り出す場合には,5つの数字の中から第一の数を選んで,次に残りの4つの数字の中から第二の数を選んで,残りの3個の数の中から第三の数を選べばよいのですから,
5*4*3
だけの組み合わせがあります.しかし,これは「1,2,3」と「2,3,1」を別のものとして考えた場合ですよね.だから,このような「順番違い」のパターンを消さなくてはなりません.順番違いのパターンは,選ばれた3つの数字の並び方が何通りあるかを確認すればよいことになります.これは,先ほどと同様に考えて,
3*2*1
だけの順番があります.だから,「順番違い」も同じ組み合わせだと考える場合には,「順番を考えた」組み合わせの数を「順番違いのパターン」の組み合わせの数で割ってやって,
(5*4*3)/(3*2*1)
通りの組み合わせがあることになります.これを(B)とします.
(何故割るのかが納得いかない場合には,1~5の数字から3つ組み合わせるパターンを全て書き出して見てください.とりあえず,割るので正しいことをご理解いただけると思います.)

「あたりが3個だけ」の確率は,「ある特定の3個だけがあたる確率」=(A)と,「その特定の3個の選び方の数」=(B)を掛け合わせた数になります.
従って,
(5/50)*(4/49)*(3/48)*(45/47)*(44/46)*(5*4*3)/(3*2*1)
が答えとなり,おおよそ0.47%と非常に低い確率となります.

以上から,#1さんのご回答は誤り,ということになります.
#2さんのご指摘は正しいものです.

「1~50までの整数の中から,5つの当選番号が選ばれる.今,5つの整数を選んだときに,その中の3つだけ当たる確率はいくつか」という質問でよろしいでしょうか.
以下,そのような前提で解説しますね.

例えば,質問者さんが1,2,3,4,5の5つの数を選んだとします.
このとき,1,2,3が当たりで4,5が外れの確率は,
(1があたり)*(2もあたり)*(3もあたり)*(4ははずれ)*(5もはずれ)
=(5/50)*(4/49)*(3/48)*(45/47)*(44/46)
となります.これを(A)としますね.

ところで,3つだ...続きを読む

Q数字の問題で「あるバネに10gのおもりを下げたらバネの長さが24㎝になり、15gのおもりを下げたら2

数字の問題で「あるバネに10gのおもりを下げたらバネの長さが24㎝になり、15gのおもりを下げたら26㎝になった。バネの伸びがおもりの重さに比例するとして、次の問いに答えなさい。 1 ) xgのおもりを下げたときのバネの長さをy㎝として、yをxの式で表しなさい 2 ) 5gのおもりを下げると、バネの長さは何㎝になるか? 3 ) バネの長さが30㎝になるのは、何gのおもりを下げたときか?」わかる方教えて下さい。 見辛くてすいません

Aベストアンサー

こういう問題は、「日本語の文章を、数式に直して考える」訓練だと思ってください。
数式に直して愚直に計算すれば、必ず解けるようになっています。

1)「バネの伸びがおもりの重さに比例する」ということから、
y=ax+b...a,bは定数
と表されます。
x=10のときy=24、またx=15のときy=26より、

24=10a+b ...(1)
26=15a+b ...(2)
(2)-(1)より、
2=5a
よってa=0.4...(3)
(3)を(1)に代入することで
24=10*0.4+b
b=20
よって、y=0.4x+20
と表されます。

Q柿2個、りんご4個、みかん6個の中から6個を取り出す方法は何通りあるか

柿2個、りんご4個、みかん6個の中から6個を取り出す方法は何通りあるか?ただし、取り出されない果実があっても良い。

この問題が分かりません。

Aベストアンサー

質問者様がこの問題が分からないように私にもこの問題が何を問うものなのかが分かりません。
『6個を取り出す方法は何通りあるか?』だけでは、回答出来ないですね。
おそらく他に何かの条件が有るのだと思いますので、それを記載してほしいです・・・。

Q白球5個、赤球2個、黒球3個の計10個を2組に分ける方法は何通りか

白球5個、赤球2個、黒球3個の計10個を2組に分ける方法は何通りか
まず、白球5個は(5,0)、(4,1)、(3,2)の3通りに分けられると考えました。
次に白球5個を(5、0)に分けた場合、赤球2個は(2,0)、(1,1)、(0,2)の3通り、黒球3個は(3,0)、(2.1)、(1,2)、(0,3)の4通りに分けられるので、計12通りに分けられると考えました。同様に、白球5個を(4,1)、(3,2)に分けた場合も赤球2個と黒球3個をそれぞれ計12通りに分けられるので、最終的に白球5個、赤球2個、黒球3個の計10個を36通りに分けられると考えました。
しかし、間違っているようです。どこか間違っているのか分かりません。アドバイスいただければと思います。よろしくお願い致します。

Aベストアンサー

10個と0個に分けた場合は2組に分けたとは言わないのでは?

答えは35通りではないですか。


人気Q&Aランキング

おすすめ情報