tellen Sie sich vor, Sie sind in einem hohen Gebäude mit einer Katze. Die Katze kann einen Sturz aus einem niedrigen Fenster überleben, stirbt jedoch, wenn sie von einem hohen Boden geworfen wird. Wie können Sie mit der geringsten Anzahl von Versuchen den längsten Tropfen ermitteln, den die Katze überleben kann?

Wenn Sie nur eine Katze haben, können Sie natürlich nur linear suchen. Werfen Sie zuerst die Katze aus dem ersten Stock. Wenn es überlebt, werfen Sie es von der zweiten. Schließlich stirbt die Katze, nachdem sie vom Boden f geworfen wurde. Sie wissen dann, dass Etage f-1 die maximal sichere Etage war.

Aber was ist, wenn Sie mehr als eine Katze haben? Sie können jetzt eine Art logarithmische Suche durchführen. Nehmen wir an, der Bau hat 100 Stockwerke und Sie haben zwei identische Katzen. Wenn Sie die erste Katze aus dem 50. Stock werfen und sie stirbt, müssen Sie nur 50 Stockwerke linear durchsuchen. Sie können es noch besser machen, wenn Sie für Ihren ersten Versuch eine untere Etage wählen. Nehmen wir an, Sie lösen das Problem in 20 Stockwerken gleichzeitig und der erste fatale Stock ist # 50. In diesem Fall überlebt Ihre erste Katze die Flüge ab den Etagen 20 und 40, bevor sie ab der 60. Etage stirbt. Sie müssen lediglich die Etagen 41 bis 49 einzeln überprüfen. Das sind insgesamt 12 Versuche. Das ist viel besser als die 50, die Sie benötigen würden, wenn Sie versucht hätten, die binäre Eliminierung anzuwenden.

Was ist im Allgemeinen die beste Strategie und die schlechteste Komplexität für ein n-stöckiges Gebäude mit 2 Katzen? Was ist mit n Stockwerken und m Katzen?

Angenommen, alle Katzen sind gleichwertig: Sie alle überleben oder sterben bei einem Sturz aus einem bestimmten Fenster. Außerdem ist jeder Versuch unabhängig: Wenn eine Katze einen Sturz überlebt, ist sie völlig unversehrt.

Dies ist keine Hausaufgabe, obwohl ich sie vielleicht einmal für eine Schulaufgabe gelöst habe. Es ist nur ein wunderliches Problem, das mir heute in den Sinn gekommen ist, und ich kann mich nicht an die Lösung erinnern. Bonuspunkte, wenn jemand den Namen dieses Problems oder des Lösungsalgorithmus kennt.