A B. 5388. feladat (2024. április)

B. 5388. Mutassuk meg, hogy bármely \(\displaystyle 2n\) egymást követő pozitív egész számot legalább \(\displaystyle n!\)-féleképpen lehet \(\displaystyle n\) párba állítani úgy, hogy semelyik párban ne legyen a számok szorzata négyzetszám.

Javasolta: Róka Sándor (Nyíregyháza)

(6 pont)

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

Megoldás. Az állítást \(\displaystyle n\)-re vonatkozó teljes indukcióval bizonyítjuk. Ha \(\displaystyle n=1\), akkor azt kell igazolnunk, hogy az egyetlen lehetséges párba állításnál a létrejövő szorzat nem négyzetszám. Ez valóban teljesül, ugyanis két szomszédos pozitív egész szám szorzata nem lehet négyzetszám: ha \(\displaystyle a\) és \(\displaystyle a+1\) pozitív egész számok, akkor \(\displaystyle a^2<a(a+1)<(a+1)^2\), és így \(\displaystyle a(a+1)\) nem négyzetszám.

Az indukciós lépés igazolásához tegyük fel, hogy valamely \(\displaystyle 1\leq n\)-re már igazoltuk az állítást. Tekintsünk most \(\displaystyle 2n+2\) egymást követő pozitív egész számot. Az első kettő legyen \(\displaystyle a\) és \(\displaystyle a+1\). Az indukciós feltevésünk alapján a maradék \(\displaystyle 2n\) (szintén egymást követő) pozitív egész számnak legalább \(\displaystyle n!\)-féle olyan párba állítása van, ahol egyik szorzat sem négyzetszám. Legyen egy tetszőleges megfelelő párba állításuk \(\displaystyle \{b_1,c_1\},\dots,\{b_n,c_n\}\), ekkor tehát a \(\displaystyle b_1c_1,b_2c_2,\dots,b_nc_n\) szorzatok egyike sem négyzetszám. Világos, hogy ha ezt kiegészítjük az \(\displaystyle \{a,a+1\}\) párral, az megfelelő. Mutatunk egy módszert, amivel legalább \(\displaystyle n\) másik jó párba állítás kapható. Legyen \(\displaystyle 1\leq i\leq n\) tetszőleges, és tekintsük a \(\displaystyle \{b_i,c_{i}\}=:\{p,q\}\), \(\displaystyle \{a,a+1\}=:\{r,s\}\) párokat. Csak annyit fogunk használni, hogy \(\displaystyle pq\) és \(\displaystyle rs\) nem négyzetszámok (a gondolatmenet további részében az, hogy \(\displaystyle r\) és \(\displaystyle s\) valójában szomszédosak, nem játszik szerepet). Ezekből kétféleképpen alakítható ki két új pár: \(\displaystyle \{p,r\},~\{q,s\}\), illetve \(\displaystyle \{p,s\},~\{q,r\}\). Ha ezek egyike sem lenne megfelelő, akkor mindkét esetben legalább az egyik szorzat négyzetszám lenne. Feltehető, hogy ezek a \(\displaystyle pr\) és \(\displaystyle ps\) szorzatok. (Ha a \(\displaystyle p,~r,~q,~s\) számokat – ebben a sorrendben – egy négyzet csúcsaiba írjuk, akkor a négy szorzat a négy oldalnak felel meg, és ha két párból választunk egyet-egyet, az mindenképpen két szomszédos él lesz.) Ha viszont \(\displaystyle pr\) és \(\displaystyle ps\) négyzetszámok, akkor szorzatuk, \(\displaystyle (pr)(ps)=p^2(rs)\) is az, és így azt kapnánk, hogy \(\displaystyle rs\) szintén négyzetszám, de \(\displaystyle rs\)-ről tudjuk, hogy nem az.

Tehát vagy a \(\displaystyle \{b_i,a\},~\{c_i,a+1\}\), vagy a \(\displaystyle \{b_i,a+1\},~\{c_i,a\}\) párok egyike esetén biztosan egyik szorzat sem négyzetszám. Ezt a két párt kiegészítve a másik \(\displaystyle n-1\) darab \(\displaystyle \{b_j,c_j\}\) párral megfelelő párba állítást kapunk. Ezzel a módszerrel tehát mutattunk legalább \(\displaystyle n+1\) megfelelő párba állítást a nagyobb \(\displaystyle 2n\) szám \(\displaystyle \{b_1,c_1\},\dots,\{b_n,c_n\}\) párba állítása segítségével. Végül belátjuk, hogy ezekből \(\displaystyle \{b_1,c_1\},\dots,\{b_n,c_n\}\) rekonstruálható. Ha ugyanis \(\displaystyle a\) és \(\displaystyle a+1\) egymás párja, akkor a másik \(\displaystyle n\) párt kell venni, ha pedig \(\displaystyle a\) és \(\displaystyle a+1\) két különböző párban vannak, akkor a párjaikból kialakítunk egy új párt, a maradék \(\displaystyle n-1\) párt pedig megtartjuk. Tehát különböző párba állításokból kiindulva módszerünkkel különböző párba állításokat kapunk. Így az indukciós feltevés alapján legalább \(\displaystyle (n+1)\cdot n!=(n+1)!\) megfelelő párba állítása van a \(\displaystyle 2n+2\) egymást követő számnak, ezzel az indukciós lépést igazoltuk.

Ezzel befejeztük a feladat állításának bizonyítását.

Megjegyzés. Valójában csak annyit használtunk, hogy a \(\displaystyle 2n\) pozitív egész számnak van legalább egy megfelelő párba állítása, a feladat állítása ezen gyengébb feltétel mellett is teljesül.

Statisztika:

22 dolgozat érkezett.
6 pontot kapott:	Ali Richárd, Bodor Mátyás, Csató Hanna Zita , Hodossy Réka, Holló Martin, Kovács Benedek Noel, Prohászka Bulcsú, Sági Mihály, Sárdinecz Dóra, Virág Tóbiás, Wágner Márton.
5 pontot kapott:	Aravin Peter, Gyenes Károly, Horák Zsófia.
4 pontot kapott:	3 versenyző.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2024. áprilisi matematika feladatai