A B. 5353. feladat (2023. december)

B. 5353. Bizonyítsuk be, hogy tetszőleges 1-nél nagyobb pozitív egész $\displaystyle n$ esetén

$\displaystyle \sum_{i=1}^n\, \sum_{j=1}^n|i-j|=\frac{n(n^2-1)}{3}.$

Javasolta: Bencze Mihály (Brassó)

(4 pont)

A beküldési határidő 2024. január 10-én LEJÁRT.

1. megoldás. Az állítást $\displaystyle n$-re vonatkozó teljes indukcióval igazoljuk $\displaystyle n=1$-től kezdődően. Az indukció kezdő lépése világos: $\displaystyle n=1$ esetén mindkét oldalon 0 áll. Tegyük most fel, hogy valamely $\displaystyle n\geq 1$-re már igazoltuk az állítást, és lássuk be, hogy $\displaystyle (n+1)$-re is teljesül.

Tekintsük a bal oldalon az új tagokat: $\displaystyle i=j=n+1$-re 0-t kapunk, $\displaystyle i<j=n+1$ melletti új tagok összege $\displaystyle 1+2+\dots+n=\frac{n(n+1)}{2}$, a szimmetria miatt $\displaystyle j<i=n+1$-re szintén $\displaystyle \frac{n(n+1)}{2}$ az új tagok összege. Tehát az új tagok összege $\displaystyle n(n+1)$. Az indukciós feltevést használva tehát a bal oldalon az összes tag összege

$\displaystyle \frac{n(n^2-1)}{3}+n(n+1)=\frac{n(n+1)(n-1+3)}{3}=\frac{(n+1)((n+1)^2-1)}{3},$

így az indukciós lépést igazoltuk. Ezzel a feladat állítását bizonyítottuk.

2. megoldás. Számoljuk meg kétféleképpen, hány olyan $\displaystyle (i,k,j)$ egészekből álló számhármas van, melyre $\displaystyle 1\leq i\leq k<j\leq n$. Rögzített $\displaystyle 1\leq i<j\leq n$ esetén a megfelelő $\displaystyle k$ értékek száma $\displaystyle j-i=|i-j|$, így a válasz $\displaystyle \sum\limits_{1\leq i<j\leq n}|i-j|$.

Ez éppen a feladat állításában az egyenlőség bal oldalán szereplő kifejezés értékének a fele, az $\displaystyle i$ és $\displaystyle j$ közötti szimmetriát, valamint azt használva, hogy az $\displaystyle i=j$ esetén kapott tagok értéke 0.

Másrészről, pontosan akkor lesz $\displaystyle 1\leq i\leq k<j\leq n$, ha $\displaystyle 1\leq i<k+1<j+1\leq n+1$, vagyis, ha $\displaystyle i,k+1,j+1$ az 1 és $\displaystyle n+1$ közötti egész számok közül választott három hosszú szigorúan növő sorozat. Ezek száma $\displaystyle \binom{n+1}{3}=\frac{n(n^2-1)}{6}$, ami pedig a bizonyítandó állítás jobb oldalán álló kifejezés fele. Ezzel a feladat állítását igazoltuk.

Statisztika:

122 dolgozat érkezett.
4 pontot kapott:	106 versenyző.
3 pontot kapott:	4 versenyző.
2 pontot kapott:	3 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.
Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt:	4 dolgozat.

A KöMaL 2023. decemberi matematika feladatai