Pigeonhole Principle
Η Αρχή Περιστερώνα είναι μία από τις πιο απλές και ταυτόχρονα πιο ισχυρές ιδέες στα μαθηματικά! Η βασική της μορφή λέει:
Φαίνεται αυτονόητο, αλλά οι εφαρμογές της είναι εντυπωσιακές! Η γενικευμένη μορφή λέει:
Αν βάλεις \(kn + 1\) περιστέρια σε \(n\) τρύπες, τότε τουλάχιστον μία τρύπα θα έχει \(k+1\) ή περισσότερα περιστέρια!
🔑 Πότε να τη διαλέξεις:
Σε μια αίθουσα με 13 άτομα, αποδείξτε ότι τουλάχιστον 2 άτομα γεννήθηκαν τον ίδιο μήνα.
Hint: Ποια είναι τα "περιστέρια" και ποιες οι "τρύπες";
Περιστέρια: Τα 13 άτομα
Τρύπες: Οι 12 μήνες του χρόνου
Κλειδί: 13 > 12, άρα κάποια "τρύπα" (μήνας) έχει 2+ "περιστέρια" (άτομα)!
Βήμα 1 - Εντοπισμός περιστεριών και τρυπών:
Βήμα 2 - Εφαρμογή της Αρχής:
Έχουμε \(n + 1 = 13\) περιστέρια και \(n = 12\) τρύπες.
Από την Αρχή Περιστερώνα: αφού \(13 > 12\), τουλάχιστον μία "τρύπα" (μήνας) πρέπει να έχει τουλάχιστον 2 "περιστέρια" (άτομα)!
Συμπέρασμα: Τουλάχιστον 2 άτομα γεννήθηκαν τον ίδιο μήνα. ✓
🔑 Κλειδί: Η Αρχή Περιστερώνα μας έδωσε την εγγύηση ύπαρξης!
Διαλέγουμε 5 σημεία μέσα σε ένα ισόπλευρο τρίγωνο με πλευρά 1.
Αποδείξτε ότι τουλάχιστον δύο από αυτά τα σημεία απέχουν το πολύ \(\frac{1}{2}\).
Hint: Πώς μπορείς να χωρίσεις το τρίγωνο σε "τρύπες";
Σκέψου: αν το χωρίσεις σε 4 μικρότερα ισόπλευρα τρίγωνα με πλευρά \(\frac{1}{2}\), τι συμβαίνει;
Κλειδί: 5 σημεία, 4 τρίγωνα → Κάποιο τρίγωνο έχει 2+ σημεία!
Βήμα 1 - Δημιουργία "τρυπών":
Χωρίζουμε το ισόπλευρο τρίγωνο με πλευρά 1 σε 4 μικρότερα ισόπλευρα τρίγωνα με πλευρά \(\frac{1}{2}\).
(Συνδέουμε τα μέσα των πλευρών)
Βήμα 2 - Εντοπισμός περιστεριών και τρυπών:
Βήμα 3 - Εφαρμογή Αρχής Περιστερώνα:
Αφού \(5 > 4\), τουλάχιστον ένα μικρό τρίγωνο περιέχει τουλάχιστον 2 σημεία.
Βήμα 4 - Απόσταση:
Σε ένα ισόπλευρο τρίγωνο με πλευρά \(\frac{1}{2}\), η μέγιστη απόσταση μεταξύ δύο σημείων είναι \(\frac{1}{2}\) (η πλευρά).
Άρα τα δύο σημεία που βρίσκονται στο ίδιο μικρό τρίγωνο απέχουν το πολύ \(\frac{1}{2}\)! ✓
🔑 Κλειδί: Χωρίσαμε το χώρο σε "τρύπες" για να εφαρμόσουμε την Αρχή!
Διαλέγουμε 101 αριθμούς από το σύνολο \(\{1, 2, 3, \ldots, 200\}\).
Αποδείξτε ότι υπάρχουν δύο αριθμοί τέτοιοι ώστε ο ένας να διαιρεί τον άλλον.
Hint: Κάθε αριθμό \(n\) μπορείς να γράψεις ως \(n = 2^k \cdot m\) όπου \(m\) είναι περιττός!
Σκέψου: πόσοι περιττοί αριθμοί υπάρχουν στο \(\{1, 2, \ldots, 200\}\);
Κλειδί: Οι περιττοί είναι οι "τρύπες"!
Βήμα 1 - Παραγοντοποίηση:
Κάθε αριθμό \(n\) μπορούμε να γράψουμε ως:
\[n = 2^k \cdot m\]
όπου \(k \geq 0\) και \(m\) είναι περιττός.
Βήμα 2 - Πλήθος περιττών:
Στο σύνολο \(\{1, 2, 3, \ldots, 200\}\), οι περιττοί είναι: \(1, 3, 5, \ldots, 199\).
Πλήθος: \(\frac{200}{2} = 100\) περιττοί.
Βήμα 3 - Εντοπισμός περιστεριών και τρυπών:
Βήμα 4 - Εφαρμογή Αρχής Περιστερώνα:
Αφού \(101 > 100\), υπάρχουν τουλάχιστον δύο αριθμοί \(n_1, n_2\) με τον ίδιο περιττό παράγοντα \(m\)!
Έστω:
\[n_1 = 2^{k_1} \cdot m, \quad n_2 = 2^{k_2} \cdot m\]
Βήμα 5 - Συμπέρασμα:
Αν \(k_1 < k_2\), τότε \(n_1 = 2^{k_1} \cdot m\) διαιρεί το \(n_2 = 2^{k_2} \cdot m\)!
(Γιατί \(n_2 = 2^{k_2 - k_1} \cdot n_1\))
Άρα υπάρχουν δύο αριθμοί όπου ο ένας διαιρεί τον άλλον! ✓
🔑 Κλειδί: Η έξυπνη επιλογή "τρυπών" (οι περιττοί) μας έδωσε τη λύση!
Ερώτηση: Πόσα άτομα χρειάζονται για να είμαστε σίγουροι ότι 3 έχουν γενέθλια τον ίδιο μήνα;