Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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

B. 4172. Legyen n pozitív egész és jelölje a k1,k2,k3,...,kn 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\ge2. Először megmutatjuk, hogy ha a kifejezés a legnagyobb lehetséges értékét veszi fel, akkor k1=n és kn=1. Valóban, tegyük fel először, hogy k1=x<n, és legyen y>1 az az index, amelyre ky=n. Ha k1-et n-re, ky értékét pedig x-re cseréljük, akkor a kifejezés értéke a pozitív

((1-n)2+(y-x)2)-((1-x)2+(y-n)2)=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 kn-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\lei\len esetén ki=n+1-i, és ezt az értéket M(n)-nel jelölve, n\ge2 esetén M(n)=M(n-2)+2(n-1)2 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:

96 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, Matyuska Péter, 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