Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 4172. (April 2009)

B. 4172. Let n be a positive integer and let k_1, k_2, k_3,\ldots,k_n denote an arbitrary order of the integers 1 to n. What is the largest possible value of the expression

(1-k1)2+(2-k2)2+(3-k3)2+...+(n-kn)2

of n terms?

(4 pont)

Deadline expired on May 15, 2009.


Sorry, the solution is available only in Hungarian. Google translation

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}.


Statistics:

95 students sent a solution.
4 points: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 points:16 students.
2 points:16 students.
1 point:10 students.
0 point:2 students.
Unfair, not evaluated:5 solutionss.

Problems in Mathematics of KöMaL, April 2009