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