ALL EN FR ES IT

Logo

≡ ► ◄ ▲

Das Glas mit dem Gift

Mathematik Nr. 77

»Mathematiker sind seltsame Vögel«, sagte der Polizeikommissar zu seiner Frau. »Stell dir vor, wir hatten alle diese teilweise gefüllten Gläser auf einen Tisch in der Küche des Hotels der Reihe nach aufgestellt. Nur in einem von ihnen befand sich Gift, und wir wollten wissen in welchem, bevor wir das Glas nach Fingerabdrücken untersuchten.

Unser Labor hätte den Inhalt jedes Glases untersuchen können, aber diese Untersuchungen kosten Zeit und Geld, und daher wollten wir so wenige wie möglich untersuchen. Wir riefen in der Universität an, und sie schickten einen Mathematikprofessor, der uns helfen sollte. Er zählte die Gläser, lächelte und sagte:

'Nehmen Sie irgendein Glas, welches Sie wollen, Kommissar, und wir werden dieses zuerst untersuchen.'

'Aber würde das nicht die ganze Untersuchung verderben?' fragte ich.

'Nein', sagte er, 'das ist der Anfang des besten Auswahlverfahrens. Wir müssen dabei ein Glas zuerst untersuchen. Es ist gleichgültig welches.'«

»Wie viele Gläser gab es denn am Anfang?« fragte die Frau des Kommissars.

»Ich kann mich nicht genau daran erinnern. Irgendeine Zahl zwischen hundert und zweihundert.«

Was war genau die Anzahl der Gläser? Und wieso war die Methode des Mathematikprofessors nicht die beste?

Lösung anzeigen

Die beste Methode, das Glas mit dem Gift herauszufinden, ist binäre Suche:

Man teile die Gläser in zwei Hälften, gebe je einen Tropfen aus der ersten Hälfte in ein Gefäß und untersuche dieses auf Gift. Findet man Gift, ist dieses in einem Glas der ersten Hälfte, sonst in einem Glas der zweiten Hälfte.

Nun wende man das Verfahren auf die Gläser an, unter denen sich das Glas mit dem Gift befinden muss; immer wieder, bis nur noch das Glas mit dem Gift übrig ist.

Für 2n Gläser braucht man dazu n Schritte.

Offensichtlich war ein Glas zu viel, insgesamt waren es also 2n+1 Gläser. Die einzige Zahl 2n zwischen 100 und 200 ist 27=128. Es waren also 129 Gläser.

Die Strategie der Mathematikprofessors war deshalb nicht optimal, da er das überzählige Glas zuerst getestet hat.

Testet man das überzählige Glas zuerst, braucht man mit der Wahrscheinlichkeit 1/129 nur einen einzigen Test und mit der Wahrscheinlichkeit 128/129 acht Tests (das macht im Schnitt 7.95 Tests).

Testet man das Überzählige Glas zum Schluss, braucht man mit einer Wahrscheinlichkeit 128/129 sieben Tests und mit einer Wahrscheinlichkeit von 1/129 acht Tests (das macht im Schnitt 7.02 Tests).