🐦 Η Αρχή του Περιστερώνα — Ένα όμορφο πρόβλημα με 51 αριθμούς

Η Αρχή του Περιστερώνα (Pigeonhole Principle) είναι μία από τις απλούστερες αλλά και πιο ισχυρές ιδέες της Συνδυαστικής.

Η βασική της μορφή λέει:

Αν τοποθετήσουμε περισσότερα από \(n\) αντικείμενα σε \(n\) κουτιά, τότε τουλάχιστον ένα κουτί θα περιέχει δύο ή περισσότερα αντικείμενα.

Η δύναμή της φαίνεται ιδιαίτερα σε προβλήματα όπου τα «περιστέρια» και οι «φωλιές» δεν είναι καθόλου προφανή.

🔢 Το πρόβλημα

Επιλέγουμε 51 διαφορετικούς αριθμούς από το σύνολο

\[ \{1,2,3,\ldots,99,100\}. \]

❓ Να αποδείξετε ότι ανάμεσα στους 51 αριθμούς υπάρχουν δύο που δεν έχουν κανέναν κοινό πρώτο διαιρέτη.

💡 Εμφάνιση υπόδειξης

Χώρισε τους \(100\) αριθμούς σε 50 ζεύγη διαδοχικών αριθμών:

\[ (1,2),\;(3,4),\;(5,6),\ldots,(99,100). \]

Τώρα έχουμε \(51\) επιλεγμένους αριθμούς αλλά μόνο \(50\) ζεύγη.

Τι εγγυάται λοιπόν η Αρχή του Περιστερώνα;

Και όταν εντοπίσεις δύο επιλεγμένους αριθμούς της μορφής

\[ k,\qquad k+1, \]

σκέψου αν δύο διαδοχικοί ακέραιοι μπορούν να έχουν κοινό πρώτο διαιρέτη.

💡 Η ομορφιά της ιδέας

Το δύσκολο μέρος δεν είναι η ίδια η Αρχή του Περιστερώνα. Είναι να ανακαλύψουμε ποια πρέπει να είναι τα «κουτιά». Εδώ, η σωστή επιλογή των 50 ζευγών μετατρέπει αμέσως ένα πρόβλημα διαιρετότητας σε ένα απλό συνδυαστικό επιχείρημα.

📚

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

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

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

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