締切済み

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

  • すぐに回答を!
  • 質問No.30706
  • 閲覧数2222
  • ありがとう数64
  • 気になる数2
  • 回答数32
  • コメント数0

お礼率 3% (1/32)

12個のおもりがあって、そのうち1つだけ重さの違うおもりがまぎれています。
それを、てんびんを3回だけ使って見分ける方法を教えてください。
ただし、重さの違うおもりは他のおもりより重いか軽いかわかりません。
わかった方は至急おしえてください。おねがいします。
通報する
  • 回答数32
  • 気になる2
    質問をブックマークします。
    マイページでまとめて確認できます。

回答 (全32件)

  • 回答No.11
レベル14

ベストアンサー率 57% (1014/1775)

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

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

  • 回答No.10
レベル11

ベストアンサー率 55% (155/280)

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
レベル11

ベストアンサー率 55% (155/280)

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.12
レベル13

ベストアンサー率 64% (700/1089)

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で割り切れる整数ですね.
  • 回答No.13
レベル14

ベストアンサー率 57% (1014/1775)

元の問題の条件(標準問題)において、
K(n):異常が重いか軽いか分かっていて、n回で判定できる最大個数
L(n):異常としか分からなくて、n回で判定できる最大個数(ただし正常1個を借りる)
L'(n):異常としか分からなくて、n回で判定できる最大個数(ただし正常1個を借りない)

とすると、
K(n) = 3^(n-1) は自明でしょう。そして、システマティックなやり方で、少なくとも
L(n) = K(n-1)+L(n-1)、
L'(n) = L(n)-1
とできます。したがって、L(0)=1を用いると、
L(1)=1+1 = 2
L(2)=3+2 = 5
L(3)=9+5 = 14
L(4)=27+14=41
L(5)=81+41=122
となります。だから、Nakaさん、4回で判定できる最大個数は少なくとも L(4)-1=40個だと思います。
 このやり方の詳細は、ちょっと待って(いや、もちろん誰か書いちゃってもいいです。)

 siegmund先生の(計測手順固定の問題における)きれいな解析は、40個以下なので問題なさそう。という事になります。
  • 回答No.15
レベル14

ベストアンサー率 57% (1014/1775)

余分の正常なおもりがあればCeiling(3^N/2), なければFloor(3^N/2)というのが予想になってきたみたいですね。

punchan_jpさんの与えられた上限Floor(3^N/2)は「異常なのが重いか軽いかまで判定する」という条件付きですから、まだホントの上限は分かっていない。

それにしても、手順を固定して、さらに異常なのが重いか軽いかまで決める、という条件を追加しても、なお判定できる最大個数が1個しか増えないというのは、実に面白いと思いませんか?
  • 回答No.14
レベル13

ベストアンサー率 64% (700/1089)

私の3進法方式が正しいとすると,
もともとの標準問題
「手順非固定,異常おもりの軽重は判定しなくて良い」で,
4回で40個までOKなのは具体的手順と共に簡単に示せます.

最初の天秤のときに,G(1,1)のグループに40番目を
入れておけばいいのです.
40の3進表現は (1111) ですから,分類上もちょうどよい.
で,G(1,0) と G(1,2) を比べる.

(A) 天秤が傾いた場合.
天秤に乗せなかったグループ {G(1,1)+40番目} は正常ですから,
40番目を取り去ってしまって差し支えない.
あとは前の手順通りで,この場合は異常おもりの軽重まで判定できます.

(B) 天秤が釣り合った場合.
天秤に乗せなかったグループ {G(1,1)+40番目} に異常おもりがあります.
したがって,
【3回で14個,ただし正常おもりが与えられている】
に帰着します.
これは stomachman さんが言われるように,判定可能です.

したがって,標準問題は4回で40個まで可能なことが
具体的手順と共に示されました.

これは Naka さんが書かれている上限 floor(3^4 / 2) ですから,
40個が限界でしょう.

stomachman さん,書いちゃいました,ごめんなさい.
  • 回答No.8
レベル13

ベストアンサー率 44% (527/1181)

◆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)
とりあえず、寝よう…
  • 回答No.7
レベル14

ベストアンサー率 57% (1014/1775)

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

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

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

ベストアンサー率 41% (52/125)

下記URLにその過程が記載しています。
よんでいて、「うーむなるほど」とおもいました。
32件中 1~10件目を表示
このQ&Aのテーマ
このQ&Aで解決しましたか?
AIエージェント「あい」

こんにちは。AIエージェントの「あい」です。
あなたの悩みに、OKWAVE 3,500万件のQ&Aを分析して最適な回答をご提案します。

関連するQ&A
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する

特集


抽選で合計100名様にプレゼント!

ピックアップ

ページ先頭へ