【論理パズル】解けるかな？Googleの面接で出題された問題

 

海外のサイトを適当に見ていると、面白いものを見つけました。

「puzzlefry」というサイトで、ユーザーがお互いに論理パズルを出しあっているサイトです。

この記事では、その中でも良く出来ているなと僕が思った問題を紹介します。

今回のお題はこちらです！”2 Eggs and 100 floor Google Classic question”

この問題はgoogleの面接で実際に聞かれた問題だそうです。

さて、みなさんの頭は柔らかいですか？

問題！「２つの卵で割れる階数を探す」

 

問題は理解できましたか？

例えば、1階で卵を落として見たけど割れなかった。しかし、2階で落とすと割れてしまった。

ということは、卵は2階から落とすと割れてしまうということがわかります。当然ですね。

1階から順番に落としていく方法だと、もし卵が100階まで割れなければ最大で100回も確認しなくてはなりませんよね。

ただ、卵は2つもあるので1回は失敗してもいいのです。

より、効率よく卵が割れる階を調べるにはどうすればいいのでしょうか？

ヒント！

もう答えがわかってる人ならばヒントを飛ばして答えを見ましょう。

まだよくわからない人のためにヒントを授けましょう。

ポイントは1回は失敗してもよいという点です。

1階から十番に確認する方法だと1から100まで100回も確認する必要があります。

しかし例えば、最初に50階から卵を落として割れるかどうか確認したとしましょう。

そうすると、もし卵が割れてしまえば1から49階の間に正解があるとわかり、割れなければ51階から100階までの間に正解があるということです。

これで一気に確認する範囲が半分に減りましたよね。

このように、1回失敗できるというチャンスを十分に活かすことを考えてみましょう。

答え！

一般的な解答

僕も含めて多くの人が考えたであろう方法。それは次のようなものでしょう。

卵は２つしかないので、1つ目の卵で何階あたりで卵が割れてしまうかの目安を付けます。

この目安の付け方が難しい。とりあえず、一番直感的なのは以下のやり方ですね。

10階単位で調べていき、割れた階があれば、その階を詳しく見ていく方法です。

具体的には、10階、20階、30階・・・100階と割れる階を探し、例えば100階で割れたとすると91階、92階・・。とチェックしていきます。

この方法だと最大回数は99階で割れるときなので、それまでに行われるチェックは次のようになります。

10,20,30,40,50,60,70,80,90,100,91,92,93,94,95,96,97,98,99

つまり、合計で19回のチェックが必要となります。

他にも20階ごとや30階ごとに区切るという方法もありますが、どれも10階で区切るよりも増えてしまいます。

スマートな解答

しかし、これが最善の方法でしょうか。目安を付けてやるという方法は問題ないはずです。

しかし、10階ごとに区切るのがいいという保証はありません。

10という数字はあくまで僕達からするとキリの数字だったからというだけで、それが最善というわけではないでしょう。

では、一番よい区切り方を考えてみます。

そもそも、上の階へと行けば行くほど割れる可能性はどんどん高くなります。

一番最初は1から100までどれもまんべんなく割れる可能性があったのに対し、80階までチェックすれば残り20階のうちのどれかとなります。

言い換えれば、チェックした階数が増えれば増えるほど、割れる可能性がどんどん大きくなってくるわけです。

それにもかかわらず、毎回同じ階数で区切るというのはナンセンスですね。

つまり、区切る階数をどんどん減らしていくほうが、スマートなやり方となるわけです。

例えば、はじめに区切った階数を10だとすると、次に区切る階数を9、8・・・とどんどん減らしていきます。

でははじめに区切る階数をいくつにしましょうか。それを求めるには数学の知識を使いましょう。

ここで、はじめに区切る階数をNだとします。すると、次に区切る階数はN-1ですよね。その次はN-2です。

それらを全て足して100になるようにするには、

それが100となればいいので、

これを解くと、N=14.。

つまり、14階、13階、・・・と区切って行けばいいということになります。詳しく書いてみると、

14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100

合計14回ですね。

単純に10で区切るよりも5回もチェックする階数が減りました。

どうですか？この方法を思いつけたのならばあなたはGoogleの面接で受かるかもしれません。

まとめ

一見簡単そうな問題に思えたのですが、実はそんなことはありませんでしたね。

僕も完全に引っかかりました。さすがGoogle、よくできた問題ですね。

もしかすると気付かれてないだけでもっとスマートな方法があるかもしれません。

良い方法が見つかればぜひコメントで教えて下さい。

 - 日々のつぶやき