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\).

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.

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.

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)