Το 1986, ο διάσημος εκλαϊκευτής των μαθηματικών Ross Honsberger παρουσίασε ένα πρόβλημα που βασίζεται στην Αρχή των Περιστερώνων — μια από τις πιο απλές αλλά πανίσχυρες ιδέες της συνδυαστικής.
Η διατύπωση του Honsberger ήταν η εξής:
Αν S είναι ένα υποσύνολο του {1, 2, …, 99} με 10 στοιχεία, τότε υπάρχουν δύο διακριτά (χωρίς κοινά στοιχεία) υποσύνολα A και B του S με το ίδιο άθροισμα.
Για παράδειγμα, αν S = {3, 9, 14, 21, 27, 35, 42, 59, 63, 76}, τότε τα υποσύνολα A = {14, 63} και B = {35, 42} έχουν και τα δύο άθροισμα 77.
Η απόδειξη με την Αρχή των Περιστερώνων
Η απόδειξη είναι εκπληκτικά απλή. Υπάρχουν 2¹⁰ − 1 = 1023 μη κενά υποσύνολα του S. Το μικρότερο δυνατό άθροισμα είναι 1, και το μέγιστο είναι 945 (δηλαδή 90 + 91 + … + 99). Έτσι υπάρχουν 945 “κουτιά” (τα δυνατά αθροίσματα), αλλά 1023 “περιστέρια” (υποσύνολα). Σύμφωνα με την Αρχή των Περιστερώνων, τουλάχιστον δύο υποσύνολα πρέπει να πέσουν στο ίδιο κουτί — να έχουν δηλαδή το ίδιο άθροισμα.
Η παραλλαγή του Andy Liu: “Ιδιωτικά Διαμερίσματα”
Ο Καναδός μαθηματικός Andy Liu έθεσε το ερώτημα αντίστροφα: Υπάρχει κάποιο υποσύνολο S του {1, 2, …, n} τέτοιο ώστε κανένα ζευγάρι διακριτών υποσυνόλων του να μην έχει το ίδιο άθροισμα;
Με άλλα λόγια, κάθε “περιστέρι” (υποσύνολο) να έχει το δικό του “διαμέρισμα” (άθροισμα).
Αυτό το πρόβλημα αποτέλεσε μέρος του AIME 1986 και αργότερα του USA Mathematical Talent Search.
Αποτελέσματα για μικρές τιμές του n
- Για n = 15, η μέγιστη λύση είναι S₁₅ = {15, 14, 13, 11, 9} με άθροισμα 61.
- Για n = 25, η λύση είναι S₂₅ = {25, 24, 23, 21, 18, 12} με άθροισμα 123.
Και στις δύο περιπτώσεις, το σύνολο S προκύπτει μέσω του λεγόμενου “Greedy Algorithm” — δηλαδή διαλέγουμε πάντα τον μεγαλύτερο δυνατό αριθμό που δεν οδηγεί σε αντίφαση.
Προτεινόμενη Εξερεύνηση
Μπορείς να πειραματιστείς με αυτό το πρόβλημα προγραμματιστικά: να γράψεις έναν αλγόριθμο που αναζητά τα μέγιστα υποσύνολα Sₙ με ιδιότητα “ιδιωτικού αθροίσματος” για διάφορες τιμές του n.
Η υπόθεση είναι ότι η λύση είναι πάντα μοναδική και ακολουθεί τον κανόνα της “άπληστης” επιλογής — κάτι που μέχρι σήμερα δεν έχει αποδειχθεί πλήρως για όλα τα n.
📚 Συνοψίζοντας
- Η Αρχή των Περιστερώνων εξασφαλίζει ότι οι τιμές “συγκρούονται”.
- Ο Andy Liu αναζητά συνθήκες ώστε οι συγκρούσεις να εξαλειφθούν.
- Η μέθοδος Greedy δημιουργεί βέλτιστα υποσύνολα για μικρές τιμές του n.
Μπορεί, λοιπόν, η φύση να δώσει σε κάθε μαθηματικό “περιστέρι” το δικό του διαμέρισμα; Ίσως όχι πάντα — αλλά η αναζήτηση συνεχίζεται!
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου