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

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

No.12 回答者： siegmund 回答日時： 2001/01/24 01:18

nine さん，まだ締め切っちゃだめですよ．

もっと面白いことがいっぱい出てきそうですよ．

天秤の右，左，残り，で分類が３通りなのですから，
３進法の分類が見通しよく使えます．

stomachman さんの，「測定結果を見て次のおもりの乗せ方を変えるのはダメ」
でやってみましょう．
１２個なら３回で判定可能で，異常なおもりが重いか軽いかもわかります．

まず，１から１２までの３進表現を書いておきます．
このとき，１３を折り目にして折り返した数字同士
(12 と 14，11 と 15，など)は同一視しておきます．
で，最初の２桁の数字の変化が，
０→１→２のタイプのものを正回転，
０→２→１のタイプのものを逆回転，
と名付けておきます．
これは，異常なおもりが重いか軽いかの判別のためです．
逆回転の３進表現には＊をつけて表現することにして

10進 ３進正(重) ３進逆(軽)
------------------------------
1 ⇒ (001) ⇔ (221*)
2 ⇒ (220) ⇔ (002*)
3 ⇒ (010) ⇔ (212*)
4 ⇒ (011) ⇔ (211*)
5 ⇒ (012) ⇔ (210*)
6 ⇒ (202) ⇔ (020*)
7 ⇒ (201) ⇔ (021*)
8 ⇒ (200) ⇔ (022*)
9 ⇒ (122) ⇔ (100*)
10 ⇒ (121) ⇔ (101*)
11 ⇒ (120) ⇔ (102*)
12 ⇒ (112) ⇔ (110*)

正回転表現と逆回転表現では，
０と２が入れ替わっていること，１はそのままであること，
この２点がポイントです．に

で，天秤で１回はかるたびに，
３進表現の数字を１個ずつ決めようというわけです．

最初は，３進正回転表現の一番左の桁に注目し，
これが０のグループＧ(1,0)を取り出します．
Ｇ(p,q)の p は桁，q はその桁の数字です．
すなわち，G(1,0)の要素は１０進表現で
G(1,0) = {1,3,4,5} です．
同様に
G(1,1) = {9,10,11,12}
G(1,2) = {2,6,7,8}
です．
ここで G(1,0) と G(1,2) で天秤の１回目をはかります．
G(1,0) が重かったら，
G(1,0) の中に重いものがあるか，G(1,2) の中に軽いものがあるか，
どちらかです．
そうすると，３進表現の１桁目が０と確定します．
上の表を見てください．
G(1,0) = {1,3,4,5} のどれかが重い
⇒1,3,4,5 の３進正回転表現は１桁目が０
G(1,2) = {2,6,7,8} のどれかが軽い
⇒2,6,7,8 の３進逆回転表現は１桁目が０
つまり，重かった方のｑが異常おもりの３進表現の１桁目！
G(1,0) と G(1,2) が釣り合ったら，
G(1,1) の中に異常なものがある．
すなわち，１が異常おもりの３進表現の１桁目．

同様にして，２回目の天秤は
G(2,0) = {1,6,7,8}
G(2,2) = {2,9,10,11}
を比べて重い方のｑを書く．
これが異常おもりの３進表現の２桁目．
釣り合ったら，１が異常おもりの３進表現の２桁目
なお，天秤に乗せなかったものは
G(2,1) = {3,4,5,12}

３回目は
G(3,0) = {2,3,8,11}
G(3,2) = {5,6,9,12}
を天秤に乗せて，重い方のｑが異常おもりの３進表現の３桁目．
釣り合ったら，１が異常おもりの３進表現の３桁目
なお，天秤に乗せなかったものは
G(3,1) = {1,4,7,10}

実例をやってみましょう．
３番目のおもりが重かったとします．
このおもりは１回目は G(1,0) に含まれているから，１桁目は０
２回目は G(2,1) に含まれているから，２桁目は１
３回目は G(3,0) に含まれているから，３桁目は０
で，上の表で (010) を見ると，確かに３番目が重い！

３番目が軽かったら？
１桁目は２，２桁目は１，３桁目は２，
(210*) は３番目が軽いことを示している！

同じ理屈で，４回で３９個まで判定可能です．
Ｎ回なら，(3^N - 3)/2 個まで判定可能ですね．
これは，３進表現が (111・・・・・111) となる１個手前までということでもあります．
前に，４回で３６個というのがあったので，多少不安なんですが，
どこか間違えていないでしょうね．
４回の場合はいくつか確かめてはありますが.......

荒っぽく言えば，１回で３分類可能だから，
Ｎ回では N^3 分類可能，重い軽いがあるから
大体 N^3/2 に近いくらいでそんなにおかしくないですよね．
おもりの個数が３で割り切れないと分類精度が悪いわけで，
(3^N - 3)/2 は N^3/2 に一番近くて(小さい側で)３で割り切れる整数ですね．

No.11 回答者： stomachman 回答日時： 2001/01/23 22:12

●実は、この問題にはさらに変種があります。

「異常なおもりが１個だけ必ず混じっている。てんびんをＮ回使ってこれを見分けよ。ただし、各測定に際しててんびんの左右の皿にどのおもりを乗せるかはあらかじめ決めて置かねばならず、測定結果によって変えることは許さない。
最大何個までのおもりまで判別できるか。」

●punchan_jpさんの仰る情報量的アプローチは重要だと思います。
> 14個のうちの1個が異常であることに変わらないから、28通りある
というのは、「１４番目のおもりが正常であることが分かっている」という事の情報量を算入することで改良できそうに思われます。

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) 個
ですが、あんまり意味のない上限です。（でもこれを超えないとい
う保証はできますが）

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.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.7 回答者： stomachman 回答日時： 2001/01/23 04:24

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

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

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

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

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

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

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

◆Naka◆

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

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

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.3 回答者： noname#258 回答日時： 2001/01/21 15:38

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

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

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