EGMO 2018/2

#1

Θεωρήστε το σύνολο
$\displaystyle A = \{1 + \frac{1}{k}:k=1,2,3\ldots \}$

(α) Αποδείξτε ότι κάθε ακέραιος $x \geqslant 2$ μπορεί να γραφεί ως γινόμενο ενός ή περισσοτέρων στοιχείων του

, τα
οποία δεν είναι κατ’ ανάγκη διαφορετικά.

(β) Για κάθε ακέραιο $x \geqslant 2$ , συμβολίζουμε με f(x)

τον ελάχιστο ακέραιο έτσι ώστε το

να μπορεί να γράφεται ως γινόμενο f(x)

σε πλήθος στοιχείων του

, τα οποία δεν είναι κατ’ ανάγκη διαφορετικά.

Αποδείξτε ότι υπάρχουν άπειρα ζεύγη (x,y)

ακεραίων με $x \geqslant 2, y \geqslant 2$ και

$\displaystyle f(xy) < f(x) + f(y).$

(Τα ζεύγη (x_1,y_1)

και

είναι διαφορετικά όταν $x_1 \neq x_2$ ή $y_1 \neq y_2$ .)

gavrilos · #2

Καλησπέρα.

α. Παρατηρούμε ότι ,αν $k\geq 2$ ,τότε $k=\left(1+\frac{1}{1}\right)\left(1+\frac{1}{2}\right)\cdots \left(1+\frac{1}{k-1}\right)$ ,από όπου έπεται το ζητούμενο.

β. Αν ο αριθμός

γράφεται ως γινόμενο f(x)

στοιχείων και ο αριθμός

ως γινόμενο f(y)

στοιχείων,τότε είναι προφανές ότι ο

γράφεται ως γινόμενο f(x)+f(y)

στοιχείων.Άρα $f(xy)\leq f(x)+f(y)$ για όλα τα $x,y\geq 2$ .Παρατηρούμε τώρα ότι f(2^n)=n

για κάθε $n\in \mathbb{N}$ .Πράγματι,ο μεγαλύτερος αριθμός του συνόλου

είναι το

οπότε χρειάζονται τουλάχιστον

αριθμοί.Αφού $2^n=2\cdot 2\cdots 2$ ,έπεται ο ισχυρισμός.Θα χρησιμοποιήσουμε αυτή την καλή ιδιότητα των δυνάμεων του

,να γράφονται δηλαδή ως γινόμενα "λίγων" στοιχείων,κοιτώντας στους αριθμούς της μορφής 2^n+1

και εξετάζοντας τους διαιρέτες τους.Οι αριθμοί 3,5,17

είναι πρώτοι οπότε δεν έχουν δύο διαιρέτες μεγαλύτερους ή ίσους του

ενώ ο αριθμός

γράφεται ως $3\cdot 3$ ,όμως είναι εύκολο να δούμε ότι f(9)=f(3)+f(3)=4

.Εξετάζουμε τώρα τον αριθμό

.Παρατηρούμε ότι $33=\left(1+\frac{1}{32}\right)\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2$ ,οπότε $f(33)\leq 6$ (στην πραγματικότητα f(33)=6

).Όμως,είναι προφανές ότι f(3)=2

,και εύκολο να δούμε ότι f(11)=5

άρα

.Ο αριθμός

θα αποτελέσει τη βάση για τη συνέχεια της απόδειξης.Θεωρούμε τα ζεύγη της μορφής $(x,y)=(11,3\cdot 2^n)$ τα οποία προφανώς είναι άπειρα σε πλήθος.Από τη σχέση $f(xy)\leq f(x)+f(y)$ που αποδείξαμε παραπάνω,έπεται ότι $f(33\cdot 2^n)\leq f(33)+f(2^n)=n+6$ .Από την άλλη, f(11)=5

και $f(3\cdot 2^n)=n+2$ (θα το εξηγήσουμε παρακάτω),οπότε $n+6=f(33\cdot 2^n)<f(11)+f(3\cdot 2^n)=n+7$ ,και το ζητούμενο έπεται.

$\rule{430pt}{1pt}$

Θα εξηγήσουμε λίγο περισσότερο τις σχέσεις f(11)=5

και $f(3\cdot 2^n)=n+2$ .Για την πρώτη,υποθέτουμε ότι το

είναι γινόμενο τεσσάρων στοιχείων του

(αποκλείεται να είναι γινόμενο τριών στοιχείων καθώς το μέγιστο από αυτά είναι το 2^3=8

).Κάποιο από αυτά τα στοιχεία θα πρέπει να έχει αριθμητη πολλαπλάσιο του

οπότε η μέγιστη τιμή που μπορεί να πάρει αυτό το στοιχείο είναι η $1+\frac{1}{10}=\frac{11}{10}$ .Τα υπόλοιπα στοιχεία έχουν γινόμενο το πολύ 2^3=8

,οπότε η μέγιστη τιμή του γινομένου είναι $2^3\cdot \frac{11}{10}<11$ ,άτοπο.Από την άλλη το

γράφεται ως $\left(1+\frac{1}{10}\right)\cdot \left(1+\frac{1}{4}\right)\cdot 2\cdot 2\cdot 2$ ,οπότε το ζητούμενο έπεται.Για τη δεύτερη σχέση,παρατηρούμε ότι πρέπει να χρησιμοποιήσουμε τουλάχιστον n+1

στοιχεία,αφού η μέγιστη τιμή του γινομένου

στοιχείων είναι $2^n<3\cdot 2^n$ .Από την άλλη,η μέγιστη τιμή του γινομένου n+1

στοιχείων είναι $2^{n+1}>3\cdot 2^n$ ,και η αμέσως επόμενη είναι η $2^n\cdot \frac{3}{2}=3\cdot 2^{n-1}<3\cdot 2^n$ ,οπότε είναι αδύνατον να εκφράσουμε το $3\cdot 2^n$ ως γινόμενο n+1

στοιχείων.Τέλος,παρατηρούμε ότι $3\cdot 2^n=\cfrac{3}{2}\cdot 2\cdot 2\cdots 2$ ( n+1

δυάρια),οπότε έπεται ότι $f(3\cdot 2^n)=n+2$ .

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

Demetres έγραψε: ↑
Τετ Απρ 11, 2018 4:13 pm
Θεωρήστε το σύνολο
$\displaystyle A = \{1 + \frac{1}{k}:k=1,2,3\ldots \}$

(α) Αποδείξτε ότι κάθε ακέραιος $x \geqslant 2$ μπορεί να γραφεί ως γινόμενο ενός ή περισσοτέρων στοιχείων του , τα
οποία δεν είναι κατ’ ανάγκη διαφορετικά.

(β) Για κάθε ακέραιο $x \geqslant 2$ , συμβολίζουμε με τον ελάχιστο ακέραιο έτσι ώστε το να μπορεί να γράφεται ως γινόμενο σε πλήθος στοιχείων του , τα οποία δεν είναι κατ’ ανάγκη διαφορετικά.

Αποδείξτε ότι υπάρχουν άπειρα ζεύγη ακεραίων με $x \geqslant 2, y \geqslant 2$ και

$\displaystyle f(xy) < f(x) + f(y).$

(Τα ζεύγη και είναι διαφορετικά όταν $x_1 \neq x_2$ ή $y_1 \neq y_2$ .)

Μία λύση.

(α) Προφανώς, $\displaystyle x=\sum_{i=1}^{x-1} \displaystyle (1+\dfrac{1}{x})$

(β) Επιλέγουμε $x=13 \cdot 2^n, y=5$ .

Αποδεικνύουμε πρώτα τo εξής Λήμμα.

Λήμμα

Για κάθε ακέραιο $x \geqslant 2$ , είναι $\displaystyle 2^{f(x)} \geqslant x$ .
Απόδειξη

Προφανώς, ο κάθε όρος του γινομένου είναι $\leqslant 2$ , οπότε $x \leqslant 2^{f(x)}$ .

Θέλουμε να δείξουμε $f(13 \cdot 2^n)+f(5)>f(65 \cdot 2^n)$ .

Όμως, παρατηρούμε ότι $65 \cdot 2^n=(1+\dfrac{1}{1})^{n+6} \cdot (1+\dfrac{1}{64})$ , οπότε $f(65 \cdot 2^n) \leqslant n+7$ (1).

Επίσης, από το λήμμα $\displaystyle 2^{f(13 \cdot 2^n)}>13 \cdot 2^n>2^{n+3} \Rightarrow f(13 \cdot 2^n) \geqslant n+4$ (2).

Επίσης, παρατηρούμε ότι, πάλι από το Λήμμα, $2^{f(5)} >5 >4 \Rightarrow f(5) \geqslant 3$ (3).

Άρα, από (1), (2), (3) $f(13 \cdot 2^n)+f(5) \geqslant n+4+f(5) \geqslant n+7 \geqslant f(65 \cdot 2^n)$ .

Άρα, υπάρχουν άπειρα ζεύγη $(x,y)= (13 \cdot 2^n,5)$ , με $n \in \mathbb{N}$ ,ώστε να ισχύει το ζητούμενο.

Με πρόλαβε ο Γιώργος (gavrilos).

#4

Το α) είναι προφανές αφού:
$\displaystyle{x = \prod_{i=1}^{x-1}\left(1+\frac{1}{i}\right)}$

Για το β) αρκεί να βρούμε ένα ζεύγος (x,y)

αφού τότε το $(2^n\cdot x,y)$ δουλεύει επίσης.
Μία κατάλληλη επιλογή είναι να πάρουμε xy=2^s+1

, και με δοκιμές βρίσκουμε (x,y)=(3,11)

αφού $f(33)\leq 6$ και f(3)=2

και

.

**Δεν είχα κάνει ανενέωση και βλέπω τώρα ότι ταυτίζομαι με το Γιώργο παραπάνω.

#5

Ορέστης Λιγνός έγραψε: ↑
Τετ Απρ 11, 2018 7:05 pm
Άρα, από (1), (2), (3) $f(13 \cdot 2^n)+f(5) \geqslant n+4+f(5) \geqslant n+7 \geqslant f(65 \cdot 2^n)$ .

Ορέστη, εδώ πρέπει να δείξεις ότι μία από τις ανισότητες είναι αυστηρή. Στην πραγματικότητα πρέπει να δείξεις δηλαδή ότι
$f(13\cdot 2^n)\geq n+5.$

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

silouan έγραψε: ↑
Τετ Απρ 11, 2018 7:21 pm

Ορέστης Λιγνός έγραψε: ↑
Τετ Απρ 11, 2018 7:05 pm
Άρα, από (1), (2), (3) $f(13 \cdot 2^n)+f(5) \geqslant n+4+f(5) \geqslant n+7 \geqslant f(65 \cdot 2^n)$ .

Ορέστη, εδώ πρέπει να δείξεις ότι μία από τις ανισότητες είναι αυστηρή. Στην πραγματικότητα πρέπει να δείξεις δηλαδή ότι
$f(13\cdot 2^n)\geq n+5.$

Σε ευχαριστώ Σιλουανέ για την διόρθωση.

Αρκεί να δείξουμε ότι $f(13 \cdot 2^n) \neq n+4$ .

Έστω $f(13 \cdot 2^n)=n+4$ .

Τότε, έστω n+k

, με $k \in \mathbb{Z}$ το πλήθος των παραγόντων $(1+\dfrac{1}{1})$ που υπάρχουν στο γινόμενο.

Προφανώς, $n+k \leqslant n+4 \Rightarrow k \leqslant 4$ (*).

Τότε, $13 \cdot 2^n=2^{n+k} \cdot (1+\dfrac{1}{s_1})(1+\dfrac{1}{s_2}) \cdots (1+\dfrac{1}{s_{4-k}})$ , με $s_1,s_2, \ldots, s_{4-k} \geqslant 2$ , άρα $13 \cdot 2^n \leqslant 2^{n+k} \cdot (\dfrac{3}{2})^{4-k}$ , που γράφεται ισοδύναμα $2^{2k-4}>13 \cdot 3^{k-4}$ .

Αν $k \geqslant 0$ , με απευθείας έλεγχο, k=4

, άρα $13 \cdot 2^n=2^{n+4} \Rightarrow 13=16$ , άτοπο.
Αν τώρα k<0

, έστω

με

, οπότε η ανισότητα γίνεται $\dfrac{81}{208} >\dfrac{4^x}{3^x}>1$ , άτοπο.

Άρα, $f(13 \cdot 2^n) \neq n+4$ , οπότε $f(13 \cdot 2^n) \geqslant n+5$ .

#7

Ίδιες σκέψεις αλλά το βάζω για να τονίσω ότι δεν χρειάζεται να υπολογίσουμε σχεδόν κανένα f(n)

πέρα από τα προφανή f(2)

και

.

Είναι απλό ότι f(2) = 1

και

. Άρα $f(48) = f(2^4 \cdot 3)\leqslant 4+2=6$ και άρα $f(49) = f(\frac{49}{48} \cdot 48) \leqslant 1+6=7$ . Ισχυρίζομαι ότι f(49) < 2f(7)

. Σε αντίθετη περίπτωση, πρέπει $f(7) \leqslant 3$ . Αυτό όμως δεν μπορεί να ισχύει αφού το μεγαλύτερο γινόμενο τριών στοιχείων του

ισούται με

ενώ το δεύτερο μεγαλύτερο ισούται με $2^2 \cdot (3/2) = 6$ .

Άρα έχουμε ένα ζεύγος (x,y)

όπου δεν επιτυγχάνεται η ισότητα. Τα υπόλοιπα όπως του Σιλουανού.

#8

Δημήτρη, ωραία λύση! Δεν την είχα δει και στο artofproblemsolving, μέχρι που έβαλα κάτι παρόμοιο κάποιος σήμερα το πρωί. Το ενδιαφέρον είναι όντως ότι σου χρειάζεται μόνο το f(2)

και το

.

Ένα ερώτημα στο οποίο δεν έχω απάντηση. Είναι η f(x)+f(y)-f(xy)

φραγμένη;

EGMO 2018/2

EGMO 2018/2

Re: EGMO 2018/1/2

Re: EGMO 2018/1/2

Re: EGMO 2018/1/2

Re: EGMO 2018/1/2

Re: EGMO 2018/1/2

Re: EGMO 2018/1/2

Re: EGMO 2018/1/2

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