Απίστευτοι Αριθμοί

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

harrisp
Δημοσιεύσεις: 547
Εγγραφή: Σάβ Μαρ 28, 2015 8:49 pm

Απίστευτοι Αριθμοί

#1

Μη αναγνωσμένη δημοσίευση από harrisp » Σάβ Απρ 22, 2017 11:11 am

Ένας απίστευτος αριθμός είναι ένας θετικός ακέραιος της μορφής:

2^{a_1}+2^{a_2}+ \cdots+ 2^{a_{100}},

με a_1,a_2, \cdots, a_{100} μη αρνητικούς ακεραίους, όχι απαραίτητα διαφορετικούς.

Να βρείτε τον μικρότερο θετικό ακέραιο n του οποίου τα πολλαπλάσια δεν είναι απίστευτοι αριθμοί!



Λέξεις Κλειδιά:
harrisp
Δημοσιεύσεις: 547
Εγγραφή: Σάβ Μαρ 28, 2015 8:49 pm

Re: Απίστευτοι Αριθμοί

#2

Μη αναγνωσμένη δημοσίευση από harrisp » Τρί Δεκ 26, 2017 9:59 am

ΧΑΡΗΣ ΤΙΟΥΡΙΝΓΚ έγραψε:
Σάβ Απρ 22, 2017 11:11 am
Ένας απίστευτος αριθμός είναι ένας θετικός ακέραιος της μορφής:

2^{a_1}+2^{a_2}+ \cdots+ 2^{a_{100}},

με a_1,a_2, \cdots, a_{100} μη αρνητικούς ακεραίους, όχι απαραίτητα διαφορετικούς.

Να βρείτε τον μικρότερο θετικό ακέραιο n του οποίου τα πολλαπλάσια δεν είναι απίστευτοι αριθμοί!
Επαναφορά!


Άβαταρ μέλους
Ορέστης Λιγνός
Δημοσιεύσεις: 1620
Εγγραφή: Κυρ Μάιος 08, 2016 7:19 pm
Τοποθεσία: Χαλάνδρι Αττικής

Re: Απίστευτοι Αριθμοί

#3

Μη αναγνωσμένη δημοσίευση από Ορέστης Λιγνός » Παρ Ιουν 01, 2018 2:14 pm

ΧΑΡΗΣ ΤΙΟΥΡΙΝΓΚ έγραψε:
Σάβ Απρ 22, 2017 11:11 am
Ένας απίστευτος αριθμός είναι ένας θετικός ακέραιος της μορφής:

2^{a_1}+2^{a_2}+ \cdots+ 2^{a_{100}},

με a_1,a_2, \cdots, a_{100} μη αρνητικούς ακεραίους, όχι απαραίτητα διαφορετικούς.

Να βρείτε τον μικρότερο θετικό ακέραιο n του οποίου τα πολλαπλάσια δεν είναι απίστευτοι αριθμοί!
Θα αποδείξουμε πρώτα την εξής Ιδιότητα:

Ιδιότητα 1

Κάθε αριθμός s < 2^{101}-1, έχει ένα τουλάχιστον απίστευτο πολλαπλάσιο.

Απόδειξη

Από το δεκαδικό σύστημα γνωρίζουμε ότι κάθε αριθμός γράφεται στην μορφή  10^{a_1}+ 10^{a_2}+ \cdots+10^{a_{k}}.

Άρα, στο δυαδικό σύστημα, κάθε αριθμός <2^{101}-1 γράφεται στην μορφή  s=2^{a_1}+ 2^{a_2}+ \cdots  2^{a_k}, με k \leqslant 100. Επομένως, παίρνοντας αρκετά μεγάλο t, είναι s 2^t=2^{a_1+t}+ 2^{a_2+t}+ \cdots+2^{a_k+t}.

Χρησιμοποιώντας την ιδιότητα 2^{m+1}=2^m+2^m, χωρίζουμε τις δυνάμεις, μέχρι να φτάσουμε ακριβώς 100 όρους.

Επομένως, ο αριθμός s 2^t γράφεται ως άθροισμα 100 δυνάμεων του 2, άρα είναι φανταστικός. \blacksquare.

Το αποτέλεσμα παραπάνω, μας δίνει ότι n \geqslant 2^{101}-1.

Θα δείξουμε ότι γίνεται n=2^{101}-1.

Έστω, ότι υπάρχει αριθμός x, ώστε ο xn να είναι απίστευτος, και έστω επίσης ο αυτό το x είναι το μικρότερο, με αυτήν την ιδιότητα.

Είναι λοιπόν xn=2^{a_1}+2^{a_2}+ \cdots  +2^{a_{100}}, με a_1<a_2< \cdots<a_{100} (μπορούμε να το υποθέσουμε αυτό, γιατί τις ίσες δυνάμεις του 2 τις ''παίρνουμε'' μαζί, οπότε το 2^a+2^a γράφεται 2^{a+1}, και με αυτήν την διαδικασία, όλες οι δυνάμεις είναι διαφορετικές).

Στο σημείο αυτό, θα δείξουμε το εξής :

Ιδιότητα 2

Ισχύει a_{100} \geqslant 101.

Απόδειξη

Αν ισχύει a_{100} \leqslant 100, τότε a_{99}<a_{100} \leqslant 100 \Rightarrow a_{99} \leqslant 99, και όμοια a_i \leqslant i, για κάθε i.

Άρα, xn=2^{a_1}+2^{a_2}+ \cdots  +2^{a_{100}} \leqslant 2^1+2^2+ \cdots 2^{100}=2^{101}-2=n-1 \Rightarrow xn \leqslant n-1<n \Rightarrow x<1, άτοπο. \blacksquare.

Επομένως, a_{100} \geqslant 101 \Rightarrow 2^{a_{100}}-2^{a_{100}-101}=n2^{a_{100}}-101}.

Αν τώρα N=2^{a_1}+2^{a_2}+ \cdots 2^{a_{100}-1}+2^{a_{100}-101} , είναι

N=2^{a_1}+2^{a_2}+ \cdots 2^{a_{100}-1}+2^{a_{100}-101} \equiv 2^{a-1}+2^{a_2}+ \cdots 2^{a_{100}-1}+2^{a_{100}}=xn \pmod n.

Άρα,ο αριθμός N είναι πολλαπλάσιο του n, και εύκολα διαπιστώνουμε ότι N<xn, που αντίκειται στην ελαχιστότητα του x.

Τελικά, καταλήξαμε στο ότι κανένα πολλαπλάσιο του 2^{101}-1 δεν είναι απίστευτος αριθμός, οπότε \textnormal{\en min} \, n=2^{101}-1.


Κερδίζουμε ό,τι τολμούμε !
Απάντηση

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

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

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