IMC 2017/1/3

Συντονιστής: Demetres

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

IMC 2017/1/3

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Αύγ 02, 2017 7:17 pm

Για κάθε θετικό ακέραιο m, γράφουμε P(m) για το γινόμενο των θετικών διαιρετών του m (π.χ. P(6)=36). Για κάθε θετικό ακέραιο n, ορίζουμε την ακολουθία

\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\}, υπάρχει θετικός ακέραιος n ώστε να ικανοποιείται η πιο κάτω συνθήκη:

Για κάθε k με 1\leq k\leq 2017, ο αριθμός a_k(n) είναι τέλειο τετράγωνο αν και μόνο αν k\in S.



Λέξεις Κλειδιά:
dement
Διευθύνον Μέλος
Δημοσιεύσεις: 1405
Εγγραφή: Τρί Δεκ 23, 2008 10:11 am

Re: IMC 2017/1/3

#2

Μη αναγνωσμένη δημοσίευση από dement » Δευ Αύγ 07, 2017 11:39 am

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

Ορίζουμε την ακολουθία (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}}.

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

Για κάθε θετικό ακέραιο n και κάθε ακολουθία (d_k)_{1 \leqslant k \leqslant n} αποτελούμενη από 0 και 1, υπάρχει αριθμός 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 ο m ταυτίζεται με την (d_k) (μήκους 1). Έστω ότι ισχύει για n=p. Εξετάζουμε την περίπτωση n=p+1.

Για δεδομένο m εξετάζουμε την ισοτιμία του \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} υπάρχουν δύο m με 0 \leqslant m < 2^{p+1} και l_{k,m} \equiv d_k \mod 2, ένα άρτιο και ένα περιττό. Για ένα ακριβώς από τα δύο ισχύει επίσης m = l_{1,m} \equiv d_1 \mod 2 και αυτό είναι το επιθυμητό m. Αυτό ολοκληρώνει την επαγωγή.

Για δεδομένο υποσύνολο του S παίρνουμε την χαρακτηριστική ακολουθία (d_k)_{1 \leqslant k \leqslant 2017} του συμπληρωματικού του. Έστω m ο αριθμός που της αντιστοιχεί σύμφωνα με το λήμμα. Τότε ο αριθμός 2^m ικανοποιεί το ζητούμενο.


Δημήτρης Σκουτέρης

Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

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

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