Az A. 886. feladat (2024. szeptember)

A. 886. Adottak a \(\displaystyle k\) és \(\displaystyle n\) 1-nél nagyobb különbözô pozitív egész számok, továbbá véges sok (nem feltétlenül különböző) egész szám felírva a táblára. Kázmér egy lépésben letörölheti egy \(\displaystyle k\)-val nem osztható differenciájú számtani sorozat \(\displaystyle k\) egymást követő elemét, míg Nándor letörölheti egy \(\displaystyle n\)-nel nem osztható differenciájú számtani sorozat \(\displaystyle n\) egymást követő elemét. Tudjuk, hogy a kiindulási számok olyanok, hogy Kázmér és Nándor is le tudja törölni az összes számot véges sok lépésben (külön-külön). Bizonyítsuk be, hogy ekkor a táblán szereplő legnagyobb és legkisebb szám különbsége legalább \(\displaystyle \varphi(n)+\varphi(k)\), ahol \(\displaystyle \varphi\) az Euler-féle fí-függvényt jelöli, vagyis \(\displaystyle \varphi(n)\) az \(\displaystyle n\)-nél nem nagyobb, \(\displaystyle n\)-hez relatív prím pozitív egészek száma.

Javasolta: Varga Boldizsár, Budapest

(7 pont)

A beküldési határidő 2024. október 10-én LEJÁRT.

Ha minden számot ugyanannyival növelünk vagy csökkentünk, az nem változtat a letörölhetőségen, és a legnagyobb és legkisebb szám különbségén sem, így feltehető, hogy a legkisebb szám a 0. Ekkor azt kell bizonyítanunk, hogy a legnagyobb szám legalább \(\displaystyle \varphi(n)+\varphi(k)\).

Legyenek a felírt számok (multiplicitással) valamilyen sorrendben \(\displaystyle a_1, a_2, \ldots, a_m\). Tekintsük a \(\displaystyle \sum_{i=1}^m x^{a_i}\) polinomot. Vegyük észre, hogy ennek a polinomnak minden primitív \(\displaystyle k\)-adik komplex egységgyök gyöke, ugyanis ha a Kázmér által letörölt számtani sorozatokba particionáljuk a tagokat, akkor minden \(\displaystyle a_i, a_i+d, a_i+2 d, \ldots, a_i+(k-1) d\) számtani sorozathoz (ahol tudjuk, hogy \(\displaystyle k \nmid d\) ) az \(\displaystyle x^{a_i}+x^{a_i+d}+\cdots+x^{a_i+(k-1) d}\) polinom tartozik (ezek összege az eredeti polinom), ebbe pedig egy \(\displaystyle \varepsilon\) primitív \(\displaystyle k\)-adik egységgyököt behelyettesítve \(\displaystyle \varepsilon^{a_i} \cdot\left(1+\varepsilon^d+\varepsilon^{2 d}+\ldots+\varepsilon^{(k-1) d}\right)=\varepsilon^{a_i} \cdot \frac{\varepsilon^{k d}-1}{\varepsilon^d-1}=0\)-t kapunk. Mivel \(\displaystyle \varepsilon\) primitív egységgyök, ezért \(\displaystyle \varepsilon^d-1 \neq 0\). A fenti indoklás alapján a polinomnak mind a \(\displaystyle \varphi(k)\) darab primitív \(\displaystyle k\)-adik egységgyök gyöke és teljesen analóg módon mind a \(\displaystyle \varphi(n)\) darab primitív \(\displaystyle n\)-edik egységgyök is gyöke. Azonban ezen gyökök között a primitívség miatt semelyik kettő nem egyezik meg, így a poinomnak van legalább \(\displaystyle \varphi(k)+\varphi(n)\) különböző gyöke. A definíció alapján a polinom nem konstans 0, amiből következik, hogy a foka legalább \(\displaystyle \varphi(k)+\varphi(n)\), így a legnagyobb táblára írt számnak is legalább ennyinek kell lennie, és éppen ezt akartuk bizonyítani.

Statisztika:

9 dolgozat érkezett.
7 pontot kapott:	Bodor Mátyás, Forrai Boldizsár, Szakács Ábel, Tianyue DAI, Varga Boldizsár.
2 pontot kapott:	2 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2024. szeptemberi matematika feladatai