A B. 4992. feladat (2018. december)

B. 4992. Az \(\displaystyle 1,2,\ldots, n\) számok mindegyikét pirosra vagy kékre színezzük. Egy lépés azt jelenti, hogy kiválasztunk három különböző számot, amelyek számtani sorozatot alkotnak, és mindhárom szám színét a másik színre változtatjuk. Mely \(\displaystyle n\)-ekre lehet az \(\displaystyle 1,2,\ldots, n\) számok tetszőleges színezéséből kiindulva elérni, hogy mindegyik szám piros legyen?

Javasolta: Róka Sándor (Nyíregyháza)

(4 pont)

A beküldési határidő 2019. január 10-én LEJÁRT.

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.

Statisztika:

50 dolgozat érkezett.
4 pontot kapott:	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 pontot kapott:	Baski Bence, Beke Csongor, Bukva Dávid, Markó Gábor, Rareș Polenciuc, Telek Zsigmond , Tiderenczl Dániel, Török Mátyás.
2 pontot kapott:	5 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	5 versenyző.

A KöMaL 2018. decemberi matematika feladatai