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

質問

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

回答No.12

siegmund

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 に一番近くて(小さい側で)３で割り切れる整数ですね．