最新閲覧日:

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

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

A 回答 (32件中21~30件)

nine さん,まだ締め切っちゃだめですよ.


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

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

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

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

10進 3進正(重) 3進逆(軽)
------------------------------
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*)

正回転表現と逆回転表現では,
0と2が入れ替わっていること,1はそのままであること,
この2点がポイントです.に

で,天秤で1回はかるたびに,
3進表現の数字を1個ずつ決めようというわけです.

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

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

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

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

3番目が軽かったら?
1桁目は2,2桁目は1,3桁目は2,
(210*) は3番目が軽いことを示している!

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

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

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


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

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

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

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回で
検出できますが、それは情報量の観点のみからでは保証されません。
    • good
    • 0

◆Naka◆


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

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

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

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



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

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

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


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

◆Naka◆


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

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

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


結論:3回測って良いなら、13個まで判定可能です。


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

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

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

あれ疑ってるな?手順として整理しますね。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個でもいけそうな気もするんですが...
    • good
    • 0
この回答へのお礼

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

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

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


解答へのリンクが……(^^; ちょっと遅かったですね。

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

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

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

このQ&Aを見た人はこんなQ&Aも見ています

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


このQ&Aを見た人がよく見るQ&A

このカテゴリの人気Q&Aランキング

おすすめ情報

カテゴリ