Κάθε αριθμός \(x\) έχει δύο «παιδιά»: το \(x+1\) και το \(x/(x+1)\). Ποιοι είναι όλοι οι απόγονοι του αριθμού 1 — όχι μόνο τα παιδιά του, αλλά τα παιδιά των παιδιών του, επ' άπειρον;
👁️ Δείτε τη Λύση
Οι απόγονοι του 1 είναι ακριβώς όλοι οι θετικοί ρητοί αριθμοί, ο καθένας εμφανιζόμενος ακριβώς μία φορά, πάντα ήδη σε ανάγωγη μορφή.
Αυτή η κατασκευή είναι, στην πραγματικότητα, το διάσημο δέντρο Calkin-Wilf (Neil Calkin και Herbert Wilf, «Recounting the Rationals», 1999/2000). Επαληθεύσαμε προγραμματιστικά: παράγοντας 10 γενιές απογόνων του 1 (2047 κόμβοι συνολικά), δεν εμφανίστηκε καμία επανάληψη, και όλα τα ανάγωγα κλάσματα με αριθμητή/παρονομαστή έως το 15 (143 συνολικά) εμφανίστηκαν, χωρίς εξαίρεση, μέσα σε μόλις 15 γενιές.
Γιατί κάθε απόγονος είναι ήδη ανάγωγος: αν \(x=a/b\) με \(\gcd(a,b)=1\), τότε τα παιδιά του είναι \(a/(a+b)\) και \((a+b)/b\). Αλλά \(\gcd(a,a+b)=\gcd(a,b)=1\) και \(\gcd(a+b,b)=\gcd(a,b)=1\) — άρα και τα δύο παιδιά παραμένουν αυτόματα ανάγωγα, με απλή επαγωγή.
Γιατί κάθε θετικός ρητός εμφανίζεται, ακριβώς μία φορά: το κλειδί είναι ότι κάθε κόμβος έχει έναν μοναδικό «γονέα», τον οποίο μπορούμε να βρούμε αντιστρέφοντας τη σχέση: αν \(x=p/q\) με \(pq\), ο γονέας είναι \((p-q)/q\). Αυτό είναι, ουσιαστικά, ο αλγόριθμος του Ευκλείδη για την εύρεση του ΜΚΔ! Αφού το άθροισμα αριθμητή+παρονομαστή μειώνεται αυστηρά σε κάθε βήμα προς τον γονέα, η διαδικασία τερματίζει πάντα, μετά από πεπερασμένα βήματα, ακριβώς στο 1. Επαληθεύσαμε αυτό ακριβώς με τυχαίους ρητούς αριθμούς — ακόμη και το «δύσκολο» \(391/393\) φτάνει στο 1 μετά από 197 βήματα, πάντα με μοναδικό, καθορισμένο μονοπάτι.
Αφού κάθε θετικός ρητός έχει έναν μοναδικό τέτοιο «πρόγονο-δρόμο» προς το 1, έπεται ότι το 1 είναι πράγματι πρόγονος του, και μάλιστα με έναν μοναδικό τρόπο — ακριβώς η ιδιότητα «ακριβώς μία φορά» που αναζητούσαμε.
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου