Rješenja zadatka "Mala olimpijada 1998 zadatak 3" korisnika "ivl"

Točno

11. travnja 2015. 21:10 (9 godine)

Korisnik: ivl
Zadatak: Mala olimpijada 1998 zadatak 3 (Sakrij tekst zadatka)

Neka je $\{ F_i \}$ , $i=0,1, \ldots$ niz brojeva definiran na sljedeći način:
$F_0=0, \ F_1=1,\ F_{i+2}=F_{i+1}+F_{i}, \ i=0,1, \ldots$
Za prirodan broj $n \geq 2$ neka su $a_0, a_1, \ldots a_n$ nenegativni brojevi koji zadovoljavaju uvjet
$a_0=1, \ a_i \leq a_{i+1} + a_{i+2}, \ i=0,1, \ldots, n-2.$
Dokažite da je $a_0+a_1+\ldots+a_n \geq \frac{F_{n+2}-1}{F_{n}}$ . Da li se postiže jednakost?

Upozorenje: Ovaj zadatak još niste riješili!
Kliknite ovdje kako biste prikazali rješenje.

Primjetimo da ne postoji $i$ takav da $a_i = a_{i+1} = 0$ (jer to implicira $a_{i-1} = 0$ , dakle $a_0 = 0$ ).
Ako uparimo svaku nulu sa nenula brojem na lijevo, primjetimo da svaki broj se nalazi u najvise jednom paru, te broj parova je jednak broju nuli, dakle broj nula je najvise $\left \lfloor \dfrac{n+1}{2}\right\rfloor$ .
Dakle $\sum{a_i} \geqslant n+1 - \left \lfloor \dfrac{n+1}{2}\right\rfloor = \left\lfloor\dfrac{n}{2}\right\rfloor + 1$
Nadalje $a_{2k}=1, \ a_{2k+1}=0$ je valjana konstrukcija za koju postizemo sumu $\left\lfloor\dfrac{n}{2}\right\rfloor + 1$ , pa je ekvivalentno dokazati (i evaluirati jednakost za):
$\left\lfloor\dfrac{n}{2}\right\rfloor + 1 \geqslant \dfrac{F_{n+2} - 1}{F_n}$

$\dfrac{F_{n+2} - 1}{F_n} = 2 + \dfrac{F_{n-1}-1}{F_n} < 3$ dakle vrijedi stroga nejednakost za $n \geqslant 4$
Jednakost vrijedi samo za $n = 2, 3$

Ocjene: (1)

Komentari:

ivl, 13. lipnja 2015. 21:04

Slazem se da nije potrebno, konstrukcija je vise za proces trazenja rjesenja bitna. To jest, ako napravim neku transformaciju na zadatku, te dokazem da je to zapravo ekvivalencija zadatka, onda znam da nisam nista gadno zeznuo/izgubio vitalne informacije te mogu komotno nastaviti derati.

ikicic, 29. svibnja 2015. 22:40

Mislim da nije potrebno navoditi konstrukciju slučaja $\sum a_i \geq \left \lfloor \dfrac{n}{2} \right \rfloor + 1$ , dovoljno je pokazati da je $\left \lfloor \dfrac{n}{2} \right \rfloor + 1 \geq \dfrac{F_{n+2} - 1}{F_n}$ , pa će automatski biti zadovoljena tvrdnja zadatka.
Primijeti da nigdje ne koristiš u dokazu tu svoju konstrukciju, tj. dokaz ti vrijedi i bez nje.

Školjka

Ocjene: (1)

Komentari: