A C. 1844. feladat (2025. február)

C. 1844. Ági pirossal, Laci kékkel színezgeti egy $\displaystyle n \times n$-es ($\displaystyle n>1$) fehér táblázat mezőit, amely $\displaystyle i$-edik sorának $\displaystyle j$-edik mezőjét $\displaystyle (i;j)$-vel jelöljük. Első lépésben Ági pirosra festi a főátló (bal felsőtől a jobb alsóig) mezőit. Ezután felváltva jönnek: ha Laci $\displaystyle (i;j)$-t színezi, akkor Ági $\displaystyle (j;i)$-t. Minden mezőt pontosan egyszer színeznek be. A $\displaystyle k$-adik sort különlegesnek hívjuk, ha bármely kék $\displaystyle (k;j)$ esetén létezik $\displaystyle l$, hogy $\displaystyle (k;l)$ és $\displaystyle (l;j)$ is piros. Bizonyítsuk be, hogy a színezgetés végeztével Ági talál különleges sort.

Javasolta: Paulovics Zoltán, Budapest

(5 pont)

A beküldési határidő 2025. március 10-én LEJÁRT.

Megoldás. A szimmetrikus színezési feltétel miatt – azaz hogy $\displaystyle (i;j)$ és $\displaystyle (j;i)$ közül pontosan az egyik piros – legfeljebb egy csupa piros sor létezik. A csupa piros sor nyilván különleges, hiszen nincs olyan (kék) mezője, melyre teljesülnie kellene a megadott feltételnek. Feltehető tehát, hogy nincs csupa piros sor.

1. ábra. A különlegesség feltétele: bármely kék $\displaystyle (k;j)$ esetén létezzen $\displaystyle l$, hogy $\displaystyle (k;l)$ és $\displaystyle (l;j)$ is piros

Indirekt módon bizonyítunk: tegyük fel, hogy Ági nem talál különleges sort, azaz nincs olyan sor, amelyre bármely kék $\displaystyle (k;j)$ mező esetén létezne $\displaystyle l$, hogy a $\displaystyle (k;l)$ és az $\displaystyle (l;j)$ mezők is pirosak. Tehát bármely $\displaystyle k$ sorra teljesül, hogy létezik olyan $\displaystyle j$, melyre a $\displaystyle (k;j)$ mező kék, és ha valamely $\displaystyle l$-re a $\displaystyle (k;l)$ mező piros, úgy az $\displaystyle (l;j)$ mező kék.

Ha viszont az $\displaystyle (l;j)$ mező kék, úgy – a szimmetrikus színezési szabály miatt – a $\displaystyle (j;l)$ mező piros. Azaz, ha a $\displaystyle (k;l)$ mező piros, vagyis a $\displaystyle k.$ sorban az $\displaystyle l.$ oszlop piros, úgy a $\displaystyle j.$ sorban is piros. Következésképpen a $\displaystyle j.$ sorban legalább annyi piros van, mint a $\displaystyle k.$ sorban. Sőt, több is, hiszen a $\displaystyle (k;j)$ mező kék, míg a $\displaystyle (j;k)$ mező piros. Az indirekt feltétel szerint nincs különleges sor, így tehát bármely sorhoz létezik olyan sor, amelyben több piros mező található, mint benne. Ez nyilvánvalóan ellentmondás.

Statisztika:

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

A KöMaL 2025. februári matematika feladatai