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