Az A. 900. feladat (2025. február)

A. 900. Egy teremben $\displaystyle n$ lámpa az $\displaystyle 1$, $\displaystyle 2$, $\displaystyle \ldots$, $\displaystyle n$ számokkal van megszámozva. A játék elején ki lehet jelölni az $\displaystyle \{1,2,\ldots,n\}$ halmaz $\displaystyle k$ darab $\displaystyle S_1$, $\displaystyle S_2$, $\displaystyle \ldots$, $\displaystyle S_k$ részhalmazát. Minden $\displaystyle 1\leq i\leq k$ egész számhoz tartozik egy felkapcsoló és egy lekapcsoló gomb, amellyel az $\displaystyle S_i$ halmaz elemeihez tartozó lámpákat lehet fel-, illetve lekapcsolni. Tetszőleges $\displaystyle n$ pozitív egész szám esetén határozzuk meg a legkisebb $\displaystyle k$-t, amelyre meg lehet választani úgy az $\displaystyle S_1$, $\displaystyle S_2$, $\displaystyle \ldots$, $\displaystyle S_k$ halmazokat, hogy a lámpák teljesen lekapcsolt állapotából tetszőleges állapotba el lehessen jutni a kapcsolók segítségével.

Javasolta: Zólomy Kristóf (Budapest)

(7 pont)

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

Világos, hogy $\displaystyle k=n$ elég, ugyanis ha minden lámpához külön rendelünk egy egyelemű $\displaystyle S_i$ halmazt, akkor tetszőleges állapotba el lehet jutni. Azt fogjuk megmutatni, hogy $\displaystyle k<n$ esetén sosem léteznek megfelelő halmazok. Ez a következő lemmán múlik.

Lemma: Ha $\displaystyle k<n$, akkor a $\displaystyle H=\{1,2, \ldots , n\}$ halmaz tetszőleges $\displaystyle S_1, S_2, \ldots , S_k$ részhalmazai esetén léteznek $\displaystyle A, B \subseteq H$ nemüres diszjunkt halmazok, melyekre teljesül, hogy $\displaystyle S_i$ vagy mindkettőt metszi, vagy egyiket sem minden $\displaystyle 1 \leq i \leq k$ esetén.

A lemma állítása segítségével már nem nehéz befejezni a feladatot. Azt állítjuk, hogy azt az állapotot, amikor pontosan a lemma által adott $\displaystyle A$ halmazhoz tartozó lámpák égnek nem lehet elérni. Indirekten tegyük fel, hogy mégis, vegyünk egy ilyen kapcsolás sorozatot, és tekintsük azt a pillanatot, amikor utoljára használunk olyan kapcsolót, melyre $\displaystyle S_i \cap A \neq \emptyset$. A lemma szerint ez egyben az utolsó pillanat, amikor $\displaystyle B$-beli lámpát kapcsolunk. Így amennyiben ebben a lépésben feloltunk lámpákat, akkor a végén fognak világítani $\displaystyle B$-beli lámpák, ha pedig leoltunk lámpákat, akkor lesznek $\displaystyle A$-beli lámpák, amik nem világítanak, tehát mindenképpen ellentmondásra jutunk azzal, hogy végül pontosan az $\displaystyle A$-beli lámpák égnek.

Így már csak a lemma állítását kell megmutatnunk, amelyre két különböző bizonyítást is adunk, egy kombinatorikusat, és egyet lineáris algebra segítségével.

A lemma 1. bizonyítása:

Indirekten tegyük fel, hogy nem igaz az állítás, és legyen $\displaystyle n$ a legkisebb szám, melyre vannak olyan $\displaystyle S_1, S_2, \ldots , S_k$ halmazok, melyek ellentmondanak a lemma állításának.

Tegyük fel, hogy van olyan $\displaystyle I \subseteq \{1,2, \ldots , k\}$ nemüres indexhalmaz, melyre $\displaystyle \left| \bigcup_{i \in I} S_i \right| \leq |I|$. Ekkor az $\displaystyle H'=H \setminus \bigcup_{i \in I} S_i$ halmazt csak a $\displaystyle J=\{1,2, \ldots , k\} \setminus I$ indexű kapcsolók tudják kapcsolni, ami a feltevésünk szerint kevesebb kapcsoló, mint $\displaystyle H'$ mérete. Tehát csak $\displaystyle H'$-re figyelve, minden állapot elérhető $\displaystyle J$-beli indexű kapcsolókkal, azaz ezeket a kapcsolókat $\displaystyle H'$-re megszorítva egy kisebb ellenpéldát kapnánk a lemma állítására, ami ellentmond a minimalitási feltételünknek.

Mostantól feltesszük, hogy tetszőleges nemüres $\displaystyle I \subseteq \{1,2, \ldots , k\}$ esetén $\displaystyle \left| \bigcup_{i \in I} S_i \right| >|I|$. A következő állítás a kulcs:

Állítás: Ekkor ki tudunk választani $\displaystyle x_i, y_i \in S_i$ elemeket minden $\displaystyle 1 \leq i \leq k$ esetén, hogy a $\displaystyle H$ csúcshalmazon definiált gráf, melyben pontosan az $\displaystyle x_iy_i$ élek vannak behúzva, körmentes.

Bizonyítsuk be ezt az állítást. A Hall-tétel szerint legalább azt tudjuk, hogy ki tudunk választani $\displaystyle x_i \in S_i$ elemeket úgy, hogy $\displaystyle x_i \neq x_j$ ha $\displaystyle i \neq j$. Legyen $\displaystyle R$ azon $\displaystyle H$-beli elemek halmaza, akiket egyik halmazhoz sem rendeltünk (ilyen van, mert $\displaystyle k<n$). Tekintsük azt a irányított gráfot a $\displaystyle H \cup \{r\}$ csúcshalmazon (ahol $\displaystyle r$ egy újonnan bevezetett csúcs), melyben $\displaystyle a,b \in H$ pontosan akkor van egy irányított éllel összekötve, ha vagy $\displaystyle b=x_i$, és $\displaystyle a \in S_i$ valamelyik $\displaystyle i$-re, vagy $\displaystyle a=r$ és $\displaystyle b \in R$.

Legyen $\displaystyle Z$ azon csúcsok halmaza, amelyek nem érhetőek el $\displaystyle r$-ből irányított úton. Ha $\displaystyle Z$ üres, akkor $\displaystyle r$-ből egy mélységi keresés segítségével tudunk építeni egy $\displaystyle r$ gyökerű $\displaystyle F$ feszítőfenyőt, azaz egy olyan részgráfot, melyben $\displaystyle r$ kivételével minden csúcsnak pontosan 1 a befoka, és amely egy fa, az irányítást elfelejtve. Ekkor $\displaystyle F$-ben azon élek, melyeknek végpontja nem $\displaystyle R$-beli (máshogy mondva, törölve $\displaystyle F$-ből az $\displaystyle r$ csúcsot és a rá illeszkedő éleket) olyan élhalmazt alkotnak, mely bizonyítja az állítást, ha elhagyjuk az élek irányítását.

Ha $\displaystyle Z$ nemüres, akkor minden $\displaystyle x_i \in Z$ csúcs esetén $\displaystyle S_i \subseteq Z$, mert ha lenne olyan pontja, amibe el tudunk jutni $\displaystyle r$-ből, akkor onnan vezetne $\displaystyle x_i$-be él. Emiatt viszont a $\displaystyle Z$ csúcshalmaz teljesen tartalmaz legalább $\displaystyle |Z|$ darab $\displaystyle S_i$ halmazt, ami ellentmond a feltevésünknek.

Már csak azt kell megmutatnunk, hogy az állításból következik a lemma állítása. Mivel minden körmentes gráf páros, így meg tudjuk színezni az állítás alapján kapott $\displaystyle x_iy_i$ éleket két színnel úgy, hogy $\displaystyle x_i$ és $\displaystyle y_i$ különböző színű minden $\displaystyle i$-re. Legyen az egyik színosztály az $\displaystyle A$ halmaz, a másik a $\displaystyle B$. Világos, hogy ezek teljesítik a lemma feltételeit.

A lemma 2. bizonyítása:

Legyenek $\displaystyle x_1, x_2, \ldots , x_n$ változók, és tekintsük a $\displaystyle \sum_{j\in S_i}x_j=0$, $\displaystyle 1\leq i\leq k$ egyenletrendszert. Ez kevesebb egyenletből áll, mint ismeretlenből, és az $\displaystyle x_i=0$ minden $\displaystyle 1 \leq i \leq n$ esetén megoldása, így lineáris algebrából ismert, hogy ekkor az egyenletrendszernek végtelen sok megoldása van, azaz van olyan $\displaystyle a_1, a_2, \ldots , a_n$ megoldása, melyben nem minden szám 0. Azt állítjuk, hogy az $\displaystyle A=\{i:a_i> 0\}$ és a $\displaystyle B=\{i:a_i< 0\}$ halmazok kielégítik a lemma feltételeit. Ugyanis $\displaystyle \sum_{j\in S_i}a_j=0$, azaz az $\displaystyle S_i$-hez tartozó $\displaystyle a_j$ értékek között pontosan akkor van pozitív, ha negatív is van, és éppen ezt akartuk megmutatni.

Statisztika:

12 dolgozat érkezett.
7 pontot kapott:	Czanik Pál, Keresztély Zsófia, Kocsis 827 Péter, Szakács Ábel, Varga Boldizsár.
6 pontot kapott:	Morvai Várkony Albert, Virág Tóbiás.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	1 versenyző.
0 pontot kapott:	3 versenyző.

A KöMaL 2025. februári matematika feladatai