12個のたまごと天秤の問題(6)1回目釣り合うとき

天秤の問題、だんだん本質の近づいてきている感じがします。

まずは、問題再掲です。

問題

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

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

何でしょう？

1回目の天秤の後、

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

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

になります。

(1)を考えていって、次の定理を得ました。

定理

$N$個の(0+)または(0-)があり、1個は(0)でないとする。

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

$3^n$

である。

じゃぁ、次は

(2)の(0+-)たくさんと(0)がある状況

を考えていきます。

(2)の問題

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

さらに(0)が1個以上あります。

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

何でしょう？

$n=2$を考えるところで、$c_1=2$を示しましたが、

もう一回ちゃんと書いてみましょう。

(0)が1個あるという状況です。

2個の(0+-)のとき

以下のように判別できます。

左 (0+-) 右 (0)  残り(0+-)

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

ここから1個増やすことはできるか？

残りを2個にすると、つりあったときに2個残ります。

なので、残りは1個でないとだめです。

天秤に載せるのを増やすとどうなるか。どちらに載せても

傾いたときに2個の(0+-)が残ってしまいます。

ということで3個の(0+-)は1回では判別できません。

したがって、

$c_1=2$

が分かりました。

漸化式の導出

これから$c_n$に関する漸化式を作ります。

左：ｘｘｘｘ　右ｘｘｘｘｘ　　残りｘｘｘｘ

とするんですが、

まずは、

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

この状況は$c_{n-1}$なので、残りの最大数は$c_{n-1}$

です。

天秤に載せる方は、左右を合わせて$3^{n-1}$以下です。

$3^{n-1}$が奇数なのでこのまま載せることはできません。

(0)がない状況では、$3^{n-1}-1$を半分ずつ載せるのが最大です。

いまは(0)が1個あるので1個足して、天秤に載せます。

左：(0+-): $(3^{n-1}+1)/2$個、　右: (0+-): $(3^{n-1}-1)/2$個、(0)1個

とすると、傾いたときに、$3^{n-1}$の(0+)、(0-)が出てきてそれが最大です。

よって、

左：(0+-): $(3^{n-1}+1)/2$個、　

右: (0+-): $(3^{n-1}-1)/2$個、(0)１個

残り　$b_{n-1}$

とおけばよいことが分かります。

したがって、

$c_n = 3^{n-1} + c_{n-1}$

これを解いて、

$c_n = (3^n + 1)/2$

です。

これで、もう一個定理ができました。

定理

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

さらに(0)が1個以上ある。

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

$(3^n + 1)/2$

である。