Problem B. 4992. (December 2018)

B. 4992. To start, each of the numbers \(\displaystyle 1,2,\ldots, n\) is coloured either red or blue. In every move, three distinct numbers in arithmetic progression are selected, and the colour of each of the three numbers is changed. For what values of \(\displaystyle n\) is it true that however the numbers \(\displaystyle 1,2,\ldots, n\) are coloured initially, it is possible to turn all of them red by applying an appropriate sequence of such steps?

Proposed by S. Róka, Nyíregyháza

(4 pont)

Deadline expired on January 10, 2019.

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

Megoldás. Megmutatjuk, hogy pontosan akkor érhető el mindig a "csupa-piros" állapot, ha \(\displaystyle n\geq 8\).

Tegyük fel először, hogy \(\displaystyle n\geq 8\). Ha a legnagyobb kék szám – amit jelöljön \(\displaystyle t\) – értéke legalább 3, akkor a \(\displaystyle \{t-2,t-1,t\}\) számokat átszínezve a legnagyobb kék szám értéke csökken. Ilyen lépésekkel tehát elérhető, hogy a legnagyobb kék szám értéke (ha egyáltalán van még kék szám) legfeljebb 2 legyen. Ha ezzel még nem értük el a csupa-piros állapotot, akkor három eset lehetséges az \(\displaystyle 1,2\) számok színe szerint:

1. eset: az \(\displaystyle 1\) piros, a \(\displaystyle 2\) kék

A \(\displaystyle \{2,5,8\},\{5,6,7\},\{6,7,8\}\) hármasokat egymás után átszínezve minden szám színe piros lesz.

2. eset: az \(\displaystyle 1\) kék, a \(\displaystyle 2\) piros

A \(\displaystyle \{1,4,7\},\{4,5,6\},\{5,6,7\}\) hármasokat egymás után átszínezve minden szám színe piros lesz.

3. eset: az \(\displaystyle 1\) és a \(\displaystyle 2\) is kék

Az \(\displaystyle \{1,2,3\},\{1,3,5\},\{1,4,7\},\{2,4,6\},\{2,5,8\}, \{6,7,8\}\) hármasokat egymás után átszínezve minden szám színe piros lesz.

Ezzel megmutattuk, hogy \(\displaystyle n\geq 8\) esetén mindig elérhető a csupa-piros állapot.

Most megvizsgáljuk az \(\displaystyle n\leq 7\) eseteket.

Ha \(\displaystyle n\in\{1,2\}\) és az 1 kék, akkor a csupa-piros állapot nem érhető el, mert nem tudunk átszínezni számokat.

Ha \(\displaystyle n\in\{3,4\}\), akkor csak az \(\displaystyle \{1,2,3\}\) és \(\displaystyle \{2,3,4\}\) hármasok színezhetők át, így ha kezdetben a 2 és a 3 különböző színt kap, akkor ez mindvégig így is marad, a legvégén sem lehetnek egyszínűek.

Ha \(\displaystyle n=5\), akkor az átszínezhető hármasok: \(\displaystyle \{1,2,3\},\{2,3,4\},\{3,4,5\},\{1,3,5\}\). Minden átszínezés 0-val vagy 2-vel változtatja meg az \(\displaystyle \{1,3,4\}\) halmazba eső piros számok számát, hiszen az \(\displaystyle 1,3,4\) számok közül mindig pontosan kettőt színezünk át. Így, ha kezdetben például az 1 kék, a 3 és a 4 pedig piros, akkor a csupa-piros állapot biztosan nem érhető el. (Az \(\displaystyle 1,3,4\) számok között mindig 1 vagy 3 kék szám lesz.)

Ha \(\displaystyle n\in\{6,7\}\), akkor az átszínezhető hármasok: \(\displaystyle n=6\) esetén \(\displaystyle \{1,2,3\},\{2,3,4\},\{3,4,5\},\{4,5,6\},\{1,3,5\},\{2,4,6\}\); \(\displaystyle n=7\) esetén ezeken kívül még: \(\displaystyle \{5,6,7\},\{3,5,7\},\{1,4,7\}\). Minden átszínezés 0-val vagy 2-vel változtatja meg az \(\displaystyle \{2,3,5,6\}\) halmazba eső piros számok számát, hiszen a \(\displaystyle 2,3,5,6\) számok közül mindig páros sokat: nullát vagy kettőt színezünk át. Így, ha kezdetben például a 2 kék, a 3, 5 és a 6 pedig piros, akkor a csupa-piros állapot biztosan nem érhető el. (A \(\displaystyle 2,3,5,6\) számok között mindig 1 vagy 3 kék szám lesz.)

Tehát a csupa-piros állapot \(\displaystyle n\geq 8\) esetén mindig elérhető, \(\displaystyle n\leq 7\) esetén viszont nem mindig.

Statistics:

50 students sent a solution.
4 points:	Argay Zsolt, Bencsik Ádám, Bursics András, Csaplár Viktor, Dobák Dániel, Fraknói Ádám, Füredi Erik Benjámin, Győrffy Ágoston, Hegedűs Dániel, Jánosik Áron, Kerekes Anna, Kocsis Anett, Kovács 129 Tamás, Lovas Márton, Nagy Nándor, Noszály Áron, Nyárfádi Patrik, Pooya Esmaeil Akhoondy, Sebestyén Pál Botond, Seláf Bence, Seres-Szabó Márton, Soós 314 Máté, Stomfai Gergely, Szabó 417 Dávid, Szabó 991 Kornél, Terjék András József, Tóth 827 Balázs, Tóth Ábel, Várkonyi Zsombor, Weisz Máté, Zsigri Bálint.
3 points:	Baski Bence, Beke Csongor, Bukva Dávid, Markó Gábor, Rareș Polenciuc, Telek Zsigmond , Tiderenczl Dániel, Török Mátyás.
2 points:	5 students.
1 point:	1 student.
0 point:	5 students.

Problems in Mathematics of KöMaL, December 2018