🔢 Το Θεώρημα Lambek–Moser — Όταν δύο ακολουθίες μοιράζονται όλους τους θετικούς ακεραίους

Μπορούν δύο διαφορετικές ακολουθίες να μοιράσουν μεταξύ τους όλους τους θετικούς ακεραίους έτσι ώστε κάθε αριθμός να εμφανίζεται ακριβώς μία φορά;

Το Θεώρημα Lambek–Moser δίνει μια κομψή απάντηση και συνδέει αυτή την ιδέα με μια ιδιαίτερη έννοια «αντίστροφων» ακολουθιών.

🔹 Αντίστροφες ακολουθίες

Δύο ακολουθίες \(f(n)\) και \(f^*(n)\) ονομάζονται αντίστροφες όταν

\[ f^*(n)=k \qquad\text{όποτε}\qquad f(k)

Με άλλα λόγια, η \(f^*(n)\) καταγράφει ουσιαστικά πόσοι όροι της \(f\) βρίσκονται πριν από μια συγκεκριμένη θέση.

🔹 Συμπληρωματικές ακολουθίες

Δύο ακολουθίες \(F(n)\) και \(G(n)\) λέγονται συμπληρωματικές όταν, αν τις ενώσουμε, κάθε θετικός ακέραιος εμφανίζεται ακριβώς μία φορά.

Το θεώρημα συνδέει τις δύο έννοιες με έναν εντυπωσιακά απλό τρόπο:

\[ \boxed{ F(n)=f(n)+n } \]

και

\[ \boxed{ G(n)=f^*(n)+n } \]

Υπό τις κατάλληλες συνθήκες μονοτονίας που αναφέρονται στο θεώρημα, οι \(F\) και \(G\) είναι συμπληρωματικές αν και μόνο αν οι \(f\) και \(f^*\) είναι αντίστροφες.

🔎 Το παράδειγμα

Στο κείμενο εμφανίζεται, για παράδειγμα, η ακόλουθη κατανομή:

\[ F(n)=1,2,3,\;6,\;8,\;10,\;11,\ldots \]

\[ G(n)=4,5,\;7,\;9,\;12,\ldots \]

Αν τις διαβάσουμε μαζί, βλέπουμε:

\[ 1,2,3,4,5,6,7,8,9,10,11,12,\ldots \]

Κανένας θετικός ακέραιος δεν λείπει και κανένας δεν εμφανίζεται δύο φορές.

💡 Η βασική ιδέα της απόδειξης

Θέτουμε

\[ f(n)=F(n)-n, \qquad f^*(n)=G(n)-n. \]

Η απόδειξη παρακολουθεί τη θέση ενός φυσικού αριθμού \(N\) μέσα στις δύο συμπληρωματικές ακολουθίες. Αν \(N=F(r)\), τότε οι προηγούμενες θέσεις που δεν έχουν καταληφθεί από την \(F\) πρέπει να έχουν καταληφθεί από την \(G\). Αυτή ακριβώς η καταμέτρηση μετατρέπεται στη σχέση που χαρακτηρίζει τις αντίστροφες ακολουθίες.

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

🔢 Δύο ακολουθίες — κανένα κενό, καμία επανάληψη.

📚

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

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

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

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