Euler 2013/4

#1

Να βρεθεί το πλήθος των μεταθέσεων $(x_1,\ldots,x_{20})$ των ακεραίων $1,2,\ldots,20$ οι οποίες ικανοποιούν

$x_1 \leqslant 2x_2 \leqslant \cdots \leqslant 20x_{20}$

#2

Ας γράψουμε A_n

για το πλήθος των μεταθέσεων $(x_1,\ldots,x_n)$ των ακεραίων $x_1,\ldots,x_n$ οι οποίες ικανοποιούν

$\displaystyle{ x_1 \leqslant 2x_2 \leqslant \cdots \leqslant nx_n.}$

Θα δείξουμε αρχικά ότι για κάθε $1 \leqslant k \leqslant n$ πρέπει $x_k \geqslant k-1$ .

Ας υποθέσουμε προς άτοπο το αντίθετο. Παίρνω

ελάχιστο ώστε x_k < k-1

. Έστω

. Τότε

$\displaystyle{ (k-1)x_{k-1} \leqslant kx_k = rk = r(k-1)+r}$

Άρα $\displaystyle{ x_{k-1} \leqslant r + \frac{r}{k-1} < r + 1.}$ Επειδή όμως $x_{k-1} \neq x_k = r$ , πρέπει $x_{k-1} \leqslant r-1 < (k-1)-1$ , άτοπο.

Πρέπει λοιπόν x_n = n

ή

.

Αν

, τότε ισχυρίζομαι ότι $x_{n-1}=n$ . Έστω ότι αυτό δεν ισχύει. Από τα πιο πάνω, πρέπει x_n-1} = n-2

. Δεν μπορούμε να έχουμε $x_{n-2} = n$ αφού τότε $(n-2)x_{n-2} = n(n-2) > (n-1)(n-2) = (n-1)x_{n-1}$ . Πρέπει λοιπόν $x_{n-2} = n-3$ . Έστω επαγωγικά ότι x_i = i-1

για κάθε $k \leqslant i \leqslant n$ . Δεν μπορούμε να έχουμε $x_{k-1} = n$ αφού τότε $(k-1)x_{k-1} = n(k-1) > k(k-1) = kx_{k}$ . Με επαγωγή καταλήγουμε σε άτοπο.

Αν x_n = n

, έχουμε $A_{n-1}$ μεταθέσεις που ικανοποιούν την συνθήκη. Αν x_n = n-1

, αφού επίσης $x_{n-1} = n$ , έχουμε $A_{n-2}$ μεταθέσεις που ικανοποιούν την συνθήκη. Δηλαδή, $A_n = A_{n-1} + A_{n-2}$ .

Αφού, A_1=1

και

, τότε $A_n = F_{n+1}$ , όπου F_n

η ακολουθία Fibonacci. Άρα $A_{20}=F_{21}$

Euler 2013/4

Euler 2013/4

Re: Euler 2013/4

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