A 67. Nemzetközi Matematikai Diákolimpia feladatainak megoldása I.

Aravin Péter, Bodor MNátyás, Szakács Ábel

A hagyományoknak megfelelően közöljük a Nemzetközi Matematikai Diákolimpia feladatainak megoldásait. A megoldások leírására idén is a magyar csapat tagjait kértük meg. Közreműködésüket köszönjük, és ezúton is gratulálunk eredményeikhez.

A szerkesztőség

Első nap

1. feladat. Valaki felírt a táblára \(\displaystyle 2026\), nem feltétlenül különböző, \(\displaystyle 1\)-nél nagyobb egész számot. Konfuciusz minden lépésben kiválaszt két egész számot, \(\displaystyle m>1\)-et és \(\displaystyle n>1\)-et két különböző helyről a táblán, és ezt a két számot kicseréli a

\(\displaystyle \mathrm{gcd}(m,n) \qquad \text{és} \qquad \frac{\mathrm{lcm}(m,n)}{\mathrm{gcd}(m,n)} \)

számokra. Ezt a lépést addig ismétli, amíg csak lehetséges.

(a) Bizonyítsuk be, hogy – függetlenül Konfuciusz választásaitól – véges sok lépés után pontosan egy olyan \(\displaystyle M\) egész szám marad a táblán, amely nagyobb \(\displaystyle 1\)-nél.

(b) Bizonyítsuk be, hogy az \(\displaystyle M\) értéke nem függ Konfuciusz választásaitól.

Megjegyzés: \(\displaystyle \mathrm{gcd}(x,y)\) az \(\displaystyle x\) és \(\displaystyle y\) pozitív egész számok legnagyobb közös osztóját, \(\displaystyle \mathrm{lcm}(x,y)\) pedig az \(\displaystyle x\) és \(\displaystyle y\) legkisebb közös többszörösét jelöli.

  Javasolta: Luxemburg

Megoldás (Aravin Péter). A megoldás során tetszőleges pozitív egész \(\displaystyle n\) esetén \(\displaystyle v_p(n)\) fogja jelölni a \(\displaystyle p\) kitevőjét a \(\displaystyle n\) prímtényezős felbontásában. Felhasználjuk azt a jól ismert tényt, hogy bármely \(\displaystyle m\), \(\displaystyle n\) pozitív egészekre \(\displaystyle \mathrm{gcd}(m,n)\!\cdot\!\mathrm{lcm}(m,n)\!=\!mn\).

(a) Vizsgáljuk meg, hogyan változik a játék lépései közben a táblára írt számok szorzata és az \(\displaystyle 1\)-nél nagyobb számok száma.

Amikor Konfuciusz letöröl valamilyen \(\displaystyle n\), \(\displaystyle m\) számokat, és felírja helyettük \(\displaystyle \mathrm{gcd}(m,n)\)-et és \(\displaystyle \frac{\mathrm{lcm}(m,n)}{\mathrm{gcd}(m,n)}\)-et, akkor ennek a két számnak a szorzata \(\displaystyle mn\)-ről \(\displaystyle \mathrm{lcm}(m,n)=\frac{mn}{\mathrm{gcd}(m,n)}\)-re változik; ha a lépés előtt az összes szám szorzata \(\displaystyle P\) volt, akkor a lépés után az új szorzat \(\displaystyle \frac{P}{\mathrm{gcd}(m,n)}\leq P\) lesz. Így az összes szám szorzata soha nem növekszik, és csak akkor nem csökken, ha \(\displaystyle \mathrm{gcd}(m,n)=1\), vagyis \(\displaystyle m\) és \(\displaystyle n\) relatív prímek.

2. feladat. Legyen \(\displaystyle ABC\) egy háromszög, és legyen \(\displaystyle M\) és \(\displaystyle N\) az \(\displaystyle AB\), illetve az \(\displaystyle AC\) oldal felezőpontja. Válasszuk meg a \(\displaystyle K\) és \(\displaystyle L\) pontokat a \(\displaystyle BMC\), illetve a \(\displaystyle BNC\) háromszög belsejében úgy, hogy a \(\displaystyle K\) az \(\displaystyle ABL\), az \(\displaystyle L\) pedig az \(\displaystyle AKC\) háromszög belsejébe essen. Tegyük fel, hogy

\(\displaystyle KBA\sphericalangle = ACL\sphericalangle, \qquad LBK\sphericalangle = LNC\sphericalangle \qquad \text{és} \qquad LCK\sphericalangle = BMK\sphericalangle. \)

Legyen \(\displaystyle O\) az \(\displaystyle AKL\) háromszög köré írt kör középpontja. Bizonyítsuk be, hogy \(\displaystyle {OM=ON}\).

  Javasolta: Ukrajna

Megoldás (Bodor Mátyás).

Legyen \(\displaystyle D\) a \(\displaystyle BK\) és \(\displaystyle AC\) egyenesek metszéspontja, \(\displaystyle E\) a \(\displaystyle CL\) és \(\displaystyle AB\) metszéspontja, \(\displaystyle P\) pedig \(\displaystyle BD\) és \(\displaystyle CE\) metszéspontja. A megadott szögfeltételek alapján \(\displaystyle EBD\sphericalangle =ABK\sphericalangle =ACL\sphericalangle =ECD\sphericalangle\), tehát \(\displaystyle BCDE\) húrnégyszög. Jelöljük \(\displaystyle BCDE\) középpontját \(\displaystyle A'\)-vel. Másrészt \(\displaystyle LBD\sphericalangle \,=\, LBK\sphericalangle \,=\, LNC\sphericalangle == 180^{\circ}-LND\sphericalangle\), így \(\displaystyle BDNL\), és hasonlóan \(\displaystyle CEMK\) is húrnégyszög.

A megoldás fő észrevétele a következő

Állítás. A \(\displaystyle K\) és \(\displaystyle L\) is rajta van az \(\displaystyle AA'\) átmérőjű körön, amelyet \(\displaystyle \omega\)-val fogunk jelölni.

3. feladat. Legyen \(\displaystyle n\) pozitív egész. Liu Bangnak és Csang Junak van egy \(\displaystyle 1\) egység hosszú pálcája, amit fel akarnak osztani egymás között. Előbb Liu kijelöl legfeljebb \(\displaystyle n\) pontot a pálcán, utána Csang is kijelöl legfeljebb \(\displaystyle n\) pontot a pálcán. A megjelölt pontok különbözők. Ezután a pálcát elvágják minden megjelölt ponton, így néhány darabra esik szét. Ezek után felváltva kiválasztják maguknak a pálca egy-egy olyan darabját, amit még senki sem választott; Liu választ először. Mindkét játékos célja az, hogy a magának kiválasztott darabok hosszának összege a lehető legnagyobb legyen.

Határozzuk meg minden egyes \(\displaystyle n\)-re a legnagyobb olyan \(\displaystyle c\) értéket, amelyre Liu biztosan elérheti, hogy a pálcadarabjainak összege legalább \(\displaystyle c\) legyen, függetlenül attól, hogyan játszik Csang.

  Javasolta: Oroszország

Megoldás (Szakács Ábel). Azt állítjuk, hogy Liu \(\displaystyle c=\frac{2^n}{2^{n+1}-1}\) összhossznyi pálcát tud garantálni. Mutatunk egy stratégiát, amellyel elérheti, hogy a pálcái összege legalább \(\displaystyle \frac{2^n}{2^{n+1}-1}\) legyen, és mutatunk egy olyan stratégiát is, amellyel Csang megakadályozhatja, hogy Liu \(\displaystyle \frac{2^n}{2^{n+1}-1}\)-nél nagyobb összeget érjen el.