同じ形、大きさをした12個の物体がある。見た目では区別をつけられないが、12個のうち１個だけ他と比べ

同じ形、大きさをした12個の物体がある。見た目では区別をつけられないが、12個のうち１個だけ他と比べて軽いものが混ざっている。上皿天秤を使い、その重さの違う1個を見つけ出す時、上皿天秤を最低何回使えば良いか。ただし、偶然わかった場合は最低回数にしないものとする。
解説に、N個のうち１個だけ軽いものが含まれている時、最小回数は3^n−1＜N＜3^nならばn回である。の意味がわからないです。なぜこのような式になるのでしょうか。

質問者からの補足コメント

• 答えは最小回数3回なのですが、どのようにしたら3回になるでしょうか。

    補足日時：2022/03/13 15:06

No.3 ベストアンサー 回答者： yhr2 回答日時： 2022/03/13 15:20

12個の場合には

(1) 4個ずつ、3つのグループに分ける。

(2) 3つのグループのうち、2つを天秤にかける。　　　←１回目

(3) 一方が軽ければ、その中に「軽いもの」がある。
　もし両方が同じ重さであれば、残ったグループに「軽いもの」がある。
　これで、どのグループに「軽いもの」があるか判明する。

(4) そのグループの4個のうち、2個を天秤にかける。　　　←２回目
　もし一方が軽ければ、それが「軽いもの」である。
　両方が同じ重さであれば、残った2個に「軽いもの」がある。

(5) 上で２回目が同じ重さであれば、残りの２個を天秤にかける。　　　←３回目
　これで軽い方が「軽いもの」である。

最も多いケースで、３回あれば判定できる。
「最小回数」ではなくて「最大回数」ですね。


一般の N 個の場合には、この N を
(a) ３の倍数の場合
(b) ３の倍数 + 1 の場合
(c) ３の倍数 + 2 の場合
に分ける必要がありそうです。

ご自分で考えてみてください。

No.2 回答者： ShowMeHow 回答日時： 2022/03/13 15:11

１回の測定で対象の数を元の数の1/3（繰り上げ整数）にしたものに絞れるということを表しているのですが、いまいちわかりにくいですね。

No.1 回答者： usa3usa 回答日時： 2022/03/13 14:54

1回の上皿天秤で、3通りの回答が得られますよね（右が重い、釣り合う、左が重い）

つまり、1回の天秤で候補は最大1/3に減らすことが可能ということです。