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