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) Megmutatjuk 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őször nézzük az $\displaystyle n=3$ eset; azt kell ellenőriznünk, hogy $\displaystyle k=2$ nem lehetséges.

1. eset: Van olyan egyenes, amely három rácsponton is átmegy.

Ez az egyenes csak egy határegyenes lehet (amely tehát nem napfényes), és három lefedetlen rácspont marad, egy kisebb derékszögű háromszög alakban.

A megmaradt három rácspontot két egyenessel kell lefednünk, tehát legalább az egyiknek két rácsponton át kell mennie, ez az egyenes viszont nem lehet napfényes. Ebben az esetben tehát legfeljebb egy napfényes egyenest használhatunk fel, vagyis $\displaystyle k=0$ vagy $\displaystyle k=1$.

2. eset: Nincs olyan egyenes, amely három rácsponton menne keresztül.

Mivel hat rácspontot kell lefednünk három egyenessel, mindegyik egyenesnek pontosan két rácsponton kell keresztül mennie.

Vegyük észre, hogy összesen csak három olyan napfényes egyenes létezik, amely pontosan két rácsponton megy keresztül; ha ezek közül kettőt megrajzolunk, a megmaradt két rácspontot a harmadik napfényes egyenessel kell lefednünk. Ebben az esetben tehát vagy kettőnél kevesebb, vagy pedig mindhárom napfényes egyenest fel kell használnunk; $\displaystyle k=2$ nem lehetséges. Ezzel az $\displaystyle n=3$, $\displaystyle k=2$ eset vizsgálatával kész vagyunk.

Az általános eset megoldása a következő észrevételen múlik.

Lemma. Ha $\displaystyle n\ge4$, és a rácspontokat lefedjük $\displaystyle n$ egyenessel, akkor ezek között biztosan van legalább egy határegyenes.

Bizonyítás. A háromszögnek összesen $\displaystyle 3n-3$ határpontja van. Mivel $\displaystyle n>3$ miatt $\displaystyle 3n-3>2n$, a skatulyaelv miatt valamelyik egyenes legalább három határponton megy át; ez az egyenes viszont csak a háromszög valamelyik oldalegyenese, tehát az egyik határegyenes lehet.

Ezek után egyszerű teljes indukcióval igazolhatjuk, hogy $\displaystyle n\ge3$ esetén $\displaystyle k$ csak $\displaystyle 0$, $\displaystyle 1$ és $\displaystyle 3$ lehet. A kiinduló $\displaystyle n=3$ esetet már megvizsgáltuk. Tegyük fel, hogy $\displaystyle n\ge4$, és az állításunk igaz az $\displaystyle n$ kisebb értékeire.

Tekintsünk a háromszög egy tetszőleges lefedését $\displaystyle n$ egyenessel. A Lemma szerint a fedésben van legalább egy $\displaystyle h$ határegyenes (ami nem napfényes).

Bármelyik oldalegyenes is legyen a $\displaystyle h$, a többi rácspont egy $\displaystyle n-1$ méretű háromszöget alkot, és ennek a rácspontjait fedi le a többi $\displaystyle n-1$ egyenes. Az indukciós feltevés szerint a többi $\displaystyle n-1$ egyenes között pontosan $\displaystyle 0$, $\displaystyle 1$ vagy $\displaystyle 3$ napfényes lehet; mivel a $\displaystyle h$ nem napfényes, ez igazolja az állítást.

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$

2. állítás. $\displaystyle ME\parallel{AN}$ és $\displaystyle NF\parallel{AM}$, tehát az $\displaystyle ANTM$ négyszög paralelogramma.

Bizonyítás. Mivel $\displaystyle ME=MA$ az $\displaystyle \Omega$ kör sugarai, ezért $\displaystyle MAE\sphericalangle=AEM\sphericalangle$. Azonban az előző állítás szerint $\displaystyle MAE\sphericalangle=EAN\sphericalangle$, tehát $\displaystyle AEM\sphericalangle=EAN\sphericalangle$, vagyis $\displaystyle ME\parallel{AN}$. Az állítás második fele hasonlóan következik abból, hogy $\displaystyle NFA\sphericalangle=FAN\sphericalangle=MAF\sphericalangle$. $\displaystyle \Box$

A feladat megoldásához legyen $\displaystyle T$ az $\displaystyle ME$ és $\displaystyle NF$ egyenesek metszéspontja; azt fogjuk megmutatni, hogy a $\displaystyle H$-n átmenő, $\displaystyle AP$-vel párhuzamos egyenes $\displaystyle T$-ben érinti a $\displaystyle BEF$ kört. Ehhez elég belátni, hogy $\displaystyle T$ rajta van a körön, és a ($\displaystyle B$-t nem tartalmazó) $\displaystyle EF$ ív felezőpontja, illetve $\displaystyle TH\parallel{EF}$, ekkor ugyanis $\displaystyle TH$ a kör $\displaystyle EF$ ívének felezőpontjában húzott érintő a szimmetria miatt.

Az előbbihez vegyük észre, hogy a kerületi és középponti szögek tétele miatt $\displaystyle BFE\sphericalangle=BFA\sphericalangle=\frac12BNA\sphericalangle=MNA\sphericalangle$, és $\displaystyle BEF\sphericalangle=180^\circ-AEB\sphericalangle=BCA\sphericalangle=\frac12BMA\sphericalangle=NMA\sphericalangle$, ahonnan

$$\begin{gather*} FBE\sphericalangle =180^\circ-EFB\sphericalangle-BEF\sphericalangle =180^\circ-ANM\sphericalangle-NMA\sphericalangle=\\ =MAN\sphericalangle =NTM\sphericalangle =180^\circ-ETF\sphericalangle, \end{gather*}$$

tehát $\displaystyle EBFT$ húrnégyszög. Ekkor $\displaystyle FET\sphericalangle=AEM\sphericalangle=MAE\sphericalangle=TFE\sphericalangle$ (a párhuzamosságok miatt), vagyis az $\displaystyle EFT$ háromszög egyenlő szárú, és $\displaystyle T$ tényleg a $\displaystyle BEF$ kör valamelyik (némi diszkusszióval látható, hogy $\displaystyle B$-t nem tartalmazó, de erre nincs szükség) $\displaystyle EF$ ívének felezőpontja.

Még azt kell belátnunk, hogy $\displaystyle HT\parallel{AP}$. Ehhez kell az alábbi állítás:

3. állítás. A $\displaystyle H$ pont az $\displaystyle MNT$ háromszög beírt körének középpontja.

Bizonyítás. Elég megmutatni, hogy $\displaystyle MH$, illetve $\displaystyle NH$ felezik a $\displaystyle TMN$, illetve $\displaystyle MNT$ szögeket, a szimmetria miatt elég csak az elsőt. Mivel $\displaystyle MH$ és $\displaystyle AD$ egyaránt merőlegesek $\displaystyle PN$-re, ezért $\displaystyle MH\parallel{AD}$, vagyis $\displaystyle HMN\sphericalangle=ADM\sphericalangle=NAD\sphericalangle=TMH\sphericalangle$ (itt kihasználtuk, hogy $\displaystyle MT\parallel{AD}$), vagyis $\displaystyle MH$ felezi az $\displaystyle NMT$ szöget, mégpedig belülről, hiszen $\displaystyle NDA\sphericalangle<90^\circ$. $\displaystyle \Box$

A 3. állításból következik, hogy $\displaystyle TH$ is felezi az $\displaystyle MTN$ szöget. De $\displaystyle MTN$ paralelogramma, ezért az $\displaystyle MAN$ és $\displaystyle NTM$ szögek belső szögfelezői egymás tükörképei a paralelogramma középpontjára, tehát párhuzamosak, azaz $\displaystyle AP\parallel{TH}$, és éppen ezt akartuk bizonyítani.

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:

$\displaystyle g(x) = \begin{cases} 1,& \text{ha }x\text{ páratlan}, \\ 2,& \text{ha }x=2,\\ 2^{v_2(x)+2},& \text{ha }x\text{ páros és }x>2. \end{cases} $

A $\displaystyle g$ függvény pöpec, mert:

Ha $\displaystyle a$ páratlan, akkor $\displaystyle g(a)=1\mid b^a-g(b)$.
Ha $\displaystyle a=2$, akkor az kell, hogy $\displaystyle g(a)=2\mid b^2-g(b)^2$, ami igaz, mert a konstrukcióból látható, hogy $\displaystyle b$ és $\displaystyle g(b)$ paritása mindig megegyezik.
Ha $\displaystyle a$ páros, $\displaystyle a\geq 4$ és $\displaystyle b$ páros, akkor az kell, hogy $\displaystyle g(a)=2^{v_2(a)+2}\mid b^a-g(b)^{2^{v_2(a)+2}}$. Mivel $\displaystyle 2\mid g(b)$ páros, $\displaystyle v_2(g(b)^{2^{v_2(a)+2}})\geq 2^{v_2(a)+2}>v_2(a)+2$, ezért $\displaystyle 2^{v_2(a)+2}\mid g(b)^{2^{v_2(a)+2}}$; másrészt $\displaystyle 2\mid b$ miatt $\displaystyle v_2(b^a)\geq a\geq v_2(a)+2$ (például a $\displaystyle 2$, $\displaystyle 3$, $\displaystyle \ldots$, $\displaystyle a$ számok között legfeljebb $\displaystyle a-2$ darab $\displaystyle 2$-hatvány lehet, mert a $\displaystyle 3$ nem $\displaystyle 2$-hatvány, ezért $\displaystyle v_2(a)\le a-2$). Vagyis $\displaystyle 2^{v_2(a)+2}\mid b^a$, ahonnan következik a kívánt oszthatóság.
Végül, ha $\displaystyle a$ páros, $\displaystyle a\geq 4$ és $\displaystyle b$ páratlan, akkor a feltétel $\displaystyle g(a)=2^{v_2(a)+2}\mid b^a-1$, ez pedig következik az LTE lemmából: $\displaystyle v_2(b^a-1)=v_2(b+1)+v_2(b-1)+v_2(a)-1\geq v_2(a)+2$, hiszen $\displaystyle b+1$ és $\displaystyle b-1$ mindegyike páros, és pontosan az egyik osztható $\displaystyle 4$-gyel is, tehát 2-es kitevője legalább $\displaystyle 2$.

Összegezve, a $\displaystyle g$ függvény valóban pöpec. Emellett $\displaystyle g(4)=2^{2+2}=16$, így $\displaystyle 4c\geq g(4)=16$, tehát biztosan $\displaystyle c\geq 4$.

Most pedig megmutatjuk, hogy $\displaystyle c=4$ eleget tesz a feltételeknek.

Tekintsünk egy tetszőleges pöpec $\displaystyle f$ függvényt. Belátjuk, hogy minden pozitív egész $\displaystyle n$-re $\displaystyle f(n)\leq 4n$, innen készen leszünk. Tetszőleges $\displaystyle a,b$ pozitív egészre legyen $\displaystyle P(a,b)$ az oszthatósági feltétel, tehát $\displaystyle P(a,b)$ annak a rövidítése, hogy $\displaystyle {f(a)\mid b^a-f(b)^{f(a)}}$.

A $\displaystyle P(a,a)$ szerint $\displaystyle f(a)\mid a^a-f(a)^{f(a)}$, ezért $\displaystyle f(a)\mid a^a$. Ha most $\displaystyle a=p$ prímszám, akkor $\displaystyle f(p)\mid p^p$. Ezért $\displaystyle f(p)$ értéke vagy $\displaystyle 1$, vagy pedig $\displaystyle p$-hatvány minden $\displaystyle p$ prímre. Legyen $\displaystyle f(p)=p^{i_p}$, ahol $\displaystyle i_p\geq 0$ egész.

Tegyük fel, hogy van végtelen sok olyan $\displaystyle p$ prím, hogy $\displaystyle i_p\!>\!0$. Legyen emellett $\displaystyle b$ tetszőleges pozitív egész. Válasszunk egy olyan nagy $\displaystyle p$ prímet, hogy $\displaystyle i_p\!>\!0$ és $\displaystyle {p\!>\!|b\!-\!f(b)|}$; ilyen van a feltevésünk miatt. Így $\displaystyle P(p,b)$-ből $\displaystyle p\mid p^{i_p}\!=\!{f(p)\mid b^p\!-\!f(b)^{f(p)}}$. De mind $\displaystyle p$, mind $\displaystyle f(p)$ egy $\displaystyle p$-hatvány, ezért a kis Fermat-tételből $\displaystyle b^p\equiv b \pmod{p}$ és $\displaystyle f(b)^{f(p)}\equiv f(b) \pmod{p}$. A fentiek alapján $\displaystyle p\mid b-f(b)$ és $\displaystyle p>|b-f(b)|$, ami csak úgy lehetséges, ha $\displaystyle b-f(b)=0$, vagyis $\displaystyle f(b)=b$. De $\displaystyle b$ tetszőlegesen volt megválasztva, tehát $\displaystyle f(b)=b\leq 4b$ minden $\displaystyle b$-re.

Marad az az eset, amikor nincs végtelen sok olyan $\displaystyle p$ prím, hogy $\displaystyle i_p>0$, vagyis véges sok van, legyenek ezek $\displaystyle p_1<p_2<\dots<p_k$, és ekkor minden $\displaystyle p>p_k$ prímszámra $\displaystyle f(p)=1$.

Ha egyáltalán nincsenek ilyen $\displaystyle p_1<\dots<p_k$ prímek, akkor $\displaystyle f(p)=1$, minden $\displaystyle p$ prímre. Ha van olyan $\displaystyle a$, amelyre $\displaystyle f(a)>1$, akkor legyen $\displaystyle p$ az $\displaystyle f(a)$ egyik prímosztója. $\displaystyle P(a,p)$-ből $\displaystyle p\mid f(a)\mid p^a-1^{f(a)}=p^a-1$ miatt $\displaystyle p\mid 1$, ellentmondás. Tehát ilyen $\displaystyle a$ nem létezhet; $\displaystyle f(n)=1\leq 4n$ minden $\displaystyle n$-re.

Ha $\displaystyle k\geq 1$, és $\displaystyle p_k>2$, akkor válasszunk egy $\displaystyle p>p_k$ prímet a $\displaystyle p\equiv 2 \pmod{p_k}$ tulajdonsággal; ezt meg tudjuk tenni a Dirichlet-tétel miatt, hiszen $\displaystyle p_k$ és a $\displaystyle 2$ relatív prímek. De $\displaystyle P(p_k,p)$ miatt $\displaystyle p_k\mid f(p_k)\mid p^{p_k}-f(p)^{p_k}=p^{p_k}-1$, de $\displaystyle p^{p_k}-1\equiv p-1\equiv 1 \pmod{p_k}$ a kis Fermat-tételből, ami ellentmondás.

Az az eset marad, amikor $\displaystyle k=1, f(2)$ páros, és $\displaystyle f(p)=1$ minden $\displaystyle p>2$ prímre.

Ha van olyan $\displaystyle a$, hogy $\displaystyle p\mid f(a)$ valamilyen páratlan $\displaystyle p$ prímre, akkor $\displaystyle P(a,p)$ miatt $\displaystyle p\mid f(a)\mid p^a-1^{f(a)}=p^a-1$, ellentmondás. Ez azzal egyenértékű, hogy $\displaystyle f(a)$ minden $\displaystyle a$-ra vagy $\displaystyle 1$, vagy pedig $\displaystyle 2$-hatvány.

A $\displaystyle P(a,3)$-ból $\displaystyle f(a)\mid 3^a-f(3)^{f(a)}=3^a-1$, így páratlan $\displaystyle a$-ra $\displaystyle 4\nmid 3^a-1$ miatt $\displaystyle f(a)\leq 2<4a$. Ha pedig $\displaystyle a$ páros, akkor az LTE lemmából $\displaystyle {v_2(3^a-1)}={v_2(3-1)}+{v_2(3+1)}+v_2(a)-1=v_2(a)+2$, ezért $\displaystyle v_2(a)+2\geq v_2(f(a))=\log_2 f(a)$, ezért $\displaystyle f(a)\leq 2^{v_2(a)+2}=4\cdot 2^{v_2(a)}\leq 4a$.

Tehát az $\displaystyle f(n)\leq 4n$ egyenlőtlenség minden $\displaystyle n\in \mathbb{N}$ számra fennáll, és ez igazolja, hogy $\displaystyle c=4$ megfelelő.

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