🥣 Το πρόβλημα της σούπας: δύσκολο μέχρι να δεις το σωστό μονοπάτι

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

ΤΟ ΠΡΟΒΛΗΜΑ

Έστω \(n\) θετικός ακέραιος. Επιλέγουμε \(n+1\) διαφορετικούς αριθμούς από το σύνολο

\[\{1,2,3,\ldots,2n\}.\]

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

Σχετικά πρώτοι λέγονται δύο ακέραιοι των οποίων ο μέγιστος κοινός διαιρέτης είναι 1. Δεν απαιτείται να είναι οι ίδιοι πρώτοι αριθμοί: για παράδειγμα, οι 8 και 15 είναι σχετικά πρώτοι.

Πριν συνεχίσετε, αξίζει να δοκιμάσετε μόνοι σας. Η πρόταση πρέπει να ισχύει για κάθε δυνατό τρόπο επιλογής των \(n+1\) αριθμών. Το να εξετάζουμε ξεχωριστά τους άρτιους, τους περιττούς ή τις παραγοντοποιήσεις τους οδηγεί γρήγορα σε έναν λαβύρινθο. Η λύση βρίσκεται στον τρόπο με τον οποίο θα οργανώσουμε ολόκληρο το σύνολο.

Μικρή υπόδειξη — ανοίξτε μόνο αν τη χρειάζεστε

Μη χωρίσετε τους αριθμούς σύμφωνα με τους διαιρέτες τους. Χωρίστε το σύνολο \(\{1,2,\ldots,2n\}\) σε \(n\) πολύ απλά ζεύγη.

Η ιστορία του προβλήματος

Ο Paul Erdős συνήθιζε να δοκιμάζει τη μαθηματική διαίσθηση νέων ανθρώπων με προβλήματα που δεν απαιτούσαν εξειδικευμένες γνώσεις, αλλά μια καθαρή ιδέα. Σύμφωνα με αφήγηση του ίδιου, γνώρισε τον Ούγγρο Louis —ή Lajos— Pósa πριν εκείνος συμπληρώσει τα δώδεκα χρόνια του και του έθεσε αυτό το ερώτημα την ώρα που έτρωγε.

Ο Erdős είχε χρειαστεί περίπου δέκα λεπτά για να εντοπίσει την πιο απλή απόδειξη. Ο μικρός Pósa, ενώ συνέχιζε τη σούπα του, απάντησε ύστερα από περίπου μισό λεπτό. Ο Erdős παρομοίασε αργότερα τη στιγμή με τη διάσημη ιστορία του νεαρού Gauss και του αθροίσματος \(1+2+\cdots+100\).

Ο Pósa δεν έμεινε απλώς ένα παιδί-θαύμα. Έγινε σημαντικός μαθηματικός με έργο στη συνδυαστική και στη θεωρία γραφημάτων, αλλά και ιδιαίτερα επιδραστικός δάσκαλος μαθηματικών.

Εμφάνιση της λύσης

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

\[(1,2),(3,4),(5,6),\ldots,(2n-1,2n).\]

Έχουμε λοιπόν \(n\) ζεύγη, αλλά έχουμε επιλέξει \(n+1\) αριθμούς. Σύμφωνα με την αρχή του περιστερώνα, τουλάχιστον δύο από τους επιλεγμένους αριθμούς πρέπει να ανήκουν στο ίδιο ζεύγος.

Οι δύο αριθμοί ενός τέτοιου ζεύγους είναι διαδοχικοί. Κάθε κοινός διαιρέτης δύο διαδοχικών ακεραίων διαιρεί και τη διαφορά τους, η οποία είναι 1. Επομένως ο μέγιστος κοινός διαιρέτης τους είναι 1 και οι δύο αριθμοί είναι σχετικά πρώτοι.

\[\gcd(2k-1,2k)=1.\qquad\square\]

Γιατί το \(n+1\) είναι το καλύτερο δυνατό όριο;

Δεν μπορούμε να αντικαταστήσουμε το \(n+1\) με \(n\). Πράγματι, αν επιλέξουμε όλους τους άρτιους αριθμούς

\[2,4,6,\ldots,2n,\]

έχουμε ακριβώς \(n\) αριθμούς, αλλά κανένα ζεύγος τους δεν είναι σχετικά πρώτο, αφού όλοι έχουν κοινό διαιρέτη το 2. Άρα το πλήθος \(n+1\) της εκφώνησης δεν είναι αυθαίρετο· είναι το μικρότερο που εγγυάται το συμπέρασμα.

Η κρυμμένη ιδέα: το πρόβλημα μοιάζει να αφορά τους πρώτους διαιρέτες, αλλά η λύση του αφορά τη διάταξη των αριθμών. Μόλις οι \(2n\) αριθμοί γίνουν \(n\) ζεύγη, η απόδειξη είναι σχεδόν αναπόφευκτη.

Ιστορική αναφορά: Paul Erdős, «I will talk about the child prodigies which I have known».

📚

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

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

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

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

Σχετικά άρθρα