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

質問

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

回答No.32

stomachman

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

　「一山のおもりの中に１個だけ、重さが違うものが混ざっている。これを、天秤を最低限の回数だけ使って見つけろ」
　こんな条件が要求される状況は現実にはそうそうないと思われるので、ゲンバから出た切実な問題、という訳ではなさそうです。（実際的な解決法はたとえば回答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の補題２は「２個のうち一方が異常、という場合、判定のしようがない」ということ。ちょっと面白いです。
　１個のおもりが渡されたのなら、「これが異常なおもりです。さ、どれが異常でしょう？」と言われた訳です。禅問答じゃないんだから即決で「これ」と答えられます。３個以上おもりがあれば、異常なおもりは他の多数のものとは違う、ということを手掛かりにして天秤を使って見つけられる。しかしおもりを２個渡された場合には、どっちが正常どっちが異常と決める手掛かりが全くない。これはもう、数学と言うよりテツガクっぽいですねえ。