12個のたまごと天秤の問題(5) 1回目釣り合わないとき

12個のたまごの問題を考えてきました。

今回は、

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

最大個数を求めていきます。

1回の天秤では？

(0+)または(0-)が3個、1個だけ(0)でないのがあるとき

1回で判別可能です。

ここは、丁寧に見ていきましょう。3個だけなので全部書きましょう。

(0+)が3個のとき

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

傾いたら重い方、釣り合ったら残り

(0+)が2個、(0-)が1個のとき

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

傾いたら重い方、釣り合ったら残り

(0+)が1個、(0-)が2個のとき

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

傾いたら軽い方、釣り合ったら残り

(0-)が3個のとき

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

傾いたら軽い方、釣り合ったら残り

じゃぁ、文章にしておきます。

補題

$3$個の(0+)または(0-)があり、1個は(0)でないとき

1回の天秤で判別可能である。

これを一般化してみましょう。

補題

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

$n$回の天秤で(0)でない1個をみつけることができる。

数学的帰納法で証明していきます。

さっき$n=1$のときは示したので、

$n=k$のとき正しいとして、$n=k+1$のときを考えます。

(0+)が$2\dot 3^k$以上のとき

左 (0+): $3^k$個   右 (0+): $3^k$個

と載せればよいです。

傾いたら、重い方が(0+): $3^k$個で他が(0)になるので

数学的帰納法を使えます。

釣り合ったときは、残りの$3^k$個に(0)でないのがあるので

数学的帰納法が使えます。

(0-)が$2\dot 3^k$以上のとき

左 (0-): $3^k$個   右 (0-): $3^k$個

と載せればよいです。

傾いたら、軽い方が(0-): $3^k$個で他が(0)になるので

数学的帰納法を使えます。

釣り合ったときは、残りの$3^k$個に(0)でないのがあるので

数学的帰納法が使えます。

(0+)も(0-)も$2\dot 3^k$より少ないとき

このとき、(0+)も(0-)も$3^k$個以上あります。

(0+)の個数を$p$個、(0-)の個数を$m$個とします。

左 (0+):$p-3^k$個、(0-):$m-3^k$個  　右(0+):$p-3^k$個、(0-):$m-3^k$個

とします。

傾いたら重い方の$p-3^k$個と軽い方の$m-3^k$個で合計$3^k$個の

中に(0)でないのがあるので、数学的帰納法が使えます

釣り合ったときは、残りの$3^k$個に(0)でないのがあるので

数学的帰納法が使えます。

これで証明終わりです。

天秤$n$回で最大$3^n$個までしか判別できないことを思い出すと、

以下の定理が導かれます。

定理

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

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

$3^n$である。