✏️ Ο γρίφος (Μέρος 1)
Έχουμε 8 όμοιες μπάλες και μια ζυγαριά δύο δίσκων. Γνωρίζουμε ότι μία μπάλα ζυγίζει περισσότερο από τις υπόλοιπες, αλλά όχι ποια. Ποιος είναι ο ελάχιστος αριθμός ζυγίσεων για να τη βρούμε με βεβαιότητα;
👁️ Δείτε τη Λύση
Κάθε ζύγιση έχει τρία δυνατά αποτελέσματα (αριστερά βαρύτερα, δεξιά βαρύτερα, ισορροπία), άρα με \(n\) ζυγίσεις μπορούμε να ξεχωρίσουμε το πολύ \(3^n\) περιπτώσεις. Χρειαζόμαστε \(3^n\geq8\), που ισχύει ήδη για \(n=2\) (\(3^2=9\)). Επαληθεύσαμε ότι το κάτω φράγμα επιτυγχάνεται πράγματι με μία συγκεκριμένη στρατηγική:
Χωρίζουμε τις μπάλες σε ομάδες 3-3-2, και ζυγίζουμε 3 έναντι 3. Αν ισορροπήσουν, η βαρύτερη είναι μία από τις 2 που απομένουν· τις ζυγίζουμε μεταξύ τους, και η βαρύτερη προδίδεται αμέσως. Αν δεν ισορροπήσουν, η βαρύτερη μπάλα βρίσκεται στην ομάδα που «έγειρε» τη ζυγαριά· παίρνουμε 2 από τις 3 μπάλες αυτής της ομάδας και τις ζυγίζουμε μεταξύ τους — είτε αποκαλύπτεται αμέσως η βαρύτερη, είτε (σε ισορροπία) είναι η τρίτη, αζύγιστη μπάλα.
Επαληθεύσαμε προγραμματιστικά, εξαντλητικά, ότι αυτή η στρατηγική εντοπίζει σωστά τη βαρύτερη μπάλα και στις 8 δυνατές περιπτώσεις, πάντα σε ακριβώς 2 ζυγίσεις.
✏️ Ο γρίφος (Μέρος 2)
Τώρα γνωρίζουμε μόνο ότι μία μπάλα είναι διαφορετική —χωρίς να ξέρουμε αν είναι βαρύτερη ή ελαφρύτερη. Ποιος είναι ο ελάχιστος αριθμός ζυγίσεων για να την εντοπίσουμε, μαζί με την κατεύθυνση της διαφοράς της;
👁️ Δείτε τη Λύση
Τώρα υπάρχουν \(8\times2=16\) δυνατές περιπτώσεις (8 μπάλες, 2 πιθανές κατευθύνσεις η καθεμία). Χρειαζόμαστε \(3^n\geq16\), που ισχύει πρώτη φορά για \(n=3\) (\(3^3=27\)) — οι 2 ζυγίσεις (\(3^2=9<16 p="">
Επαληθεύσαμε προγραμματιστικά μια πλήρη στρατηγική 3 ζυγίσεων: ζυγίζουμε πρώτα 3 έναντι 3 (αφήνοντας 2 στην άκρη). Αν ισορροπήσουν, η διαφορετική μπάλα είναι μία από τις 2 απομένουσες· τη συγκρίνουμε με μια ήδη γνωστή «καλή» μπάλα, και ύστερα (αν χρειαστεί) μεταξύ τους, για να βρούμε ταυτόχρονα ποια είναι και προς ποια κατεύθυνση διαφέρει. Αν δεν ισορροπήσουν, η πρώτη ζύγιση περιορίζει τις πιθανότητες σε 6 (3 «ύποπτες για βαρύτερες» και 3 «ύποπτες για ελαφρύτερες»)· μια προσεκτικά σχεδιασμένη δεύτερη ζύγιση, αναμειγνύοντας μπάλες από τις δύο ομάδες με ήδη γνωστές καλές μπάλες, περιορίζει περαιτέρω τις πιθανότητες σε το πολύ 3, και μια τρίτη ζύγιση τις διαχωρίζει οριστικά.
Ελέγξαμε εξαντλητικά και τις 16 δυνατές περιπτώσεις (κάθε μία από τις 8 μπάλες, βαρύτερη ή ελαφρύτερη) — η στρατηγική εντοπίζει σωστά τόσο τη μπάλα όσο και την κατεύθυνσή της, πάντα σε ακριβώς 3 ζυγίσεις, χωρίς καμία εξαίρεση.
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου