A B. 4172. feladat (2009. április)

B. 4172. Legyen n pozitív egész és jelölje a k₁,k₂,k₃,...,k_n az 1-től n-ig terjedő egész számok egy tetszőleges sorrendjét. Mekkora az

${(1-k_1)}^2+{(2-k_2)}^2+{(3-k_3)}^2+\ldots+{(n-k_n)}^2$

n-tagú kifejezés legnagyobb értéke?

(4 pont)

A beküldési határidő 2009. május 15-én LEJÁRT.

Megoldás: Tegyük fel, hogy n $\ge$ 2. Először megmutatjuk, hogy ha a kifejezés a legnagyobb lehetséges értékét veszi fel, akkor k₁=n és k_n=1. Valóban, tegyük fel először, hogy k₁=x<n, és legyen y>1 az az index, amelyre k_y=n. Ha k₁-et n-re, k_y értékét pedig x-re cseréljük, akkor a kifejezés értéke a pozitív

((1-n)²+(y-x)²)-((1-x)²+(y-n)²)=2(y-1)(n-x)

mennyiséggel nő. Mivel a kifejezés csak véges sok különböző értéket vehet fel, ezzel állításunk első felét igazoltuk, és a k_n-re vonatkozó rész is ugyanígy ellenőrizhető.

Ebben az esetben a $k_2,\ldots,k_{n-1}$ számok a $2,\ldots, n-1$ számok egy permutációját alkotják, és

$(2-k_2)^2+\ldots+(n-1-k_{n-1})^2=(1-\ell_1)^2+\ldots+(n-2-\ell_{n-2})^2,$

ahol az $\ell_1=k_2-1,\ldots,\ell_{n-2}=k_{n-1}-1$ számok az $1,\ldots,n-2$ számoknak alkotják egy permutációját. Innen már n szerinti teljes indukcióval könnyen belátható, hogy ha a kifejezés a legnagyobb lehetséges értékét veszi fel, akkor minden 1 $\le$ i $\le$ n esetén k_i=n+1-i, és ezt az értéket M(n)-nel jelölve, n $\ge$ 2 esetén M(n)=M(n-2)+2(n-1)² is fennáll.

M(n) pontos meghatározásához érdemes bevezetni az

$S_k=1^2+2^2+\ldots+k^2=\frac{k(k+1)(2k+1)}{6}$

jelölést. Mivel üres összegről lévén szó M(0)=0, és M(1)=0 is fennáll, a megállapított rekurzió alapján M(n) értékét a páratlan (n=2k+1) és páros (n=2k) esetekre lebontva így határozhatjuk meg:

$M(2k+1)=2(2k)^2+2(2k-2)^2+\ldots+2\cdot2^2=8S_k=\frac{4k(k+1)(2k+1)}{3},$

$M(2k)=2(2k-1)^2+2(2k-3)^2+\ldots+2\cdot1^2=2S_{2k}-8S_k= \frac{2k(2k-1)(2k+1)}{3}.$

Statisztika:

95 dolgozat érkezett.

4 pontot kapott: Bali Gábor, Balla Attila, Beke Lilla, Blázsik Zoltán, Bodor Bertalan, Cséke Balázs, Csere Kálmán, Dinh Hoangthanh Attila, Dorkó Barbara, Dudás 002 Zsolt, Egyed Zsombor, Éles András, Énekes Péter, Fonyó Dávid, Frankl Nóra, Huszár Kristóf, Janosov Milán, Janzer Olivér, Keresztfalvi Tibor, Lantos Tamás, Lenger Dániel, Lovas Lia Izabella, Márki Róbert, Márkus Bence, Mester Márton, Mészáros András, Mezei Márk, Muszka Balázs, Nagy 111 Miklós, Nagy 648 Donát, Németh Bence, Perjési Gábor, Réti Dávid, Somogyi Ákos, Strenner Péter, Szabó 928 Attila, Szenczi Zoltán, Tóth 222 Barnabás, Tuan Nhat Le, Varga 171 László, Varju 105 Tamás, Vuchetich Bálint, Weisz Ágoston, Weisz Gellért, Zelena Réka, Zsakó András.

3 pontot kapott: 16 versenyző.

2 pontot kapott: 16 versenyző.

1 pontot kapott: 10 versenyző.

0 pontot kapott: 2 versenyző.

Nem versenyszerű: 5 dolgozat.

A KöMaL 2009. áprilisi matematika feladatai

95 dolgozat érkezett.
4 pontot kapott:	Bali Gábor, Balla Attila, Beke Lilla, Blázsik Zoltán, Bodor Bertalan, Cséke Balázs, Csere Kálmán, Dinh Hoangthanh Attila, Dorkó Barbara, Dudás 002 Zsolt, Egyed Zsombor, Éles András, Énekes Péter, Fonyó Dávid, Frankl Nóra, Huszár Kristóf, Janosov Milán, Janzer Olivér, Keresztfalvi Tibor, Lantos Tamás, Lenger Dániel, Lovas Lia Izabella, Márki Róbert, Márkus Bence, Mester Márton, Mészáros András, Mezei Márk, Muszka Balázs, Nagy 111 Miklós, Nagy 648 Donát, Németh Bence, Perjési Gábor, Réti Dávid, Somogyi Ákos, Strenner Péter, Szabó 928 Attila, Szenczi Zoltán, Tóth 222 Barnabás, Tuan Nhat Le, Varga 171 László, Varju 105 Tamás, Vuchetich Bálint, Weisz Ágoston, Weisz Gellért, Zelena Réka, Zsakó András.
3 pontot kapott:	16 versenyző.
2 pontot kapott:	16 versenyző.
1 pontot kapott:	10 versenyző.
0 pontot kapott:	2 versenyző.
Nem versenyszerű:	5 dolgozat.

Már regisztráltál?
Új vendég vagy?