Problem B. 5498. (December 2025)

B. 5498. Let \(\displaystyle n\geq 2\) be a given positive integer. For which permutation \(\displaystyle a_1,a_2,\dots,a_n\) of numbers \(\displaystyle 1,2,\dots,n\) will the value of

\(\displaystyle a_1a_2+a_2a_3+\dots+a_{n-1}a_n\)

be maximal?

Proposed by Márton Lovas, Budakalász

(5 pont)

Deadline expired on January 12, 2026.

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

Megoldás. Jelölje \(\displaystyle f(n)\) a vizsgált szorzatösszeg maximális értékét \(\displaystyle 1,2,\ldots,n\) összes permutációját tekintve.

Nyilván \(\displaystyle f(2) = 2\), és egyszerű esetvizsgálattal látható, hogy \(\displaystyle f(3) = 9\), amely az \(\displaystyle 1,3,2\) és \(\displaystyle 2,3,1\) sorrendek esetén valósul meg.

Lemma: \(\displaystyle f(k) - f(k-1) \leq (2k-3)k - (k-1)(k-2) = k^2 - 2\) minden \(\displaystyle k \geq 3\) esetén. Egyenlőség csak akkor teljesülhet, ha az \(\displaystyle f(k)\)-t realizáló permutációban \(\displaystyle k\) a \(\displaystyle k-1\) és \(\displaystyle k-2\) között van.

Lemma bizonyítása: Tekintsük az \(\displaystyle f(k)\)-t megvalósító permutációt, ebben \(\displaystyle k\) szomszédai \(\displaystyle 1 \leq a < b \leq k-1\). Ha \(\displaystyle k\)-t kivennénk a sorozatból, maradna az \(\displaystyle \{ 1,2,\ldots,k-1 \}\) halmaz egy érvényes permutációja, melyhez tartozó összeg legfeljebb \(\displaystyle f(k-1)\). Ehhez képest a vizsgált, \(\displaystyle f(k)\)-t megvalósító \(\displaystyle k\)-elemű permutációnk összege ennyivel több:

\(\displaystyle (a+b) k - ab = a(k-b) + bk = b(k-a) + bk. \)

Az átalakítások mutatják, hogy \(\displaystyle a\) és \(\displaystyle b\) függvényeként tekintve is monoton nő ez a különbözet, tehát akkor a legnagyobb az értéke, ha \(\displaystyle \{a,b \} = \{k-2,k-1\}\). Így éppen a lemma állításában kiszámított maximális különbözetet kapjuk. \(\displaystyle \square\)

Legyen \(\displaystyle f^*(n) = 2 + \sum_{k=3}^n (k^2-2)\) minden \(\displaystyle n \geq 3\) egészre.

A lemmából rögtön következik, hogy \(\displaystyle f(n) \leq f^*(n)\), és az is, hogy az egyenlőség elérésére csak olyan permutációval lehet esély, ahol az \(\displaystyle n\) két szomszédja az \(\displaystyle n-1\) és az \(\displaystyle n-2\). Feltehetjük, hogy ebben a sorrendben következnek:

\(\displaystyle \ldots, n-1, n, n-2, \ldots \)

hiszen különben ,,tükrözhetjük'' az egész permutációt, azaz fordított sorrendben írjuk fel az elemeket.

Az \(\displaystyle n\) törlése után egy \(\displaystyle f^*(n-1)\)-et megvalósító permutációt kellene kapnunk, ehhez a lemma szerint \(\displaystyle n-1\) másik szomszédjának \(\displaystyle (n-3)\)-nak kell lennie:

\(\displaystyle \ldots, n-3, n-1, n, n-2, \ldots \)

Hasonlóképpen, ha \(\displaystyle n\) után az \(\displaystyle (n-1)\)-et is töröljük, akkor egy \(\displaystyle f(n-2)\)-et megvalósító permutációnak kell maradnia, és így a lemma szerint \(\displaystyle n-2\) másik szomszédjának \(\displaystyle (n-4)\)-nek kell lennie:

\(\displaystyle \ldots, n-3, n-1, n, n-2, n-4 \ldots \)

Ezt a gondolatmenetet folytatva láthatjuk, hogy egy \(\displaystyle f^*(n)\)-t megvalósító permutációnak úgy kell kinéznie, hogy középen egymás mellett áll \(\displaystyle n\) és \(\displaystyle n-1\), és ezektől a szélek felé haladva 2-esével csökkenek a számok. Másképpen fogalmazva: a permutáció egyik végétől kezdve a páros, másik végétől kezdve a páratlan számok következnek befele haladva növekvő sorrendben, középen a két legnagyobb számnál összeérve. Két ilyen permutáció van (egymás tükörképei), ezek pedig tényleg meg is valósítják az \(\displaystyle f^*(n)\) értékét – ez is rögtön következik a lemmából.

Megjegyzés. A feladat nem kérdezte, de érdekességképp megadjuk \(\displaystyle f(n)\) értékét explicit alakban is:

\(\displaystyle f(n) = 2 + \sum_{k=3}^n (k^2-2) = \sum_{k=1}^n k^2 - 2n + 1 = \frac{n(n+1)(2n+1)}6 - 2n + 1 = \frac13 n^3 + \frac12 n^2 - \frac{11}6 n + 1. \)

Statistics:

65 students sent a solution.
5 points:	Ali Richárd, Balla Ignác , Baran Júlia, Bodor Ádám, Bodor Noémi, Ercse Ferenc, Ethan Y.Wang, Görömbey Tamás, Hideg János, Holló Martin, Li Mingdao, Lovas Márk, Molnár Lili, Molnár-Sáska Tamás, Péter Hanna, Rajtik Sándor Barnabás, Sánta Gergely Péter, Tóth László Pál, Tóth Luca, Varga 511 Vivien, Wiener Marcell, Zhu Yi.
4 points:	Gál Mózes, Máté Marcell, Miszori Márton, Takács András.
3 points:	5 students.
2 points:	6 students.
1 point:	11 students.
0 point:	14 students.
Unfair, not evaluated:	1 solutions.
Not shown because of missing birth date or parental permission:	1 solutions.

Problems in Mathematics of KöMaL, December 2025