Der Haken: Die sind wirklich schwer. Intelligenz und Kreativität müssen beim Bewerber Hand in Hand gehen, damit das was wird mit kostenlosem Mittag und Bademeister. Interessant ist vor allem, dass zumindest einige der Fragen nicht eindeutig zu beantworten sind. Die hier hat in den Kommentaren einiges an Diskussion hervorgerufen. Witzigerweise war die Antwort auf der Website noch eine andere als vor kurzem. Offensichtlich hat der Autor klammheimlich den Post verändert.
Die Frage ist folgende: Stell dir vor, du kannst dich einem Gebäude mit 100 Stockwerken frei bewegen. Außerdem hast du zwei (Hühner-)Eier. Sie können entweder hart gekocht sein und niemals brechen (just accept it for the sake of the argument), oder sie sind weich und brechen irgendwann. Du weißt aber nicht, wann sie kaputt gehen. Frage: Wie viele Würfe benötigt man, um heraus zu finden, dass nach einem Wurf von diesem Stockwerk das Ei nicht bricht? (Die Frage ist im Original etwas missverständlich gestellt. Ich gehe davon aus, dass mit gekocht-nicht-gekocht nur eine plausible Begründung dafür geliefert werden soll, dass die Eier irgendwo zwischen der ersten und der letzten Abwurfstelle zerbrechen können. Außerdem verfügen beide Eier über die gleiche Zerbrechlichkeit.)
Was hat der Spaß mit Google zu tun? Es geht um generelle Vorgehensweisen bei Suchen. Was man sucht, ist ziemlich beliebig. Daher kann es sich auch um die Haltbarkeit von gekochten Eiern handeln. Grundlage des Vorgehens ist divide-and-conquer. Man muss die Stockwerke, von denen man die Eier wirft, also möglichst geschickt auswählen. Weder dürfen es zu viele noch zu wenige sein. Das Problem ist folgendes: Wenn ein Ei nicht kaputt geht, weiß man nicht, ob es ein wenig zerbrechliches Ei war, oder ob das Stockwerk nicht hoch genug war.
Falls es sich um gekochte Eier handelt, würden sie nicht einmal nach einem Wurf vom 100. Stockwerk zerbrechen. Die nicht-gekochten Eier könnten jedoch bereits vom 1. Stockwerk herab kaputtgehen. Eine Möglichkeit wäre also, gleich vom 100. Stockwerk ein Ei zu werfen. Falls nichts passiert, ist alles gut. Falls es jedoch kaputt geht: Was tun? Man müsste beim ersten Stockwerk anfangen, um sicherzugehen, dass man jede Möglichkeit überprüft. Es könnte ja so sein, dass das Ei erst auf dem 99. Stockwerk kaputtgeht. Dann hätte man im schlimmsten Fall 1 + 99 Möglichkeiten gebraucht. Ebenfalls würde man auf 100 Würfe kommen, wenn man gleich ganz unten anfängt und sich nach oben vorarbeitet. Auch hier beträgt die maximale Anzahl 100, allerdings würde dafür ein Ei genügen.
(Der Klassiker "binäre Suche" funktioniert nicht, weil man sich nur 2 Fehlversuche leisten kann.)
Ein bisschen smarter ist eine Variante, die mit 19 Möglichkeiten auskommt. Man wirft das erste Ei vom 10 Stockwerk, dann vom 20. usw. Im besten Fall wäre man nach 10 Würfen fertig. Falls es jedoch zerbricht, nutzt man das zweite Ei. Sagen wir, es geht nach dem 70. Stockwerk kaputt. Dann ist klar, dass es mehr als 60 Stockwerke hält, aber weniger als 70. Mit dem 2. Ei überprüft man die Stockwerke 61 - 69. Der schlimmste Fall wäre, wenn die Eier auf dem 69. Stockwerk zerbrechen. Dann bräuchte man 10 + 9 Würfe. Bei diesem Algorithmus hätte man also die Stockwerke in 10er-Blöcke geteilt.
Es geht aber noch cleverer. Die Mindestzahl von Würfen ist 14. (Ich habe in den Kommentaren leider keinen Beweis dafür gefunden, scheint eher intuitiv, bestenfalls computational.) In den Kommentaren hat jemand alle Möglichkeiten aufgeschrieben:
Drop an egg at floor 14. If the egg breaks, you have 13 floors (1 to 13) to check with the 2nd egg and you'er done. Otherwise...
Drop an egg at floor 27. If the egg breaks, you have 12 floors (15 to 26) to check with the 2nd egg and you'er done. Otherwise...
Drop an egg at floor 39. If the egg breaks, you have 11 floors (28 to 38) to check with the 2nd egg and you'er done. Otherwise...
Drop an egg at floor 50. If the egg breaks, you have 10 floors (40 to 49) to check with the 2nd egg and you'er done. Otherwise...
Drop an egg at floor 60. If the egg breaks, you have 9 floors (51 to 59) to check with the 2nd egg and you'er done. Otherwise...
Drop an egg at floor 69. If the egg breaks, you have 8 floors (61 to 68) to check with the 2nd egg and you'er done. Otherwise...
Drop an egg at floor 77. If the egg breaks, you have 7 floors (70 to 76) to check with the 2nd egg and you'er done. Otherwise...
Drop an egg at floor 84. If the egg breaks, you have 6 floors (78 to 83) to check with the 2nd egg and you'er done. Otherwise...
Drop an egg at floor 90. If the egg breaks, you have 5 floors (85 to 89) to check with the 2nd egg and you'er done. Otherwise...
Drop an egg at floor 95. If the egg breaks, you have 4 floors (91 to 94) to check with the 2nd egg and you'er done. Otherwise...
Drop an egg at floor 99. If the egg breaks, you have 3 floors (96 to 98) to check with the 2nd egg and you'er done.
Drop an egg at floor 100.
Falls sich jemand bemüßigt fühlt, einen Beweis zu erstellen, wird der hier natürlich veröffentlicht.
