IMC 2017/1/3

#1

Για κάθε θετικό ακέραιο

, γράφουμε P(m)

για το γινόμενο των θετικών διαιρετών του

(π.χ.

). Για κάθε θετικό ακέραιο

, ορίζουμε την ακολουθία

$\displaystyle{a_1(n)=n,\quad a_{k+1}(n)=P(a_k(n))\quad (k=1,2,\dots,2016).}$

Να αποφασιστεί αν για κάθε σύνολο $S\subset\{1,2,\dots,2017\}$ , υπάρχει θετικός ακέραιος

ώστε να ικανοποιείται η πιο κάτω συνθήκη:

Για κάθε

με $1\leq k\leq 2017$ , ο αριθμός a_k(n)

είναι τέλειο τετράγωνο αν και μόνο αν $k\in S$ .

dement · #2

Η απάντηση είναι θετική.

Ορίζουμε την ακολουθία $(l_{m,n})_{m,n \in \mathbb{N}^*}$ ως $\displaystyle l_{1,n} \equiv n, \ l_{m+1,n} \equiv \frac{l_{m,n} (l_{m,n} + 1)}{2}$ . Παρατηρούμε ότι ισχύει $\displaystyle a_k (2^m) = 2^{l_{k,m}}$ .

Θα αποδείξουμε με επαγωγή στο

το λήμμα:

Για κάθε θετικό ακέραιο

και κάθε ακολουθία $(d_k)_{1 \leqslant k \leqslant n}$ αποτελούμενη από

και

, υπάρχει αριθμός $m \ (0 \leqslant m < 2^n)$ με $l_{k,M} \equiv d_k \mod 2$ για κάθε k,M

με $1 \leqslant k \leqslant n, \ M \equiv m \mod 2^n$ .

Για n=1

ο

ταυτίζεται με την (d_k)

(μήκους

). Έστω ότι ισχύει για n=p

. Εξετάζουμε την περίπτωση n=p+1

.

Για δεδομένο

εξετάζουμε την ισοτιμία του $\displaystyle \frac{m(m+1)}{2} \mod 2^p$ . Η ισότητα $\displaystyle \frac{m(m+1)}{2} \equiv \frac{q(q+1)}{2} \mod 2^p$ ικανοποιείται αν και μόνο αν $m \equiv q$ ή $m \equiv -1-q \mod 2^{p+1}$ . Έτσι, για κάθε υπακολουθία $(d_k)_{2 \leqslant k \leqslant p+1}$ υπάρχουν δύο

με $0 \leqslant m < 2^{p+1}$ και $l_{k,m} \equiv d_k \mod 2$ , ένα άρτιο και ένα περιττό. Για ένα ακριβώς από τα δύο ισχύει επίσης $m = l_{1,m} \equiv d_1 \mod 2$ και αυτό είναι το επιθυμητό

. Αυτό ολοκληρώνει την επαγωγή.

Για δεδομένο υποσύνολο του

παίρνουμε την χαρακτηριστική ακολουθία $(d_k)_{1 \leqslant k \leqslant 2017}$ του συμπληρωματικού του. Έστω

ο αριθμός που της αντιστοιχεί σύμφωνα με το λήμμα. Τότε ο αριθμός 2^m

ικανοποιεί το ζητούμενο.

IMC 2017/1/3

IMC 2017/1/3

Re: IMC 2017/1/3

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