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:

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

A KöMaL 2025. februári matematika feladatai