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

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

No.1 回答者： sugamo 回答日時： 2001/01/21 15:06

まず、おもりを４個ずつに分けて、天秤に４個と４個をのせて、４個をのけておく。

てんびんの傾きでどの４個に重い１つが含まれているかわかるから、その重い４個を今度は２個ずつに分けててんびんにのせて、さらに重いほうを１個ずつに分けてのせる。以上
つまり天秤が２つと思う概念を捨てよ！

No.2 回答者： ryouchi 回答日時： 2001/01/21 15:27

下記URLにその過程が記載しています。

よんでいて、「うーむなるほど」とおもいました。

参考URL：http://www.platz.or.jp/~takase/lesson/answer_1.h …

No.3 回答者： noname#258 回答日時： 2001/01/21 15:38

一所懸命考えて、やっと解けたと思ったら……ryouchiさんから

解答へのリンクが……（＾＾；　ちょっと遅かったですね。

ところで、最初のsugamoさんのお答えは違っているように思います。
１つだけ違うおもりが“重い”とは決まっていませんし？

No.4 回答者： stomachman 回答日時： 2001/01/21 17:53

ホントになめてはいけないなぁ・・・

結論：３回測って良いなら、１３個まで判定可能です。


どこまでがんばれるのか、ちょっと系統的にやってみました。
●１回の比較
(1)ひとつが異常だと分かっていれば、１回で２個(1,2)を調べられる。
　正常とわかっているものxを使って、1とxを比べ、釣り合えば2、違えば1が異常です。
(1*)ひとつが異常で、異常なのが重いか軽いかわかっていれば、１回で３個(1,2,3)を調べられる。
　仮に重いと分かっているなら、
　1と2を比べ、
　釣り合えば3が異常。
　1が重ければ1が異常。、
　1が軽ければ2が異常です。軽いと分かっている場合も同様ですね。
●２回の比較
(2) ひとつが異常だと分かっていれば、２回で５個を調べられます。
　1,2,3と正常の３個を比べる。
　釣り合えば、これらは正常なので4,5を(1)で判定。
　釣り合わなければ、1,2,3を(1*)で判定。
(2*) ひとつが異常で、異常なのが重いのか軽いのかわかっていれば、２回で９個を調べられる。
　仮に重いと分かっているなら、
　1,2,3と4,5,6を比べ、
　釣り合えば7,8,9を(1*）で判定。
　釣り合わなければ重い方３個を(1*)で判定。軽いと分かっている場合も同様ですね。
(2h) 半分のうちに重いのがあるか、あるいは残り半分のうちに軽いのがある。と分かっている場合には、２回で8個まで判定できます。例えば「1-4の中に重いのがあるか、あるいは5-8のうちに軽いのがある」とします。このとき正常のもの３個を使います。
4,5,6,7と（8および正常３個）を比べ、
　釣り合えば、乗せてない3個(1,2,3のどれかが重い）を(1*)で判定。
軽ければ5,6,7のどれかが軽いので、(1*)で判定。
　重ければ4が重いのか,8が軽い訳ですから、(1)で判定します。
●３回の比較
(3) ひとつが異常だと分かっていれば、３回では5+9　= 14個まで調べられます。
　1-9と正常の9個を比べ、釣り合えば10-14を(2)で判定。
　1-9が重いか軽いか分かれば、(2*)で判定。
　しかしこの手を使うには正常なおもりが余分にいりますね。

(3#)さて、ひとつが異常だと分かっていて、しかも正常のおもりが手に入らない場合に、３回では5+8=13個まで調べられます。
　1-4と5-8を比べます。
　釣り合えば1～8は正常とわかり、これら８個を正常のおもりとして利用して9-13を(2)で判定。
　釣り合わなければ、9-13の５個が正常とわかったので、1-4と5-8を(2h)で判定します。

と言うわけで、問題の場合には、(3#)を使うことが出来ます。１度目の比較で釣り合った場合には、13番目のおもりの代わりに１番目のおもりを使っておけばよいです。

あれ疑ってるな？手順として整理しますね。１３個を判定する手順。
<1-4>と<5-8>を比べる。
　　釣り合ったら、<9-13>の一つが異常とわかります。<9,10,11>と<1,2,3>（これらは正常）を比べます。
　　　　釣り合ったら、12,13のどっちかが異常ですから、<12>と<1>を比べます。
　　　　　　釣り合ったら、13が異常。釣り合わなければ12が異常です。
　　　　<9,10,11>の方が重かったら、この中に重いのがあります。<9>と<10>を比べます。
　　　　　　釣り合ったら、11が重い。釣り合わなければ、重かったやつ(9か10)が重い。
　　　　<9,10,11>の方が軽かったら、この中に軽いのがあります。<9>と<10>を比べます。
　　　　　　釣り合ったら、11が軽い。釣り合わなければ、軽かったやつ(9か10)が軽い。
　　<1-4>が重かったら、<1-4>が重いのか<5-8>が軽い。<4,5,6,7>と<8,11,12,13>を比べます。
　　　　釣り合ったら、<1,2,3>の中に重いのがある。<1>と<2>を比べます。
　　　　　　釣り合ったら<3>が重い。釣り合わなければ、重かったやつ(1か2)が重い。
　　　　<4,5,6,7>が重かったら、4が重いのか、あるいは8が軽い。<4>と<13>を比べます。
　　　　　　釣り合ったら8が軽い。釣り合わなければ4が重い。
　　　　<4,5,6,7>が軽かったら、5,6,7の中に軽いのがある。<5>と<6>を比べます。
　　　　　　釣り合ったら7が軽い。釣り合わなければ、軽かったやつ(5か6)が軽い。
　　<1-4>が軽かったら、<1-4>が軽いのか<5-8>が重い。<4,5,6,7>と<8,11,12,13>を比べます。
　　　　釣り合ったら、<1,2,3>の中に軽いのがある。<1>と<2>を比べます。
　　　　　　釣り合ったら<3>が軽い。釣り合わなければ、軽かったやつ(1か2)が軽い。
　　　　<4,5,6,7>が軽かったら、4が軽いのか、あるいは8が重い。<4>と<13>を比べます。
　　　　　　釣り合ったら8が重い。釣り合わなければ4が軽い。
　　　　<4,5,6,7>が重かったら、5,6,7の中に重いのがある。<5>と<6>を比べます。
　　　　　　釣り合ったら7が重い。釣り合わなければ、重かったやつ(5か6)が重い。

もうちょっと頑張れば、14個でもいけそうな気もするんですが...

この回答へのお礼

すばらしい考察ありがとうございました。
さらにどこまでやれるか考えてくださるなんて、とてもうれしいですし、
そういったことを実際にできてしまうstomachmanさんがうらやましいです。

お礼日時：2001/01/21 19:21

No.5 回答者： Naka 回答日時： 2001/01/22 12:17

◆Naka◆

過去の質問で、「36個で４回」という問題がありましたので、そちらもご参考までにごらんください。

参考URL：http://oshiete1.goo.ne.jp/kotaeru.php3?q=3528

No.6 回答者： papua 回答日時： 2001/01/22 21:53

これは裏ワザですが、おもりの数がいくつでも、2回あれば見分ける事ができますよ(^_^)

１回目：てんびんの両側におもりを一個づつ順番にのせていき、てんびんが傾いたら、最後にのせた両側のおもりを取り出す。
2回目：取り出したおもりの一方を、その他大勢のおもりの一個と一緒にてんびんにのせる。それが傾いたら、てんびんにのせた側のおもりが、つり合ったら、のせなかった側のおもりが、重さの違うおもりです。

No.7 回答者： stomachman 回答日時： 2001/01/23 04:24

Nakaさん < ご紹介のQA、わいわい楽しそう。

「４回で最高何個まで判定できるか」「Ｎ回では？」って問題は、どうするんでしょう？

　３回だと、「もし正常なおもりをあと１個貸してくれるンなら、１４個まで、判定できる。」というのがどうも限界のようです。

No.8 回答者： Naka 回答日時： 2001/01/23 05:14

◆Naka◆

出たな～、stomachmanさんの「絡み」が！
寝ようと思ってたのに、もう… (^o^)

私も３回では13個までしかできませんでした。
４回では最高何個まで可能かと言うと、最初に３つに分けた各ブロックが13個までＯＫで39個まで可能かと思ったんですが、２回目に８個対８個で量ったときに、釣り合ったら没になるんですね。
38個でも、３回目の結果によってはダメ。（詳細は省略）

そうすると、結局37個で、最初に12個同士を天秤にかけるのが限界かと。
だったらＮ回で「4/3×3^(N-1)+1」（ただしN>=2） ？？？？？ （ホンマかいや…）
どうやって証明しよう… (T_T)
とりあえず、寝よう…

No.9 回答者： punchan_jp 回答日時： 2001/01/23 17:10

n個のおもりがあって少しだけ重さの違うものが確実に1個まぎれて

いる場合、それぞれのおもりをちゃんと区別できるなら 2n 通りの
場合が存在します。通常はそれらの確率は等しいとできますので、
この状況が持つ平均情報量は log_2 (2n) ビットと表せます。

これに対して、天秤でおもりを同数ずつ乗せた場合、左に傾くか、
右に傾くか、つりあうかの3通りの場合があります。それぞれの場
合を構成する場合の数を等しくできるならば、つまり、1回計るこ
とによって、可能性を正確に1/3に限定できるように分けられるな
ら、log_2 3 ビットだけの情報量が得られます。

つまり、理想的な分け方ができる限り、
ceiling(log_2 (2n) / log_2 3) = ceiling(log_3 (2n)) 回で重さ
の違うおもりを見分けられることがわかります。これが回数の理論
的な下限といえます。（ceiling は切り上げの意）

n=14では、この値は4になりますので、3回では不可能であることが
証明されます。n=40でも4なので、もしうまい分け方があれば4回で
検出できますが、それは情報量の観点のみからでは保証されません。

No.10 回答者： punchan_jp 回答日時： 2001/01/23 20:42

stomachman さんの方法で、1個正常なのがあれば14個まで判別でき

るとあります。しかし私が下に書いた情報量の観点からの計算では、
14個のうちの1個が異常であることに変わらないから、28通りある
わけですが、log_3 28 > 3 で3回では判別できないことと矛盾しま
す。

これがなぜかと思って、stomachman さんの方法をよく見たところ、
1回で2個のうちの異常を判別できるというところに矛盾が帰着され
てしまうようです。この方法では、異常のあるおもりが重いのか軽
いのかが不明となる可能性があります。最終的に平均情報量が0に
ならなくてもよいという立場の場合にはこれでOKなわけですね。

異常であるものは特定できたが、重いか軽いかわからないという場
合は2通りですから、この状況での各場合の平均情報量は1ビットで
す。とすると、さきほどの下限値の計算では、
ceiling(((log_2 (2n)) - 1) / log_2 3) = ceiling(log_3 n) 回
となりますね。しかし、これでは下限値が小さくなりすぎて、あん
まり役に立たないかもしれません。それは、1個について重いか軽
いかわからないという場合だけでなく、2個について、どちらが重
いかはわかるけれど、どちらが正常かわからないという状況でもOK
とカウントしてしまうためです。

情報量のアプローチでは限界がありますね。

ちなみに、N回の比較が許された場合、扱えるおもりの個数の上限
値は、式を変形して
floor(3^N / 2) 個
となります。重いか軽いかわからなくていいなら、
floor(3^N) 個
ですが、あんまり意味のない上限です。（でもこれを超えないとい
う保証はできますが）