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

Czanik Pál, Holló Martin, 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

Második nap

Az első nap feladatainak megoldását az októberi számban közöltük.

4. feladat. Egy \(\displaystyle N\) pozitív egész szigorú osztói alatt az \(\displaystyle N\)-nél kisebb pozitív osztóit értjük.

Az \(\displaystyle a_1, a_2, \ldots\) végtelen sorozat olyan pozitív egészekből áll, melyek mindegyikének legalább három szigorú osztója van. Minden \(\displaystyle n\geqslant 1\) esetén \(\displaystyle a_{n+1}\) megegyezik \(\displaystyle a_n\) három legnagyobb szigorú osztójának összegével.

Határozzuk meg \(\displaystyle a_1\) összes lehetséges értékét.

Javasolta: Litvánia

Megoldás (Holló Martin). Azt fogjuk megmutatni, hogy pontosan azok a számok jók – vagyis ezek lehetnek a sorozat első elemei –, amelyek nem oszthatók \(\displaystyle 5\)-tel, a prímtényezős felbontásukban a \(\displaystyle 2\) kitevője valamilyen \(\displaystyle k\) nemnegatív számra \(\displaystyle 2k+1\), és a \(\displaystyle 3\) kitevője legalább \(\displaystyle k+1\).

Ahhoz, hogy az ilyen számok jók, elég megmutatnunk, hogy minden ilyen számnak van legalább \(\displaystyle 4\) osztója, és ha \(\displaystyle a_n\) tudja ezt a tulajdonságot, akkor \(\displaystyle a_{n+1}\) is tudja. Minden ilyen tulajdonságú számnak osztója az \(\displaystyle 1\), \(\displaystyle 2\), \(\displaystyle 3\) és a \(\displaystyle 6\), továbbá ha \(\displaystyle a_n\) négy legkisebb osztója az \(\displaystyle 1<b<c<d\), akkor a három legnagyobb szigorú osztó az \(\displaystyle \dfrac{a_n}{b}>\dfrac{a_n}{c}>\dfrac{a_n}{d}\), és így \(\displaystyle a_{n+1}=\left(\dfrac{1}{b}+\dfrac{1}{c}+\dfrac{1}{d}\right)a_n\).

Ha \(\displaystyle k=0\), akkor \(\displaystyle a_n\) szám nem osztható \(\displaystyle 4\)-gyel, a három legkisebb osztó a \(\displaystyle 2\), \(\displaystyle 3\) és a \(\displaystyle 6\), és így

\(\displaystyle a_{n+1}=\left(\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{6} \right)a_n=a_n, \)

vagyis innen kezdve a sorozat konstans.

Ha \(\displaystyle k>0\), akkor \(\displaystyle b=2\), \(\displaystyle c=3\), \(\displaystyle d=4\), és így

\(\displaystyle a_{n+1}=\left(\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{4} \right)a_n=\dfrac{13a_n}{12}, \)

és így \(\displaystyle a_{n+1}\) továbbra sem osztható \(\displaystyle 5\)-tel, a \(\displaystyle 2\) kitevője \(\displaystyle 2\)-vel csökkent, vagyis most \(\displaystyle 2(k-1)+1\), és a \(\displaystyle 3\) kitevője \(\displaystyle 1\)-gyel csökkent, vagyis ha eddig legalább \(\displaystyle k\) volt, akkor most még mindig legalább \(\displaystyle k-1\), ezzel beláttuk, hogy ezek a számok jók.

A megfordításhoz először megmutatjuk, hogy a sorozat egyik eleme sem lehet páratlan. Ha \(\displaystyle a_n\) páratlan, akkor minden osztója, és így \(\displaystyle a_{n+1}\) is páratlan. Ha az \(\displaystyle a_n\) négy legkisebb osztója \(\displaystyle 1<b<c<d\), akkor

\(\displaystyle a_{n+1}=\left(\dfrac{1}{b}+\dfrac{1}{c}+\dfrac{1}{d} \right)a_n\leq \left(\dfrac{1}{3}+\dfrac{1}{5}+\dfrac{1}{7} \right)a_n<a_n, \)

vagyis innentől kezdve a sorozat elemei szigorúan csökkennek, ami egy csak pozitív egészekből álló sorozatnál nem lehetséges.

Most azt is megmutatjuk, hogy a sorozat minden eleme osztható \(\displaystyle 3\)-mal. Ehhez elég megmutatnunk, hogy ha \(\displaystyle a_n\) páros és nem osztható \(\displaystyle 3\)-mal, akkor \(\displaystyle a_{n+1}\) páratlan (és akkor rögtön készen vagyunk), vagy pedig kisebb mint \(\displaystyle a_n\) és nem osztható \(\displaystyle 3\)-mal (ekkor pedig a sorozat mindig csökkenne, ami szintén nem lehet). Továbbra is legyen az \(\displaystyle a_n\) négy legkisebb osztója \(\displaystyle 1<b<c<d\). Mivel \(\displaystyle a_n\) páros, ezért \(\displaystyle b=2\), továbbá tudjuk, hogy \(\displaystyle c>3\).

• Ha \(\displaystyle c=4\), akkor \(\displaystyle a_{n+1}=\dfrac{a_n}2+\dfrac{a_n}4+\dfrac{a_n}{d}=\dfrac{3a_n}{4}+\dfrac{a_n}{d}\); az első tag osztható \(\displaystyle 3\)-mal, a második nem; tehát \(\displaystyle a_{n+1}\) nem lehet osztható \(\displaystyle 3\)-mal. Továbbá \(\displaystyle a_{n+1}<\left(\dfrac12+\dfrac14+\dfrac15\right)a_n<a_n\).
• Ha \(\displaystyle c>4\), akkor \(\displaystyle a_n\) nem osztható \(\displaystyle 4\)-gyel, így \(\displaystyle c\) páratlan, az \(\displaystyle a_n\) legkisebb páratlan prímosztója. Ezen az eseten belül,
• Ha \(\displaystyle d\) is páratlan, akkor \(\displaystyle \dfrac{a_n}2\) páratlan, míg \(\displaystyle \dfrac{a_n}{c}\) és \(\displaystyle \dfrac{a_n}{d}\) páros, tehát ezek összege, \(\displaystyle a_{n+1}\) páratlan.
• Ha \(\displaystyle d\) páros, akkor \(\displaystyle d/2\) egy még kisebb osztó, ami csak a \(\displaystyle c\) lehet, vagyis \(\displaystyle d=2c\). Ekkor \(\displaystyle a_{n+1}=\dfrac{a_n}2+\dfrac{a_n}{c}+\dfrac{a_n}{2c}=\dfrac{a_n}2+\dfrac{3a_n}{2c}\); a második tag osztható \(\displaystyle 3\)-mal, az első nem, tehát \(\displaystyle a_{n+1}\) sem osztható \(\displaystyle 3\)-mal. Továbbá \(\displaystyle a_{n+1}\le\dfrac{a_n}2+\dfrac{3a_n}{10}<a_n\).

Így tehát feltehetjük, hogy a sorozat minden eleme osztható \(\displaystyle 2\)-vel és \(\displaystyle 3\)-mal.

Ha \(\displaystyle a_n\) osztható 4-gyel is, akkor a legkisebb osztói 1, 2, 3, 4, és \(\displaystyle a_{n+1}=\dfrac{a_n}2+\dfrac{a_n}3+\dfrac{a_n}4=\dfrac{13a_n}{12}\), tehát a következő tagban a 2 kitevője 2-vel csökken, a 3 kitevője pedig 1-gyel, az 5 kitevője nem változik.

Ezért ha \(\displaystyle a_1\) prímtényezős felbontásában a 2 kitevője páros, akkor minden lépés után páros marad, így viszont véges sok lépés után eljutunk egy páratlan elemhez, ami nem lehetséges. Az \(\displaystyle a_1\)-ben tehát a \(\displaystyle 2\) kitevője csak páratlan lehet, \(\displaystyle 2k+1\) valamilyen \(\displaystyle k\) nemnegatív egésszel. \(\displaystyle k\) lépés után eljutunk az \(\displaystyle a_{k+1}=\left(\dfrac{13}{12}\right)^k\) számhoz, amely páros, de nem osztható 4-gyel. Mivel ez az elem is osztható 3-mal, az \(\displaystyle a_1\) prímtényezős felbontásában a 3 kitevője legalább \(\displaystyle k+1\).

Már csak azt kell ellenőriznünk, hogy \(\displaystyle a_1\) nem lehet osztható 5-tel. Ha \(\displaystyle a_1\) osztható 5-tel, akkor \(\displaystyle a_{k+1}\) is osztható 5-tel, ezért \(\displaystyle a_{k+1}\) négy legkisebb osztói 1, 2, 3, 5, akkor viszont \(\displaystyle a_{k+2}=\dfrac{a_{k+1}}2+\dfrac{a_{k+1}}3+\dfrac{a_{k+1}}5\); az első tag páratlan, a másik kettő pedig páros; ez ellentmond annak, hogy \(\displaystyle a_{k+2}\) páros.

5. feladat. Hanga és Ábel egy kétszemélyes játékot játszanak, amelynek a szabályai egy \(\displaystyle \lambda\) pozitív valós számtól függenek, amelyet mindkét játékos ismer. Az \(\displaystyle n\)-edik lépésben (\(\displaystyle n=1\)-gyel kezdődően) a következő történik.

• Ha \(\displaystyle n\) páratlan, Hanga választ egy \(\displaystyle x_n\) nemnegatív valós számot úgy, hogy

\(\displaystyle x_1+x_2+\dots+x_n \leqslant \lambda n. \)

• Ha \(\displaystyle n\) páros, Ábel választ egy \(\displaystyle x_n\) nemnegatív valós számot úgy, hogy

\(\displaystyle x_1^2+x_2^2+\dots+x_n^2 \leqslant n. \)

Ha valamelyik játékos nem tud megfelelő \(\displaystyle x_n\) számot választani, a játék véget ér és a másik játékos nyer. Ha a játék örökké tart, egyik játékos sem nyer. A választott számok mindkét játékos számára ismertek.

Határozzuk meg az összes olyan \(\displaystyle \lambda\) számot, amelyre Hangának nyerő stratégiája van, valamint az összes olyat, amelyre Ábelnek nyerő stratégiája van.

Javasolta: Olaszország

Megoldás (Szakács Ábel). Azt állítjuk, hogy

• ha \(\displaystyle 0<\lambda<\dfrac{1}{\sqrt2}\), akkor Ábelnek van nyerő stratégiája;
• ha \(\displaystyle \lambda>\dfrac{1}{\sqrt2}\), akkor Hangának van nyerő stratégiája;
• ha \(\displaystyle \lambda=\dfrac{1}{\sqrt2}\), akkor mindkét játékos meg tudja akadályozni, hogy a másik nyerjen.

Először mutatunk egy egyszerű stratégiát, amelyet követve \(\displaystyle \lambda\ge\dfrac{1}{\sqrt2}\) esetén Hanga nem veszíthet. Válassza Hanga mindig a \(\displaystyle 0\) számot, tehát legyen minden \(\displaystyle n=(2k+1)\)-re \(\displaystyle x_n=0\). Gondoljuk meg, hogy Hanga ezt megteheti úgy, hogy sohasem sérül a \(\displaystyle \sum\limits_{i=1}^{n}x_i\le\lambda n\) feltétel.

Ábel \(\displaystyle 2k\)-adik lépése után \(\displaystyle \sum\limits_{i=1}^{2k} x_{i}^2\le2k\). A számtani és négyzetes közepek közti egyenlőtlenséggel felülről becsülhetjük az összeget. Mivel \(\displaystyle x_1=x_3=\ldots=x_{2k+1}=0\),

Így Hanga mindig folytatni tudja ezt a stratégiát.

Ha \(\displaystyle \lambda>\dfrac{1}{\sqrt2}\), akkor nemcsak nem vesztő, de nyerő stratégiája is van Hangának, mert elegendően sok 0 választása után tudja elég nagynak választani számát ahhoz, hogy Ábel rögtön veszítsen. Válasszunk egy olyan nagy \(\displaystyle N\) pozitív egész számot, amelyre \(\displaystyle (\lambda(2N+1)-\sqrt2N)^2 > 2N+2\) (ilyen létezik, mert a bal oldalon álló kifejezés másodfokú), és legyenek Hanga lépései

\(\displaystyle x_1=x_3=x_5=\ldots=x_{2N-1}=0, \qquad x_{2N+1}=\lambda(2N+1)-\sum\limits_{k=1}^{2N}x_k. \)

Mint láttuk, \(\displaystyle \sum\limits_{k=1}^{2N}x_k\le\sqrt2N<\lambda(2N+1)\), így \(\displaystyle x_{2N+1}>0\), vagyis Hangának ez a lépése is megengedett. Másrészt

\(\displaystyle \sum\limits_{k=1}^{2N+1}x_k^2 \ge x_{2N+1}^2\ge(\lambda(2N+1)-\sqrt2N)^2 > 2N+2, \)

így Ábel a \(\displaystyle (2N+2)\)-edik lépésben nem tud lépni, és Hanga nyer.

Most vizsgáljuk azt az esetet, ha \(\displaystyle \lambda\le\dfrac{1}{\sqrt2}\). Legyen Ábel stratégiája az, hogy mindig a legnagyobb megengedett számot választja:

\(\displaystyle x_{2n}=\sqrt{2-x_{2n-1}^2}. \)

Megmutatjuk, hogy Ábel ezt mindig megteheti, tehát Hanga nem nyerhet; ha pedig \(\displaystyle \lambda<\dfrac{1}{\sqrt2}\), akkor előáll egy olyan helyzet, amikor Hanga nem tud lépni, tehát Ábel nyer.

Vegyük észre, hogy minden pozitív egész \(\displaystyle n\)-re

\(\displaystyle x_{2n-1}+x_{2n}=\sqrt{x_{2n-1}^2+2x_{2n-1}x_{2n}+x_{2n}^2}\ge\sqrt{x_{2n-1}^2+x_{2n}^2}=\sqrt2, \)

ezért

\(\displaystyle x_1+x_2+\ldots+x_{2n} \ge n\sqrt2 \ge \lambda\cdot 2n \)

(ez az \(\displaystyle n=0\) esetben is igaz, amikor a bal oldalon üres összeg áll). Emiatt Hanga mindig legfeljebb \(\displaystyle \lambda\le\frac{1}{\sqrt{2}}\)-nek tudja választani \(\displaystyle x_{2n+1}\)-et, tehát Ábel mindig tud lépni, Hanga nem nyerhet.

Ha \(\displaystyle \lambda<\dfrac{1}{\sqrt2}\), akkor Ábel nyerni is fog ezzel a stratégiával. Ha \(\displaystyle N\) olyan nagy pozitív egész, amelyre \(\displaystyle \sqrt2N > (2N+1)\lambda\) (ilyen \(\displaystyle N\) létezik, mert \(\displaystyle \sqrt2>2\lambda\)), akkor

\(\displaystyle \sum\limits_{k=1}^{2N}x_k \ge\sqrt2N > (2N+1)\lambda, \)

tehát Hanga legkésőbb a \(\displaystyle (2N+1)\)-edik lépésben biztosan veszít.

6. feladat. Vegyünk egy \(\displaystyle 2025 \times 2025\) egységnégyzetből álló négyzetrácsot. Matild téglalap alakú csempéket helyez a rácsra (amelyek mérete eltérő lehet) úgy, hogy a csempék oldalai a rácsegyenesekre esnek, illetve minden egységnégyzetet legfeljebb egy csempe fed.

Határozzuk meg, legkevesebb hány csempét kell Matildnak leraknia ahhoz, hogy a rács minden sorában és minden oszlopában pontosan egy egységnégyzetet ne fedjen csempe.

Javasolta: Szingapúr

Megoldás (Czanik Pál, az IMO Shortlist alapján). Az állítjuk, hogy \(\displaystyle 2025+{2\cdot45}-3=2112\) csempére van szüksége Matildnak, és általánosabban, ha \(\displaystyle {n=k^2}\) négyzetszám, akkor egy \(\displaystyle n\times n\)-es négyzetrács esetén a válasz \(\displaystyle k^2+2k-3\). (Ez valóban általánosabb állítás, hiszen \(\displaystyle 2025=45^2\).)

Vegyük az alábbi konstrukciót (az ábrán \(\displaystyle k=4\)): Összesen \(\displaystyle (k-1)^2\) darab, \(\displaystyle {k\times k}\) méretű csempe van középen és \(\displaystyle k-1\) minden oldalt, ami összesen \(\displaystyle k^2+2k-3\) csempe.

1. ábra

Így tudjuk, hogy ennyi csempe elegendő.

A megoldás konstrukciója a Sunshine Coast-i repülőtér várótermének padlóján
(Forrás: https://stea.com.au/sunshine-coast-airport)

Annak bizonyításához, hogy ennél kevesebbel nem tudja Matild lefedni a négyzetrácsot, felhasználjuk az Erdős–Szekeres tételt:

Tétel. Tetszőleges \(\displaystyle p,q\) nemnegatív egészek és \(\displaystyle pq+1\) különböző számból álló sorozatban van egy legalább \(\displaystyle (p+1)\) elemű monoton növekvő részsorozat, vagy egy legalább \(\displaystyle (q+1)\)-elemű monoton csökkenő részsorozat.

(Lásd https://hu.wikipedia.org/wiki/Erdős–Szekeres-tétel)

A tétel egy átfogalmazása. Ha egy \(\displaystyle n\) hosszú, különböző számokból álló sorozatban a leghosszabb monoton növekvő részsorozat \(\displaystyle p\), a leghosszabb monoton csökkenő részsorozat \(\displaystyle q\) elemű, akkor \(\displaystyle pq\ge n\).

Vegyünk egy tetszőleges csempézést, jelöljük a kimaradó mezőket \(\displaystyle {\boldsymbol{\times}}\)-ekkel, és a táblázat mind a négy oldalára helyezzünk egy \(\displaystyle n\times 1\)-es csempét. Így minden \(\displaystyle {\boldsymbol{\times}}\) négy különböző csempével szomszédos a négy oldalán, és minden csempe minden oldalán legfeljebb egy \(\displaystyle {\boldsymbol{\times}}\)-szel szomszédos.

Nevezzük leghosszabb növekvő részsorozatnak (LNR) azt a töröttvonalat, ami a lehető legtöbb \(\displaystyle {\boldsymbol{\times}}\) közepét köti össze sorban úgy, hogy mindegyik jobbra-fel található az előzőtől, és ehhez vegyük hozzá a táblázat bal-alsó és jobb-felső sarkát is. Hasonlóan definiáljuk a leghosszabb csökkenő részsorozatot (LCsR) bal-fentről jobbra-le. Legyen az LNR-en lévő \(\displaystyle {\boldsymbol{\times}}\)-ek száma \(\displaystyle a\) és az LCsR-en lévő \(\displaystyle {\boldsymbol{\times}}\)-ek száma \(\displaystyle b\). Az Erdős–Szekeres tétel átfogalmazása szerint \(\displaystyle ab\geq n\).

A két töröttvonal négy részre bontja a négyzetrácsot: \(\displaystyle A\)-ra, \(\displaystyle B\)-re, \(\displaystyle C\)-re és \(\displaystyle D\)-re, ahol \(\displaystyle A\) a két töröttvonaltól balra, \(\displaystyle B\) felettük, \(\displaystyle C\) tőlük jobbra és \(\displaystyle D\) alattuk található. Kössük össze az összes \(\displaystyle A\)-ban (vagy határán) lévő \(\displaystyle {\boldsymbol{\times}}\)-et a közvetlenül tőle balra elhelyezkedő csempével, hasonlóan a \(\displaystyle B\)-beliket a fölöttük levővel, a \(\displaystyle C\)-beliket a tőlük jobbra levővel és a \(\displaystyle D\)-beli \(\displaystyle {\boldsymbol{\times}}\)-eket az alattuk levő csempével.

2. ábra

Lemma. Minden csempét legfeljebb egy \(\displaystyle {\boldsymbol{\times}}\)-szel kötöttünk össze.

Bizonyítás. Tegyük fel indirekten, hogy egy csempét két \(\displaystyle {\boldsymbol{\times}}\)-szel is összekötöttünk, ekkor vizsgáljunk három esetet:

1. eset: A két \(\displaystyle {\boldsymbol{\times}}\) a csempe ugyanazon oldalán van. Ekkor ugyanabban a sorban vagy oszlopban vannak, ami ellentmondás.

2. eset: A két \(\displaystyle {\boldsymbol{\times}}\) szemközti oldalon van, feltehetjük, hogy az egyik, \(\displaystyle {\boldsymbol{\times}}_{d}\) felül és a másik, \(\displaystyle {\boldsymbol{\times}}_{b}\), alul. Ekkor \(\displaystyle {\boldsymbol{\times}}_{d}\) az \(\displaystyle {\boldsymbol{\times}}_{b}\) felett van, de \(\displaystyle {\boldsymbol{\times}}_{d}\) a \(\displaystyle D\) részben, míg \(\displaystyle {\boldsymbol{\times}}_{b}\) a \(\displaystyle B\) részben van, ami ellentmondás.

3. eset: A két \(\displaystyle {\boldsymbol{\times}}\) szomszédos oldalon van, ekkor feltehetjük, hogy az egyik, \(\displaystyle {\boldsymbol{\times}}_{a}\), jobb oldalt és a másik, \(\displaystyle {\boldsymbol{\times}}_{b}\), alul. Ekkor \(\displaystyle {\boldsymbol{\times}}_{a}\) jobbra-fel található \(\displaystyle {\boldsymbol{\times}}_{b}\)-től. Viszont \(\displaystyle {\boldsymbol{\times}}_{a}\) az \(\displaystyle A\) részben, \(\displaystyle {\boldsymbol{\times}}_{b}\) pedig a \(\displaystyle B\) részben található, ami ezzel ellentmond.    \(\displaystyle \Box\)

Számoljuk meg kétféleképpen az összekötött \(\displaystyle {\boldsymbol{\times}}\)-csempe párokat. Minden \(\displaystyle {\boldsymbol{\times}}\) legalább egy csempével össze van kötve, és azok, amelyek valamely töröttvonalon találhatóak, legalább kettővel. Az ábrán látható esetben a két töröttvonal egy \(\displaystyle {\boldsymbol{\times}}\)-en metszi egymást, így ez \(\displaystyle 4\) csempével is össze van kötve, azaz a csempék száma legalább \(\displaystyle (n-a-b+1)+2(a-1)+2(b-1)+4=n+a+b+1\). Ha a két töröttvonal nem egy \(\displaystyle {\boldsymbol{\times}}\)-en találkozik, csak \(\displaystyle n+a+b\) csempéhez kötöttük az \(\displaystyle {\boldsymbol{\times}}\)-eket. Viszont ekkor az a csempe, amelyen a két töröttvonal találkozik, egy \(\displaystyle {\boldsymbol{\times}}\)-szel sincs összekötve, vagyis ebben az esetben is legalább \(\displaystyle n+a+b+1\) csempénk van. Így a csempék száma legalább

\(\displaystyle n+a+b+1\geq n+2\sqrt{ab}+1\geq n+2\sqrt{n}+1=k^2+2k+1. \)

Ha ebből kivonjuk azt a négy csempét, amit a négy oldalra helyeztünk, megkapjuk az \(\displaystyle (k^2+2k-3)\)-as alsó becslést, amit állítottunk.