Σελίδα 1 από 1

Euler 2013/4

Δημοσιεύτηκε: Τρί Οκτ 25, 2016 11:14 pm
από Demetres
Να βρεθεί το πλήθος των μεταθέσεων (x_1,\ldots,x_{20}) των ακεραίων 1,2,\ldots,20 οι οποίες ικανοποιούν

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

Re: Euler 2013/4

Δημοσιεύτηκε: Δευ Ιούλ 24, 2017 12:33 pm
από Demetres
Ας γράψουμε 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.

Ας υποθέσουμε προς άτοπο το αντίθετο. Παίρνω k ελάχιστο ώστε x_k < k-1. Έστω x_k = r. Τότε

\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 = n-1.

Αν x_n = n-1, τότε ισχυρίζομαι ότι 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_2=2, τότε A_n = F_{n+1}, όπου F_n η ακολουθία Fibonacci. Άρα A_{20}=F_{21}