Θέμα Εισαγωγικών Scuola Normale Superiore 2019-20 (2)

Al.Koutsouridis · #1

(i) Να αποδείξετε, ότι κάθε μη αρνητικός ακέραιο

μπορεί να εκφραστεί με μοναδικό τρόπο ως άθροισμα διακεριμένων προσθετέων της μορφής $2^{j}$ , όπου

μη αρνητικός ακέραιος. (Η έκφραση αυτή αναπαριστά την δυαδική μορφή του

. Σας ζητείτε η απόδειξη της ύπαρξης και μοναδικότητας αυτής της μορφής, δεν επιτρέπεται να τα θεωρήσετε δεδομένα.)

(ii) Να αποδείξετε, ότι υπάρχουν άπειροι ακέραιοι

που μπορούν να γραφούν ως το άθροισμα διακεκριμένων προσθετέων της μορφής 2^j+1

όπου

μη αρνητικός ακέραιος.

(iii) Να αποδείξετε ότι υπάρχουν άπειροι μη αρνητικοί ακέραιοι

, οι οποίοι δεν μπορούν να εκφραστούν στην μορφή του ερωτήματος (ii).

#2

Κάνω το (iii) που είναι και το πιο ενδιαφέρον. Δίνω δύο τρόπους:

Πρώτος τρόπος: Θα δείξουμε ότι αν δεν μπορούμε να γράψουμε τον αριθμό

, τότε δεν μπορούμε να γράψουμε ούτε τον αριθμό $2^{k+1} + k+1$ . Αφού δεν μπορούμε να γράψουμε το

τότε δεν θα μπορούμε ούτε τους $1,4,37,\ldots$ .

Απόδειξη: Επειδή $(2^0+1)+(2^1+1) + \cdots + (2^k+1) = (2^{k+1}-1) + (k+1) = 2^{k+1}+k$ , αν θέλουμε να γράψουμε τον $2^{k+1} + k+1$ πρέπει να χρησιμοποιήσουμε τον $2^{k+1}+1$ . (Ασφαλώς δεν μπορούμε να χρησιμοποιήσουμε τον $2^{k+2}+1$ ή μεγαλύτερο αφού επαγωγικά είναι εύκολο να δειχθεί ότι $2^{k+1} > k$ οπότε θα έχουμε $2^{k+2}+1 > 2^{k+1} + k + 1$ . ) Αν όμως χρησιμοποιήσω τον $2^{k+1}+1$ τότε θα πρέπει να μπορώ να γράψω και τον

ως τέτοιο άθροισμα, άτοπο.

Δεύτερος τρόπος: Έστω a_n

το πλήθος των ακεραίων στο διάστημα [0,n]

που μπορούν να γραφτούν σε αυτή τη μορφή. Αν χρησιμοποιήσουμε μόνο τους αριθμούς $2^0+1,2^1+1,\ldots,2^k+1$ , μπορούμε να πάρουμε το πολύ $2^{k+1}$ αριθμούς. Αυτοί θα είναι στο διάστημα $[0,2^{k+1}+k]$ . Από αυτούς, τουλάχιστον a_k

θα είναι στο διάστημα $[2^{k+1}+1,2^{k+1}+k]$ . (Επειδή $(2^0+1)+(2^1+1) + \cdots + (2^k+1) = 2^{k+1}+k$ , τότε μπορώ να γράψω τον $2^{k+1}+\ell$ αν και μόνο αν μπορώ να γράψω και τον $k-\ell$ .) Επομένως παίρνω $a_{2^{k+1}} \leqslant 2^{k+1}-a_k$ . Αν τώρα γράψω b_n

το πλήθος των ακεραίων στο διάστημα [0,n]

που δεν μπορούν να γραφτούν σε αυτή τη μορφή παίρνω $b_{2^{k+1}} + b_k\geqslant k+2$ . Επειδή προφανώς $b_{2^{k+1}} \geqslant b_k$ , τότε έχω $b_{2^{k+1}} \geqslant (k+2)/2$ . Δηλαδή για κάθε

μπορώ να βρω τουλάχιστον (k+2)/2

μη αρνητικούς ακεραίους που δεν μπορούν να γραφτούν στη ζητούμενη μορφή.

Θέμα Εισαγωγικών Scuola Normale Superiore 2019-20 (2)

Θέμα Εισαγωγικών Scuola Normale Superiore 2019-20 (2)

Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2019-20 (2)

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