Το Παιχνίδι του Ψεύτη: Πόσες Ερωτήσεις Χρειάζονται αν Επιτρέπονται Ψέματα;

🤥 Το Παιχνίδι του Ψεύτη: Μαθηματικά απέναντι στο Ψέμα

Στο κλασικό παιχνίδι των 20 ερωτήσεων, κάποιος σκέφτεται έναν αριθμό και εμείς προσπαθούμε να τον ανακαλύψουμε κάνοντας μόνο ερωτήσεις που απαντώνται με Ναι ή Όχι.

Τι συμβαίνει όμως αν αυτός που απαντά έχει δικαίωμα να πει ψέματα;

Ένας άγνωστος αριθμός \(x\) επιλέγεται από ένα σύνολο πιθανών αριθμών.

Μπορούμε να κάνουμε το πολύ \(q\) ερωτήσεις της μορφής:

«Ο αριθμός \(x\) ανήκει στο σύνολο \(X\);»

Οι απαντήσεις είναι μόνο Ναι ή Όχι.

Υπάρχει όμως μια παγίδα: ο αντίπαλος επιτρέπεται να πει ψέματα μέχρι \(k\) φορές.

Το ερώτημα είναι εντυπωσιακό:

Πόσους διαφορετικούς αριθμούς μπορούμε να ξεχωρίσουμε με \(q\) ερωτήσεις, όταν γνωρίζουμε ότι μέχρι \(k\) απαντήσεις μπορεί να είναι ψευδείς;

🔢 Χωρίς ψέματα είναι εύκολο

Αν όλες οι απαντήσεις είναι αξιόπιστες, κάθε ερώτηση Ναι/Όχι μπορεί ουσιαστικά να χωρίσει τις πιθανότητες στα δύο.

Με \(q\) ερωτήσεις μπορούμε επομένως να διακρίνουμε μέχρι

\[ 2^q \]

διαφορετικές περιπτώσεις.

Με μόλις 7 ερωτήσεις, για παράδειγμα,

\[ 2^7=128. \]

Αν όμως μία από τις επτά απαντήσεις μπορεί να είναι ψέμα, η κατάσταση αλλάζει εντελώς: δεν αρκεί να αποκωδικοποιήσουμε τις απαντήσεις — πρέπει ταυτόχρονα να μπορούμε να εντοπίσουμε και το πιθανό λάθος.

🧩 7 ερωτήσεις και ένα ψέμα

Στο παράδειγμα της εικόνας, χρησιμοποιούνται 7 κατάλληλα επιλεγμένες ερωτήσεις και επιτρέπεται το πολύ ένα ψέμα.

Παρόλα αυτά, είναι δυνατό να προσδιοριστεί με βεβαιότητα ο άγνωστος αριθμός από το \(0\) έως το \(15\).

\[ \boxed{16\text{ δυνατές τιμές}} \]

Και εδώ εμφανίζεται η μεγάλη έκπληξη: η στρατηγική συνδέεται με κώδικες διόρθωσης σφαλμάτων.

Οι επτά απαντήσεις μπορούν να αντιμετωπιστούν σαν μια δυαδική λέξη:

\[ \text{Ναι}=1, \qquad \text{Όχι}=0. \]

Έτσι, το ψέμα λειτουργεί μαθηματικά σαν ένα σφάλμα κατά τη μετάδοση πληροφορίας.

Στο συγκεκριμένο παράδειγμα, η γεωμετρία του επιπέδου Fano χρησιμοποιείται για να εντοπιστεί η λανθασμένη απάντηση. Μόλις διορθωθεί, οι πρώτες τέσσερις δυαδικές θέσεις αποκαλύπτουν τον αριθμό από \(0\) έως \(15\).

Και ξαφνικά ένα παιχνίδι ερωτήσεων γίνεται Θεωρία Πληροφορίας:

Ερωτήσεις Ναι/Όχι
↓
δυαδικά ψηφία
↓
ψέματα
↓
σφάλματα μετάδοσης
↓
κώδικες διόρθωσης σφαλμάτων

📈 Και αν έχουμε πολλές ερωτήσεις;

Για σταθερό αριθμό \(k\) επιτρεπόμενων ψεμάτων, καθώς ο αριθμός \(q\) των ερωτήσεων γίνεται πολύ μεγάλος, το μέγιστο πλήθος πιθανών τιμών που μπορούμε να αντιμετωπίσουμε συμπεριφέρεται ασυμπτωτικά ως

\[ \boxed{ U_k(q)\sim 2^q \binom{q}{k}^{-1} } \qquad (q\to\infty). \]

Για σταθερό \(k\), επειδή

\[ \binom{q}{k}\sim\frac{q^k}{k!}, \]

μπορούμε να το διαβάσουμε και ως

\[ U_k(q)\sim \frac{2^q k!}{q^k}. \]

Το εντυπωσιακό είναι ότι, παρά τα ψέματα, ο αριθμός των περιπτώσεων που μπορούμε να διακρίνουμε εξακολουθεί να αυξάνεται εκθετικά με τον αριθμό των ερωτήσεων.

🤔 Μια τελευταία σκέψη

Αν γνωρίζουμε ότι κάποιος μπορεί να μας πει ψέματα, δεν προσπαθούμε απλώς να συγκεντρώσουμε περισσότερες πληροφορίες.

Πρέπει να οργανώσουμε τις ερωτήσεις έτσι ώστε η ίδια η πληροφορία να περιέχει αρκετό πλεονασμό για να αποκαλύψει το ψέμα.

Αυτή είναι ακριβώς η ιδέα που βρίσκεται πίσω από πολλούς κώδικες διόρθωσης σφαλμάτων: προσθέτουμε ελεγχόμενο πλεονασμό, ώστε το μήνυμα να μπορεί να ανακτηθεί ακόμη και όταν μέρος της πληροφορίας αλλοιωθεί.

Πηγές και περαιτέρω ανάγνωση:
Joel Spencer – Ulam's Searching Game with a Fixed Number of Lies, Theoretical Computer Science (1992)
Theorem of the Day – Notes and original references

📚

Έρχεται το πολλαπλό βιβλίο ΝΕΟ — βρες όλες τις επιλογές εδώΠολλαπλό βιβλίο ΝΕΟ — 437 βιβλία σε PDF

PDF & Ψηφιακά Μαθησιακά Αντικείμενα — χωρίς εγγραφή • Portify

📚 437 βιβλία🎬 22.000+ Ψηφιακά Μαθησιακά Αντικείμενα

Δες τα βιβλία →