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

harrisp · #1

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

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

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

Να βρείτε τον μικρότερο θετικό ακέραιο

του οποίου τα πολλαπλάσια δεν είναι απίστευτοι αριθμοί!

harrisp · #2

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

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

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

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

Επαναφορά!

Ορέστης Λιγνός · #3

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

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

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

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

Θα αποδείξουμε πρώτα την εξής Ιδιότητα:

Ιδιότητα 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$ . Επομένως, παίρνοντας αρκετά μεγάλο

, είναι $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

δυνάμεων του

, άρα είναι φανταστικός. $\blacksquare$ .

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

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

Έστω, ότι υπάρχει αριθμός

, ώστε ο

να είναι απίστευτος, και έστω επίσης ο αυτό το

είναι το μικρότερο, με αυτήν την ιδιότητα.

Είναι λοιπόν $xn=2^{a_1}+2^{a_2}+ \cdots +2^{a_{100}}$ , με $a_1<a_2< \cdots<a_{100}$ (μπορούμε να το υποθέσουμε αυτό, γιατί τις ίσες δυνάμεις του

τις ''παίρνουμε'' μαζί, οπότε το 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$ , για κάθε

.

Άρα, $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<xn

, που αντίκειται στην ελαχιστότητα του

.

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

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

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

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

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

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