Az A. 879. feladat (2024. április)

A. 879. Adott egy \(\displaystyle k>2\) egész szám. Xavér és Yvett a következő játékot játssza. Eredetileg a táblán egy \(\displaystyle n>k\) egész szám szerepel. Ezt követően felváltva lépnek, Xavér kezd. Egy lépés abból áll, hogy a táblán szereplő \(\displaystyle m\) számot kicserélik egy olyan \(\displaystyle m'\) számra, amelyre \(\displaystyle k\le m'<m\) és \(\displaystyle (m',m)=1\). Aki először nem tud lépni, veszít.

Azt mondjuk, hogy egy \(\displaystyle n>k\) egész szám jó, ha Yvettnek van nyerő stratégiája. Mutassuk meg, hogy ha \(\displaystyle n\), \(\displaystyle n'>k\) olyanok, hogy minden \(\displaystyle p\le k\) prímre \(\displaystyle p\) akkor és csak akkor osztja \(\displaystyle n\)-et, ha \(\displaystyle n'\)-t, akkor \(\displaystyle n\) akkor és csak akkor jó, ha \(\displaystyle n'\) jó.

(7 pont)

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

Megoldás. \(\displaystyle k\) világosan jó, mert ha \(\displaystyle k\) a kezdőszám, akkor Xaver nem tud lépni, így egyből Yvett nyer.

Rekurzívan definiáljuk a helyes számokat: \(\displaystyle k\) helyes, és egy \(\displaystyle k<n\) szám pontosan akkor helyes, ha nem relatív prím egyetlen \(\displaystyle k\le m<n\) helyes \(\displaystyle m\) számmal sem.

\(\displaystyle n\) szerinti indukcióval könnyű belátni, hogy a helyes számok és jó számok megegyeznek: Ha \(\displaystyle n\) helyes szám, akkor ha azzal kezdünk, akkor Xaver nem léphet egyetlen helyes számra sem, és minden \(\displaystyle n\)-nél kisebb nem helyes szám egyben nem jó is, tehát Xaver egy nem jó számra lép, így onnan a kezdőnek, azaz Yvettnek van nyerő stratégiája. Tehát ekkor \(\displaystyle n\) jó. Ellenben ha \(\displaystyle n\) nem helyes, akkor létezik egy \(\displaystyle k\le m<n\) helyes és egyben jó szám, ami relatív prím \(\displaystyle n\)-nel, így Xaver léphet \(\displaystyle m\)-re, és onnan a második játékosnak, azaz Xavernak van nyerő stratégiája. Tehát ekkor \(\displaystyle n\) nem jó.

Mostantól újra jó és rossz-ként hivatkozunk a számokra, de a helyesség definícióját használjuk, mert az imént beláttuk, hogy ez ekvivalens.

Indukcióval belátjuk az alábbi állítást:

Bármely két jó számnak van \(\displaystyle k\)-nál kisebb-egyenlő közös prímosztója, továbbá igaz a feladat állítása: ha \(\displaystyle n, n' \ge k \) olyanok, hogy minden \(\displaystyle p \le k \) prímre \(\displaystyle p|n \iff p|n' \), akkor \(\displaystyle n\) jó \(\displaystyle \iff\) \(\displaystyle n'\) jó.

Indukciós feltesszük, hogy az \(\displaystyle n\)-nél kisebb számokra igaz ez az állítás.

(Az indukció alapesetére, \(\displaystyle n=k\)-ra igaz az állítás, mert üres halmazokra vonatkozik.)

Először belátjuk az indukciós lépést az állítás első felére: \(\displaystyle n\) pontosan akkor jó, ha van \(\displaystyle k\)-nál kisebb közös prímosztója minden korábbi jó számmal.

Az egyik irány könnyű: ha \(\displaystyle n\) nem jó, akkor van olyan korábbi jó szám, amivel egyáltalán nincs közös prímosztója.

A másik irányhoz tegyük fel, hogy \(\displaystyle n\) jó, de van egy korábbi \(\displaystyle k\le m<n\) jó szám, amivel nincs \(\displaystyle k\)-nál kisebb-egyenlő közös prímosztója. Mivel \(\displaystyle n\) és \(\displaystyle m\) is jó, léteznie kell közös osztójuknak. Legyen \(\displaystyle m\) prímfelbontásában az \(\displaystyle n\)-nel közös tényezők szorzata \(\displaystyle q\). Azaz felírhatjuk \(\displaystyle m\)-et \(\displaystyle m=qm_1\) alakban, ahol \(\displaystyle m_1\) relatíve prím \(\displaystyle n\)-nel. A feltételezés szerint \(\displaystyle q\) csak \(\displaystyle k\)-nál nagyobb prímeket tartalmaz, így \(\displaystyle q>k\).

Mivel \(\displaystyle k\) jó és \(\displaystyle m\) jó, ezért az indukciós feltétel alapján kell lennie \(\displaystyle k\)-nál kisebb-egyenlő közös prímosztójuknak, így \(\displaystyle m_1\)-nek biztosan van \(\displaystyle k\)-nál kisebb-egyenlő prímosztója, nevezzük ezt \(\displaystyle p\)-nek.

\(\displaystyle p\)-nek biztosan van olyan \(\displaystyle p^t\) hatványa, amire \(\displaystyle \frac{k}{p}\le p^t\le k\). Vegyük az \(\displaystyle m'=m_1p^t\) számot. Mivel \(\displaystyle \frac{k}{p}\le p^t\), és \(\displaystyle p|m_1\), ezért \(\displaystyle m'=m_1p^t\ge p^{t+1}\ge k\). Másrészt mivel \(\displaystyle p^t\le k<q\), ezért \(\displaystyle m'=m_1p^t< m_1q=m\).

Mivel \(\displaystyle p|m_1\), ezért \(\displaystyle m\) és \(\displaystyle m'\) ugyanazokkal a \(\displaystyle k\)-nál kisebb-egyenlő prímszámokkal oszthatók. Mivel mindketten kisebbek \(\displaystyle n\)-nél, az indukciós feltétel szerint pontosan akkor jó az egyik, ha a másik az. Mivel tudjuk, hogy \(\displaystyle m\) jó, ebből következik, hogy \(\displaystyle m'\) is jó. Másrészt tudjuk, hogy \(\displaystyle n\)-nek nincs közös prímosztója \(\displaystyle m_1\)-gyel, így \(\displaystyle m'=m_1p^t\)-nel sem lehet. Ekkor \(\displaystyle n\) relatív prím lenne a \(\displaystyle k\le m'<n\) jó számmal, ami ellentmond annak, hogy \(\displaystyle n\) jó.

Most lássuk be az indukciós lépés második felét: ha létezik \(\displaystyle k\le m<n\) szám, aminek pontosan azok a \(\displaystyle k\)-nál kisebb-egyenlő prímosztói, mint \(\displaystyle n\)-nek, akkor \(\displaystyle n\) pontosan akkor jó, ha \(\displaystyle m\) jó.

Ha \(\displaystyle m\) jó, akkor az indukciós állítás első fele szerint minden \(\displaystyle k\le r<n\) jó számra van \(\displaystyle m\)-nek és \(\displaystyle r\)-nek \(\displaystyle k\)-nál kisebb-egyenlő közös prímosztója, és az osztja \(\displaystyle n\)-t is, tehát \(\displaystyle n\)-nek minden jó \(\displaystyle r\)-rel van közös prímosztója, tehát \(\displaystyle n\) is jó. Ha viszont \(\displaystyle m\) nem jó, akkor létezik jó \(\displaystyle k\le r<m<n\), amivel \(\displaystyle m\)-nek nincs közös osztója, és \(\displaystyle m\)-nek és \(\displaystyle n\)-nek ugyanazok a \(\displaystyle k\)-nál kisebb-egyenlő prímosztói, tehát \(\displaystyle r\)-nek és \(\displaystyle n\)-nek nem lehet \(\displaystyle k\)-nál kisebb-egyenlő közös prímosztója, ezért mint korábban beláttuk, \(\displaystyle n\) nem lehet jó.

Ezzel az indukciós lépést beláttuk, így indukcióval bizonyítottunk egy állítást ami magában foglalja a feladat állítását.

Megjegyzés: Ez a feladat 2013-ban szerepelt az IMO shortlisten.

Statisztika:

8 dolgozat érkezett.
7 pontot kapott:	Bodor Mátyás, Philip Stefanov, Varga Boldizsár, Wiener Anna.
6 pontot kapott:	Szakács Ábel.
5 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2024. áprilisi matematika feladatai