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

Molnár István Ádám, Varga Boldizsár, Bodor Mátyás

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

A második nap feladatainak megoldását a novemberi számban közöljük.

1. feladat. Egy síkbeli egyenest napfényesnek nevezünk, ha nem párhuzamos sem az $\displaystyle x$ tengellyel, sem az $\displaystyle y$ tengellyel, sem pedig az $\displaystyle x+y=0$ egyenessel.

Adott egy $\displaystyle n\geqslant3$ egész szám. Határozzuk meg az összes $\displaystyle k$ nemnegatív egész számot, amelyre létezik $\displaystyle n$ különböző egyenes a síkon az alábbi tulajdonságokkal:

ha $\displaystyle a$ és $\displaystyle b$ pozitív egészekre $\displaystyle a+b\le n+1$ teljesül, akkor az $\displaystyle (a,b)$ pont rajta van legalább egy egyenesen; valamint
az $\displaystyle n$ egyenes közül pontosan $\displaystyle k$ napfényes.

Javasolta: USA

Megoldás. (Molnár István Ádám) hogy $\displaystyle k$ lehetséges értékei $\displaystyle 0$, $\displaystyle 1$ és $\displaystyle 3$.

A feladatban megadott rácspontokat egy derékszögű egyenlő szárú háromszögben ábrázolhatjuk. A továbbiakban ezeket a pontokat fogjuk rácspontnak hívni. A definíció szerint egy egyenes akkor napfényes, ha nem párhuzamos a háromszög egyik oldalával sem.

A háromszög kerületén levő rácspontokat határpontnak, a három oldalegyenest határegyenesnek fogjuk hívni. A fenti ábrán ezeket kék színnel rajzoltuk meg.

Először mutatunk egy-egy példát arra, hogy a rácspontokat le lehet fedni $\displaystyle n$ olyan egyenessel, amelyek közül pontosan $\displaystyle k=0$, $\displaystyle k=1$, illetve $\displaystyle k=3$ napfényes. Az egyeneseknek egy-egy ilyen elrendezése látható az alábbi ábrákon; a napfényes egyeneseket piros színnel rajzoltuk.

$k=0$	$k=0$	$k=0$

A továbbiakban belátjuk, hogy $\displaystyle k$ értéke csak a fenti $\displaystyle 0$, $\displaystyle 1$ és $\displaystyle 3$ lehet.

Előfizetőink bejelentkezés után a teljes cikket elolvashatják.

2. feladat. Legyen az $\displaystyle \Omega$, illetve $\displaystyle \Gamma$ körök középpontja rendre $\displaystyle M$, illetve $\displaystyle N$. Tegyük fel, hogy $\displaystyle \Omega$ sugara kisebb, mint $\displaystyle \Gamma$ sugara, valamint hogy $\displaystyle \Omega$ és $\displaystyle \Gamma$ a (különböző) $\displaystyle A$ és $\displaystyle B$ pontokban metszik egymást. Az $\displaystyle MN$ egyenes $\displaystyle \Omega$-t a $\displaystyle C$ pontban, $\displaystyle \Gamma$-t pedig a $\displaystyle D$ pontban metszi olyan módon, hogy $\displaystyle C$, $\displaystyle M$, $\displaystyle N$ és $\displaystyle D$ ebben a sorrendben követik egymást az egyenesen. Jelölje $\displaystyle P$ az $\displaystyle ACD$ háromszög körülírt körének a középpontját. Messe az $\displaystyle AP$ egyenes $\displaystyle \Omega$-t az $\displaystyle E\neq A$ pontban. Messe az $\displaystyle AP$ egyenes $\displaystyle \Gamma$-t az $\displaystyle F\neq A$ pontban. Legyen $\displaystyle H$ a $\displaystyle PMN$ háromszög magasságpontja.

Bizonyítsuk be, hogy a $\displaystyle H$-n átmenő, $\displaystyle AP$-vel párhuzamos egyenes érinti a $\displaystyle BEF$ háromszög körülírt körét.

(Egy háromszög magasságpontja a magasságvonalainak metszéspontja.)

Javasolta: Vietnám

Megoldás. (Varga Boldizsár) A megoldáshoz előbb belátunk néhány segédállítást.

1. állítás. $\displaystyle MAP\sphericalangle=PAN\sphericalangle$.

Bizonyítás. Mivel $\displaystyle M$ és $\displaystyle P$ is egyenlő távol vannak $\displaystyle A$-tól és $\displaystyle C$-től, ezért az $\displaystyle MP$ egyenes az $\displaystyle AC$ szakasz felezőmerőlegese, vagyis az $\displaystyle AMC$ szög belső szögfelezője, amely éppen az $\displaystyle NMA$ szög külső szögfelezője. Hasonlóan $\displaystyle NP$ az $\displaystyle ANM$ szög külső szögfelezője, ezért a két egyenes metszéspontja, $\displaystyle P$ az $\displaystyle ANM$ háromszög $\displaystyle A$-val szemközti hozzáírt körének középpontja, amely rajta van az $\displaystyle MAN$ szög belső szögfelezőjén is, tehát valóban, $\displaystyle MAP\sphericalangle=PAN\sphericalangle$. $\displaystyle \Box$

Előfizetőink bejelentkezés után a teljes cikket elolvashatják.

3. feladat. Jelölje $\displaystyle \mathbb{N}$ a pozitív egész számok halmazát. Egy $\displaystyle f\colon\mathbb{N} \to \mathbb{N}$ függvényt pöpecnek nevezünk, ha $\displaystyle b^a-f(b)^{f(a)}$ osztható $\displaystyle f(a)$-val tetszőleges $\displaystyle a$ és $\displaystyle b$ pozitív egész számok esetén.

Határozzuk meg a legkisebb $\displaystyle c$ valós konstanst, amelyre $\displaystyle f(n)\leqslant cn$ fennáll minden $\displaystyle f$ pöpec függvényre és minden $\displaystyle n$ pozitív egészre.

Javasolta: Kolumbia

Megoldás. (Bodor Mátyás) Megmutatjuk, hogy $\displaystyle c$ legkisebb lehetséges értéke a $\displaystyle 4$.

Bármely $\displaystyle p$ prímszámra és nemnulla $\displaystyle x$ egészre jelöljük $\displaystyle v_p(x)$-szel az $\displaystyle x$ prímtényezős felbontásában a $\displaystyle p$ kitevőjét. A megoldás során többször is használni fogjuk a Lifting The Exponent (LTE) lemmát:

Ha $\displaystyle p$ páratlan prímszám és $\displaystyle x,y$ egészek úgy, hogy $\displaystyle p\nmid x,y$ és $\displaystyle p\mid x-y$, akkor tetszőleges $\displaystyle n$ pozitív egészre

$\displaystyle v_p(x^n-y^n)=v_p(x-y)+v_p(n). $

$\displaystyle p=2$-re: ha $\displaystyle x,y$ páratlanok és $\displaystyle n$ páros, akkor

$\displaystyle v_2(x^n-y^n)=v_2(x-y)+v_2(x+y)+v_2(n)-1. $

(Bővebben lásd például a https://en.wikipedia.org/wiki/Lifting-the-exponent_lemma oldalt.)

Nekünk csak a $\displaystyle p=2$ az esetre lesz szükségünk.

Először megmutatjuk, hogy $\displaystyle c\geq 4$. Ehhez tekintsük a következő függvényt:

Előfizetőink bejelentkezés után a teljes cikket elolvashatják.

Már regisztráltál?
Új vendég vagy?