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