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

今回で答えを得ます。

問題

(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+-)が$N$個ある。1個だけ(0)でなく、残りのN-1個は(0)。

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

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

$(3^n + 1)/2$

である。

ここまで考えたたのでできます。

大体、前回の$c_n$を求めるのと同じような感じです。

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

とするんですが、

まずは、

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

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

です。

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

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

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

よって、

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

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

残り　$b_{n-1}=(3^{n-1}+1)/2$

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

よって、

$a_n = (3^{n-1}-1)  + (3^{n-1}+1)/2 = (3^n-1)/2$

です。

$a_n =  (3^n-1)/2$

が答えです。

ここまで来て定理を得ることができました。

定理

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

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

$(3^n - 1)/2$

である。

これで、結論を得ることができました。

最初に解こうとした$a_n$とは別に、$b_n$, $c_n$も求めることができました。

天秤の問題はいろいろバリエーションありますけど、

今回考えたことで、大概は解けるようになったかなと思います。