Putnam 2018/B3

Συντονιστές: cretanman, silouan, rek2

Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8184
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Putnam 2018/B3

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Δεκ 19, 2018 11:14 am

Να βρεθούν όλοι οι θετικοί ακέραιοι n < 10^{100} ώστε ταυτόχρονα ο n να διαιρεί τον 2^n, ο n-1 να διαιρεί τον 2^n-1 και ο n-2 να διαιρεί τον 2^n - 2.



Λέξεις Κλειδιά:
Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 793
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Re: Putnam 2018/B3

#2

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Τετ Δεκ 19, 2018 3:33 pm

Υποθέτουμε για ευνόητους λόγους n\geq 3.

Προφανώς πρέπει 2^m=n, m\geq 2, ώστε να ικανοποιείται η πρώτη συνθήκη. Κάθε τέτοιο n την ικανοποιεί.

Σύμφωνα με τη δεύτερη συνθήκη πρέπει 2^m-1|2^{2^m}-1.

Θα χρησιμοποιήσουμε το εξής λήμμα:

Αν 2^a-1|2^b-1, τότε a|b και αντίστροφα.

Προφανώς b\geq a και μπορούμε να θέσουμε b=ka+l, όπου k θετικός ακέραιος και l μη αρνητικός ακέραιος μικρότερος του a.

Ισχύει ότι 2^a-1|2^{ak}-1

Τότε είναι 2^a-1|2^b-1\Leftrightarrow 2^a-1|2^b-1-2^{ka}+1\Leftrightarrow 2^a-1|2^b-2^{ka}\Leftrightarrow 2^a-1|2^{ka}(2^l-1)\Leftrightarrow 2^a-1|2^l-1, που ισχύει αν και μόνο αν 2^l-1=0 ή 2^l-1\geq 2^a-1, που δεν ισχύει. Άρα 2^l=1 και l=0.

Πίσω στην άσκηση:

Σύμφωνα με το λήμμα πρέπει m|2^m, άρα m=2^l, όπου l\geq 1. Άρα n=2^{2^l}, l\geq 1. Κάθε τέτοιο n ικανοποιεί τις δύο πρώτες συνθήκες.

Σύμφωνα με την τρίτη συνθήκη πρέπει 2^{2^l}-2|2^{2^{2^l}}-2\Leftrightarrow 2^{2^l-1}-1|2^{2^{2^l}-1}-1.

Το λήμμα υποδεικνύει ότι 2^l-1|2^{2^l}-1, άρα από τα παραπάνω συμπεραίνουμε ότι l=2^r, όπου r\geq 0.

Συνοψίζοντας n=2^{2^{2^r}}, r\geq 0. Κάθε τέτοιο n ικανοποιεί όλες τις συνθήκες.

Πρέπει ωστόσο n<10^{100}.

Για r=3, έχουμε n=2^{256}<2^{258}<8^{86}<10^{100}.

Για r=4 ωστόσο έχουμε 2^{65536}>16^{16384}>10^{100}.

Συνεπώς τα μόνα n που ικανοποιούν είναι αυτά στα οποία 3\geq r\geq 0, δηλαδή n=4, n=16, n=65536, n=2^{256}.


Houston, we have a problem!
Απάντηση

Επιστροφή σε “Θεωρία Αριθμών - Προχωρημένο Επίπεδο (Seniors)”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης