«Σήμερα μου έτυχε μια πολύ παράξενη υπόθεση» , είπε ο αστυνόμος Σαίνης στο βοηθό του υπαστυνόμο Κλουζώ. «Στο ξενοδοχείο «Η ξάπλα» διεπράχθη ένας φόνος με δηλητήριο. Γνωρίζαμε ότι το θύμα δηλητηριάστηκε πίνοντας κρασί από ένα ποτήρι κατά την διάρκεια μιας γιορτής .Το ερώτημα ήταν ποιο ποτήρι; Είχαμε όλα τα ποτήρια μισογεμάτα, και τοποθετημένα σε σειρές στην κουζίνα του ξενοδοχείου. Μόνο ένα από αυτά περιείχε δηλητήριο θέλαμε να βρούμε ποιο είναι, για να το εξετάσουμε για δακτυλικά αποτυπώματα. Το εργαστήριο μας θα μπορούσε να εξετάσει το περιεχόμενο κάθε ποτηριού χωριστά αλλά όπως ξέρεις λόγω περικοπής κονδυλίων και επειδή κοστίζουν οι αναλύσεις, θέλαμε να κάνουμε όσο το δυνατό λιγότερες δόκιμες. Τηλεφωνήσαμε λοιπόν στο Πανεπιστήμιο και έστειλαν έναν καθηγητή μαθηματικών να μας βοηθήσει .Αυτός μέτρησε τα ποτήρια, γέλασε και μου είπε:
« Διαλέξτε οποιοδήποτε ποτήρι θέλετε, αστυνόμε . Θα το εξετάσουμε πρώτο.»
«Μα δεν χάνουμε έτσι μια δόκιμη;», ρώτησα.
«Όχι» μου απάντησε.», είναι κι αυτό μέρος της πιο σύντομης διαδικασίας .Θα εξετάσουμε ένα ποτήρι στην αρχή. Δεν έχει σημασία ποιο.»
«Πόσα ήταν τα ποτήρια;», ρώτησε τότε ο υπαστυνόμος Κλουζώ.
«Δεν θυμάμαι .Ήταν αρκετά κάπου μεταξύ 500 και 600.»
Ποιος ήταν ακριβώς ο αριθμός των ποτηριών;
Διευκρίνιση:
Υποτίθεται βέβαια ότι μια ομάδα ποτηριών μπορεί να ελεγχτεί ως προς το αν περιλαμβάνει το δηλητηριασμένο ποτήρι, αντλώντας λίγο κρασί από κάθε ποτήρι και φτιάχνοντας ένα μείγμα.
Προτάθηκε από Carlo de Grandi
Για να μην επιβαρύνεται από τη μεμονωμένη εξέταση ενός τυχαίου ποτηριού η βέλτιστη διαδικασία, θα πρέπει τα ποτήρια να είναι κατά 1 ακριβώς περισσότερα από κάποια δύναμη του 2. Τέτοια δύναμη στο δεδομένο εύρος είναι μόνο η 2^9=512, άρα τα ποτήρια είναι 512+1=513.
Εξετάζεται αρχικά 1 τυχαίο ποτήρι κι αν βρεθεί δηλητηριασμένο, τελειώσαμε. Αν όχι, το αφήνουμε στην άκρη και εξετάζουμε ένα μίγμα από τα μισά των υπόλοιπων 512, δηλαδή 256 ποτήρια. Συνεχίζουμε εξετάζοντας διαδοχικά ένα τη φορά μίγμα από τα μισά των εκάστοτε απομενόντων ύποπτων ποτηριών. Όταν θα έχουν απομείνει 2 ύποπτα ποτήρια, εξετάζουμε το ένα και ή το βρίσκουμε δηλητηριασμένο ή όχι, οπότε το δηλητηριασμένο είναι το άλλο.
Χρειάζονται 1+9=10 το πολύ αναλύσεις.
513