Euler 2013/4

Συντονιστές: Demetres, silouan

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

Euler 2013/4

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Τρί Οκτ 25, 2016 11:14 pm

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

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



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

Re: Euler 2013/4

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Ιούλ 24, 2017 12:33 pm

Ας γράψουμε 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}


Απάντηση

Επιστροφή σε “Συνδυαστική - Επίπεδο Αρχιμήδη (Seniors)”

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

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