天秤にかけろ

Googleの採用試験として次のような問題が紹介されていました。

あなたは同じサイズのボールを8つもっています。
そのうち7つは同じ重さですが、1つはほかのものよりもわずかに重いです。
秤を2回だけ使ってこのわずかに重いボールを見つけるには
どうすればいいですか

https://twitter.com/bunkei_kanojo/status/349686416122454019

これはGoogleの採用試験としては簡単すぎるので、おそらくは本当ではないと思います。あえて関連を見つけ出すならば、８個のボールから他と違う１つを見つけるのもある種の検索であるのだという点くらいでしょうか。
他にも問題の不備はあります。秤がどういう種類のものか書いていないことです。もし体重計のようなバネばかりだとしたら問題が成り立ちません。でも、バネばかりを使ったこんな問題もあります。

金貨が入った袋が４袋あって、そのうち１袋にはすべて偽の金貨が入っている。本物が１０グラム、偽者が９グラムだったとして、どの袋に偽の金貨が入っているかを一度だけ秤をつかって見つける方法を示せ。

こんな問題ならばバネばかりでなければいけません。答えとしては４つの袋をＡＢＣＤとして、Ａの袋から１枚、Ｂの袋からは２枚、Ｃからは３枚、Ｄからは４枚の金貨を取り出して重さをはかる方法があります。合計１０枚の金貨が全部本物ならば１００グラムですが、偽物の金貨の分だけ軽くなるのですがそれが１０グラムならばＡの袋が偽だということがわかります。
もう少し発展させた問題として、偽の金貨の袋が１つではなく複数の場合なんてのもありますが、これは取り出す金貨を１枚、２枚、４枚、８枚のようにすることで対応できます。

話を最初の問題に戻すと、８個のボールから１つの重いボールを見つけるのに使う秤は天秤ばかりです。さらに、秤を使う場合にボールを乗せながら観察する方法などは禁止されていると考える必要があります。そうでないと、両方の皿にまず１個づつボールを乗せて天秤の傾きを見ながらボールを追加していき、天秤が傾いたときに乗せたボールが重いボールだなんてことができてしまいます。だから４個のボールを乗せるのならば、一度に乗せて天秤のがかたむくかつりあうのかを観察するのが１回としなければいけません。そうしないと何がいけないのかというのを聞かれても困るのですが、問題が成立するためにはそうしないとならないということはご理解願います。

さて、８個のボールから天秤を２回使って１個の重いボールを見つけ出す問題を考える前に、天秤を１回使った場合について考えてみます。１回天秤を使う場合には、何個のボールから１つのボールを見つけ出すことができるでしょうか。
答は３個のボールとなるのですが、一応方法も説明しておきます。
３個のボールをＡＢＣとおいて、ＡとＢのボールの重さを天秤で比べます。天秤が傾いた場合は、下がった方のボールが重いことがわかり、天秤がつりあった場合は残ったＣのボールが他よりも重いことがわかります。ＡとＢしか天秤に載せていないのに、Ｃが重いことがわかるのは問題でどれか１つが重いとなっているからで、問題の言うことを信じるのならばＡとＢが同じ重さであった場合には残る１つのＣが重たいのだということがわかります。これは消去法と言われる考え方です。考えられる答から、１つ以外がすべて否定された場合には残るひとつが正解だというのが消去法です。

天秤を１回使うと３個のボールの中から重たい１個を見つけることができるので、天秤を２回使う場合には最初の１回で重たいボールがどれか３個の中にあることがわかれば良いことがわかります。３個の中から１つの重い玉を見つけるには、天秤を１回使えば大丈夫なのは先ほどの説明の通りです。
具体的には天秤の片方に３個もう片方に３個乗せて、天秤が傾いたら下がったほうの３個に重いボールがあることがわかります。もし天秤がつりあった場合にも、残ったボールが３個以下ならば残り１回で重いボールを見つけることができます。だから８個ではなく、９個のボールからでも天秤を２回使うことで重いボールを見つけ出すことができます。
では、天秤を３回使える場合はどうか。これは、最初の１回で重いボールがどれか９個の中に入っていることがわかれば残り２回で見つけられます。２７個のボールを９個づつ３つに分けて天秤を使うことで、どの９個の中に重いボールが入っているのかがわかるので、天秤を３回使った場合には２７個のボールから重いボールを見つけることができます。このような考え方を帰納法といいます。

いまさら説明する必要もないでしょうが、最初の問題の答を書いてみます。

８個のボールをＡＢＣＤＥＦＧＨとして、ＡＢＣとＤＥＦを天秤ばかりに乗せる。ＡＢＣが下がったらＡとＢを天秤に乗せ、下がったほうが重いボール。もし釣り合えば残りのＣが重いボール。ＤＥＦが下がった場合も同様。
ＡＢＣとＤＥＦが釣り合った場合にはＦとＧを天秤に乗せてどちらかが下がれば下がったほう、釣り合ったら残ったＨが重いボールということになる。

ではボールが８個ではなく、８０個だとしたら天秤を何回使えば重いボールを見つけることができるでしょうか。

８個の場合の１０倍なので、天秤も２回の１０倍の２０回使えば見つけ出せることはあきらかですが、もっとずっと少ない回数でも見つけることができます。
先ほどの天秤を３回使った場合には２７個のボールから１つの重いボールを見つけ出せることがわかりましたが、４回の場合は２７個の３倍の８１個の中から重いボールを見つけることができます。つまり８０個の場合でも天秤を４回使うことで、１つだけ混ざった重いボールを見つけることができるわけです。
個数が８個と８０個で１０倍になっても、天秤を使う回数は２回から４回と２倍にしかならないのと同様に、検索する個数が増えた場合にでも検索方法を工夫することで個数が増えたほどには検索の手間が増えないようにできる。なんて書くと、最初のＧｏｏｇｌｅの採用試験だというのにも何か信憑性が増してきたりしないでしょうか。