 |
A B. 5498. feladat (2025. december) |
B. 5498. Legyen \(\displaystyle n\geq 2\) egy adott pozitív egész. Az \(\displaystyle 1,2,\dots,n\) számok mely \(\displaystyle a_1,a_2,\dots,a_n\) permutációjára lesz
\(\displaystyle a_1a_2+a_2a_3+\dots+a_{n-1}a_n \)
maximális?
Javasolta: Lovas Márton (Budakalász)
(5 pont)
A beküldési határidő 2026. január 12-én LEJÁRT.
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. \)
Statisztika:
A B. 5498. feladat értékelése még nem fejeződött be.
A KöMaL 2025. decemberi matematika feladatai