Sie haben 1.000 Flaschen Wein. Eine Flasche ist vergiftet. Es gibt 10 Gläser. Sie müssen Wein in Gläser gießen. (Sie können Wein in verschiedenen Gläsern gießen; Sie können Wein in einem Glas aus verschiedenen Flaschen mischen) Und drücken Sie den Knopf. Nach dem Drücken, Gläser, wo es einen Tropfen Gift zerbrechen. Gibt es eine Möglichkeit, Wein in Gläser zu gießen, so dass Sie mit Sicherheit sagen können, in welcher Flasche der vergiftete Wein? Wie können Sie die Antwort auf eine beliebige Anzahl von Flaschen und Gläsern zusammenfassen?
Es gibt einen Algorithmus, den man genau wissen kann, welche Giftflasche. 1. Füllen Sie das erste Glas mit einem Tropfen von halben Flaschen Wein. Drücken Sie den Knopf. 2. Wenn das Glas gebrochen ist, ist eines von ihnen Gift und die anderen nicht. Wiederholen Sie Absatz 1 mit dem nächsten Glas und die Hälfte Flaschen, von denen eine Gift ist. 3. Wenn das Glas intakt ist, gibt es kein Gift in dieser halben Flasche, und es gibt keine Giftflasche in der anderen Hälfte Flaschen. Wiederholen Sie Absatz 1 mit der anderen Hälfte Flaschen. So wird bei jedem Schritt, ein oder kein Glas verwendet werden und die Anzahl der Flaschen, die vergiftet enthält, halbiert werden. Die Aufgabe wird somit durch Induktion in beliebiger Anzahl von Gläsern und Flaschen kombiniert werden. Zehn Schritte auf diese Weise, einer der 2 × 10 = 1.024 Flaschen. 1000 < 1024 Flaschen werden identifiziert.