第１問（２）の解答
１．問題
| （１）１２個のおもりがあります。このうち、１個だけ他のおもりと重さが異なるものがあります。天秤を利用して何回かおもりを量り、どのおもりが他と異なるかを見つけて下さい。 さて、おもりを量る回数をできるだけ少なくするとして、最大何回量ればいいでしょうか。 また、その具体的な量り方を考えて下さい。 （２）７回まで量ることができるとします。このとき、最大何個のおもりのなから１個だけある重さの異なるものを見つけることができるでしょうか。 |
２．設問（２）
一般におもりがｍ個のとき、いずれかのおもりが重いあるいは軽いのｍ×２通り可能性があります。ところが、ｎ回はかることで、３ｎ通りの状態を区別することができるので、ｍ×２≦３ｎとなります。３ｎは奇数なので、結局ｍ≦（３ｎ−１）／２となります。
ところが、効率的にはかることで、（３ｎ−１）／２個のおもりの中から異なるものを判定することができることを示せますので、最大個数は（３ｎ−１）／２個となります。
ｎ＝７のときは、（３７−１）／２＝１０９３個です。
一般には数学的帰納法で証明できますが、ここでは７個の場合を具体的に示してみましょう。
（おもりが７個の場合）
１回目に左右に載せることができる最大個数ｍは、もし天秤が傾いたときにｍ×２通りの場合が考えられ、残りの６回で３6＝７２９通りの状態が判定できることからｍ×２≦７２９、ｍ≦３６４個となります。
・１回目：１〜３６４のおもりを左、３６５〜７２８のおもりを右に載せ（計７２８個）、７２９〜１０９３（３６５個）を残します。
・左が重いとき：１〜３６４が重いか３６５〜７２８が軽い（７２８通り）
・右が重いとき：１〜３６４が軽いか３６５〜７２８が重い（７２８通り）
・釣り合うとき：７２９〜１０９３が異なる（３６５通り）・・・「１回目に釣り合った場合」へ・２回目：
・左の天秤：重い可能性のある３６４個のおもりのうち１２２個と軽い可能性のある３６４個のおもりのうち１２１個。
・右の天秤：重い可能性のある３６４個のおもりのうち１２２個と軽い可能性のある３６４個のおもりのうち１２１個。
・残す：重い可能性のある３６４個のおもりのうち１２０個と軽い可能性のある３６４個のおもりのうち１２２個・左が重いとき：１２２個のどれかが重いか１２１個のどれかが軽い（２４３通り）
・右が重いとき：１２２個のどれかが軽いか１２１個のどれかが重い（２４３通り）
・釣り合うとき：１２２個および１２０個ののどれかが異なる（重いか軽いかは分かる）（２４２通り）
・３回目：（以下、前に釣り合ったときは個数が１個少なくてすむ）
・左の天秤：１２２個のおもりのうち４１個と１２１個のおもりのうち４０個。
・右の天秤：１２２個のおもりのうち４１個と１２１個のおもりのうち４０個。
・残す：１２２個のおもりのうち４０個と１２１個のおもりのうち４１個。・左が重いとき：４１個および４０個ののどれかが異なる（重いか軽いかは分かる）（８１通り）
・右が重いとき：４１個および４０個ののどれかが異なる（重いか軽いかは分かる）（８１通り）
・釣り合うとき：４１個および４０個ののどれかが異なる（重いか軽いかは分かる）（８１通り）・４回目：
・左の天秤：４１個のおもりのうち１４個と４０個のおもりのうち１３個。
・右の天秤：４１個のおもりのうち１４個と４０個のおもりのうち１３個。
・残す：４１個のおもりのうち１３個と４０個のおもりのうち１４個。・左が重いとき：１４個および１３個ののどれかが異なる（重いか軽いかは分かる）（２７通り）
・右が重いとき：１４個および１３個ののどれかが異なる（重いか軽いかは分かる）（２７通り）
・釣り合うとき：１４個および１３個ののどれかが異なる（重いか軽いかは分かる）（２７通り）・５回目：
・左の天秤：１４個のおもりのうち５個と１３個のおもりのうち４個。
・右の天秤：１４個のおもりのうち５個と１３個のおもりのうち４個。
・残す：１４個のおもりのうち４個と１３個のおもりのうち５個。・左が重いとき：５個および４個ののどれかが異なる（重いか軽いかは分かる）（９通り）
・右が重いとき：５個および４個ののどれかが異なる（重いか軽いかは分かる）（９通り）
・釣り合うとき：４個および５個ののどれかが異なる（重いか軽いかは分かる）（９通り）・６回目：
・左の天秤：５個のおもりのうち２個と４個のおもりのうち１個。
・右の天秤：５個のおもりのうち２個と４個のおもりのうち１個。
・残す：５個のおもりのうち１個と４個のおもりのうち２個。・左が重いとき：２個および１個ののどれかが異なる（重いか軽いかは分かる）（３通り）
・右が重いとき：２個および１個ののどれかが異なる（重いか軽いかは分かる）（３通り）
・釣り合うとき：１個および２個ののどれかが異なる（重いか軽いかは分かる）（３通り）・７回目：
・左の天秤：２個のおもりのうち１個。
・右の天秤：２個のおもりのうち１個。
・残す：１個のおもりのうち１個。・左が重いとき：１個が異なる（重いか軽いかは分かる）
・右が重いとき：１個が異なる（重いか軽いかは分かる）
・釣り合うとき：１個が異なる（重いか軽いかは分かる）
（１回目に釣り合った場合）残り３６５個
・２回目：残り３６５個のなかから２４３個のおもりを左、正しいおもりを２４３個右に載せ、１２２個を残します。
・左が重いとき：２４３個のどれかが重い
・右が重いとき：２４３個のどれかが軽い
・釣り合うとき：１２２個のどれかが異なる・・・「２回目に釣り合った場合」へ
・３回目：異なる（重いか軽いかは分かる）２４３個のなかから８１個のおもりを左、８１個を右に載せ、８１個を残します。（３分割法と呼ぶ）
・左が重いとき：８１個のどれかが異なる（重いか軽いかは分かる）
・右が重いとき：８１個のどれかが異なる（重いか軽いかは分かる）
・釣り合ったとき：８１個のどれかが異なる（重いか軽いかは分かる）以下、個数を３分の１づつに絞っていけるので、７回目で異なるおもりとそれが重いのか軽いのかまでが判定できる。
（２回目に釣り合った場合）残り１２２個
・３回目：残り１２２個のなかから８１個のおもりを左、正しいおもりを８１個右に載せ、４１個を残します。
・左が重いとき：８１個のどれかが重い（以下３分割法により後４回で分かる）
・右が重いとき：８１個のどれかが軽い（〃）
・釣り合うとき：４１個のどれかが異なる・・・「３回目に釣り合った場合」へ
（３回目に釣り合った場合）残り１２２個
・４回目：残り４１個のなかから２７個のおもりを左、正しいおもりを２７個右に載せ、１４個を残します。
・左が重いとき：２７個のどれかが重い（以下３分割法により後３回で分かる）
・右が重いとき：２７個のどれかが軽い（〃）
・釣り合うとき：１４個のどれかが異なる・・・「４回目に釣り合った場合」へ
（４回目に釣り合った場合）残り１４個
・５回目：残り１４個のなかから９個のおもりを左、正しいおもりを９個右に載せ、５個を残します。
・左が重いとき：９個のどれかが重い（以下３分割法により後２回で分かる）
・右が重いとき：９個のどれかが軽い（〃）
・釣り合うとき：５個のどれかが異なる・・・「５回目に釣り合った場合」へ
（５回目に釣り合った場合）残り５個
・６回目：残り５個のなかから３個のおもりを左、正しいおもりを３個右に載せ、２個を残します。
・左が重いとき：３個のどれかが重い（以下３分割法により後１回で分かる）
・右が重いとき：３個のどれかが軽い（〃）
・釣り合うとき：２個のどれかが異なる・・・「６回目に釣り合った場合」へ
（６回目に釣り合った場合）残り５個
・７回目：残り２個のなかから１個のおもりを左、正しいおもりを１個右に載せ、１個を残します。
・左が重いとき：左の１個が重い
・右が重いとき：左の１個が軽い
・釣り合うとき：残した１個が異なる（重いか軽いか分からない）
以上