Problem B. 4808. (September 2016)

B. 4808. A point \(\displaystyle (a;b)\) of the coordinate plane, where \(\displaystyle a\) and \(\displaystyle b\) are positive integers, is coloured red. Then if a point \(\displaystyle (x;y)\) is red then point \(\displaystyle (x+1;y+1)\), as well as point \(\displaystyle \left(\frac x2;\frac y2\right)\) are also coloured red, provided that \(\displaystyle x\) and \(\displaystyle y\) are both even. If \(\displaystyle (x;y)\) and \(\displaystyle (y;z)\) have both been coloured, then we will also colour the point \(\displaystyle (x;z)\) red. What is the distance from the origin to the closest point coloured red?

Proposed by Z. Bereczki, Szeged

(5 pont)

Deadline expired on October 10, 2016.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Ha \(\displaystyle a=b\), akkor minden később pirosra színezett \(\displaystyle (x;y)\) pontra is \(\displaystyle x=y\) lesz. Az \(\displaystyle (x;x)\) alakú pontok közül az \(\displaystyle (1;1)\) van legközelebb az origóhoz, megmutatjuk, hogy ezt a pontot egy idő után pirosra is fogjuk színezni. Legyen ugyanis \(\displaystyle c\) a legkisebb olyan pozitív egész szám, amelyre \(\displaystyle (c;c)\) piros lesz. (Ilyen \(\displaystyle c\) nyilván létezik, és értéke legfeljebb \(\displaystyle a\).) Ha \(\displaystyle c\) páros lenne, akkor \(\displaystyle (c/2;c/2)\) pontot pirosra színezzük, de ez \(\displaystyle c/2<c\) miatt ellentmondana \(\displaystyle c\) minimalitásának. Ha \(\displaystyle c\geq 3\) páratlan szám lenne, akkor \(\displaystyle (c+1;c+1)\) szintén piros lesz, és így \(\displaystyle ((c+1)/2;(c+1)/2)\) is, viszont \(\displaystyle (c+1)/2<c\) ismét ellentmondana \(\displaystyle c\) minimalitásának. Vagyis csak \(\displaystyle c=1\) lehetséges, tehát \(\displaystyle (1;1)\) is piros lesz, és így ez lesz az origóhoz legközelebbi piros pont, a távolsága az origótól pedig \(\displaystyle \sqrt{2}\).

Tegyük fel most, hogy \(\displaystyle a<b\). A színezési szabályokból következik, hogy minden később pirosra színezett \(\displaystyle (x;y)\) pontra is \(\displaystyle x<y\) lesz. Ha ugyanis \(\displaystyle x<y\), akkor \(\displaystyle x+1<y+1\) és \(\displaystyle x/2<y/2\) is teljesül. Ha pedig \(\displaystyle x<y\) és \(\displaystyle y<z\), akkor \(\displaystyle x<z\) szintén teljesül. Vagyis az összes pirosra színezett pontnak a második koordinátája nagyobb lesz, mint az első. Most megmutatjuk, hogy \(\displaystyle b-a\) legnagyobb páratlan osztója, amit jelöljünk \(\displaystyle t\)-vel, az összes pirosra színezett \(\displaystyle (x;y)\) pont esetén osztja \(\displaystyle (y-x)\)-et. Ehhez ismét végignézzük a háromféle színezési lehetőséget. Mivel \(\displaystyle (y+1)-(x+1)=y-x\), ezért ebben az esetben \(\displaystyle y-x\) sem változik. Mivel \(\displaystyle y/2-x/2=(y-x)/2\), ezért a legnagyobb páratlan osztó ennél a származtatásnál is változatlan marad. Végül tegyük fel, hogy \(\displaystyle x<y<z\), és tudjuk, hogy \(\displaystyle t|y-x\) és \(\displaystyle t|z-y\). Ekkor \(\displaystyle z-x=(z-y)+(y-x)\) miatt \(\displaystyle t|z-x\) szintén teljesül. Vagyis pirosra csak olyan \(\displaystyle (x;y)\) pontokat színezünk, amelyekre \(\displaystyle x<y\) és \(\displaystyle t|y-x\). Az ilyen tulajdonságú pontokra \(\displaystyle 1\leq x\) és \(\displaystyle t+1\leq y\) teljesül, így az origótól vett távolságuk négyzetére

\(\displaystyle x^2+y^2\geq 1+(t+1)^2=t^2+2t+2,\)

ahol egyenlőség pontosan akkor áll fenn, ha \(\displaystyle (x;y)=(1;t+1)\). Most megmutatjuk, hogy az \(\displaystyle (1;t+1)\) pont piros színű lesz. Először belátjuk, hogy lesz olyan piros színű \(\displaystyle (1;c)\) pont, amelyre \(\displaystyle c-1\) legnagyobb páratlan osztója \(\displaystyle t\). Legyen \(\displaystyle d\) a legkisebb olyan pozitív egész szám, amelyre lesz olyan piros \(\displaystyle (d;e)\) pont, amelyre \(\displaystyle e-d\) legnagyobb páratlan osztója \(\displaystyle t\). (Ilyen \(\displaystyle d\) nyilvánvalóan létezik, és értéke legfeljebb \(\displaystyle a\).) Ha \(\displaystyle d\) és \(\displaystyle e\) is párosak, akkor \(\displaystyle (d/2;e/2)\) szintén piros lenne, ami ellentmondana \(\displaystyle d\) minimalitásának. Ha \(\displaystyle 1<d\) és \(\displaystyle e\) is páratlanok, akkor \(\displaystyle (d+1;e+1)\), és így \(\displaystyle ((d+1)/2;(e+1)/2)\) szintén pirosak, ami \(\displaystyle (d+1)/2<d\) miatt ellentmondana \(\displaystyle d\) minimalitásának. Ha \(\displaystyle d\) páros, és \(\displaystyle e\) páratlan, akkor \(\displaystyle (d+1;e+1),(d+2;e+2),\dots,(e;2e-d)\) mind pirosak, így \(\displaystyle (d;e)\) és \(\displaystyle (e;2e-d)\) pirossága miatt \(\displaystyle (d;2e-d)\), és így \(\displaystyle (d/2,e-d/2)\) is az, ami ismét ellentmond \(\displaystyle d\) minimalitásának. Ha \(\displaystyle 1<d\) páratlan és \(\displaystyle e\) páros, akkor \(\displaystyle (d+1;e+1),(d+2;e+2),\dots,(e+1;2e-d+1)\) mind pirosak, és így az előzőekhez hasonlóan \(\displaystyle (d+1;2e-d+1)\), és ezért \(\displaystyle ((d+1)/2;e-(d-1)/2)\) is az, ami ellentmond \(\displaystyle d\) minimalitásának. Mindez azt jelenti, hogy csak \(\displaystyle d=1\) lehetséges. Van tehát \(\displaystyle (1;2^\alpha t+1)\) alakú piros pont. De ekkor \(\displaystyle (2;2^\alpha t+2)\), és így \(\displaystyle (1;2^{\alpha-1}t+1)\) szintén piros. Ezeket a lépéseket ismételgetve azt kapjuk, hogy \(\displaystyle (1;t+1)\) is piros.

Az eddigiek alapján az origóhoz legközelebbi piros pont \(\displaystyle (1;t+1)\), melynek origótól vett távolsága \(\displaystyle \sqrt{t^2+2t+2}\), ahol \(\displaystyle t\) a \(\displaystyle b-a\) szám legnagyobb páratlan osztója. Az \(\displaystyle a>b\) esetben ehhez teljesen hasonlóan kapjuk, hogy az origóhoz legközelebbi piros pont \(\displaystyle (t+1;1)\), melynek origótól vett távolsága \(\displaystyle \sqrt{t^2+2t+2}\), ahol \(\displaystyle t\) az \(\displaystyle a-b\) szám legnagyobb páratlan osztója.

Statistics:

105 students sent a solution.
5 points:	Alexy Milán, Baran Zsuzsanna, Beke Csongor, Bindics Boldizsár, Borbényi Márton, Busa 423 Máté, Daróczi Sándor, Deák Bence, Dobák Dániel, Döbröntei Dávid Bence, Egri Máté, Fajszi Bulcsú, Fülöp Anna Tácia, Gáspár Attila, Gergely Patrik, Győrffy Ágoston, Imolay András, Jánosik Áron, Janzer Orsolya Lili, Jedlovszky Pál, Kálóczi Kristóf, Kerekes Anna, Klász Viktória, Kocsis Júlia, Kovács 246 Benedek, Kővári Péter Viktor, Kuchár Zsolt, Lakatos Ádám, Marshall Tamás, Matolcsi Dávid, Molnár-Sáska Zoltán, Móricz Benedek, Nagy Dávid Paszkál, Nagy Nándor, Németh 123 Balázs, Noszály Áron, Pap Benedek, Schrettner Jakab, Simon Dániel Gábor, Surján Anett, Szabó Kristóf, Szemerédi Levente, Tiszay Ádám, Tóth 827 Balázs, Vankó Miléna, Vári-Kakas Andor, Weisz Máté, Záhorský Ákos, Zólomy Kristóf, Zsigri Bálint.
4 points:	15 students.
3 points:	6 students.
2 points:	5 students.
1 point:	20 students.
0 point:	9 students.

Problems in Mathematics of KöMaL, September 2016