Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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:

A B. 4992. feladat értékelése még nem fejeződött be.


A KöMaL 2018. decemberi matematika feladatai