12個のたまごと天秤の問題(4) 問題の一般化

12個のたまごと天秤の問題4回目です。

今までの復習をしておきましょう。

12個のときの解法を見て、新しい記号を導入して、

12個の解法を新しい記号で書き直しました。

ここから、一般化していきます。

どう一般化するの？と思う人も多いでしょうけど、

まずは、3回でできるのは12個が最大ですか？

というような問から始めます。 

実は13個でも3回でできます。14個では3回ではどう転んでも無理です。

最大の個数を求めていくという問題設定を行います。

問題

(0+-)がN個あります。1個だけ(0)でなく、残りのN-1個は(0)です。

天秤をn回まで使って(0)でない1個を見つけることのできるNの最大数$a_n$は

何でしょう？

前回までに示したことは$a_3 \ge 12$です。

$n=2$のとき

$n=2$のときのことをまず考えてみましょう。

つまり

2回の天秤で何個判別できるか？

という話です。

1回目に$k$個ずつ載せるとしましょう。

傾いたとき、(0+)が$k$個、(0-)が$k$個出てきます。

あと$1$回で判定するには、この$2k$個が$3$個以下でなくてはなりません。

$2k \le 3$

だから、なので$k=1$が最大個数になります。

つりあったときは、残りに(0)でないのがあります。

残りが1個のときはそれが(0)でないです。

2個のときは、1回目で(0)と確定した1個と残りの一個で測ればよいです。

左 (0+-)  右(0)　残り　(0)(0+-)が1個ずつ

傾いたら左、釣り合ったら残りの(0+-)が(0)でないです。

1回目で釣り合ったときの残りが3個のときは、

あと1回で判別することはどうやってもできません。

したがって、

$a_2=4$

が分かりました。

この$n=2$のときの思考がいろいろなことを示唆します。

まずは、1回の天秤の操作は、3個の情報しか得られないという事実です。

天秤と最大数について

無造作に天秤という言葉を使ってきましたが

天秤というものの性質をちゃんと考えておきましょう。

天秤というのは、1回の操作で、3通りの情報しか出せません。

「つりあっている」

「右に傾く」

「左に傾く」

です。だから、1回の操作で判別できるのは3個までです。

そして、

$n$回の操作で判別できるのは$3^n$が最大

言い方を変えると

$n$回の操作で判別できるのはどう頑張っても$3^n$以下

です。

最初の考察

まず、1回目の天秤を載せる前、(0+-)がたくさんあります。

釣り合ったときは、(0+-)がたくさんという状況はあまり変わりません。

ですが、釣り合わなかったときは、(0+)と(0-)がたくさんに変わります。

それ以降は(0+)と(0-)がたくさんという状況です。

(1)  (0+)と(0-)がたくさんという状況

(2)  (0+-)がたくさんと(0)がたくさんという状況

の二つの状況があることを認識しましょう。

次回からは、(1)の

(0+)と(0-)が合計N個あるとき$n$回の天秤で判別できる$N$の

最大個数を求めていきましょう。