Az A. 819. feladat (2022. február)

A. 819. Legyen \(\displaystyle G\) egy tetszőlegesen választott véges egyszerű gráf. A gráf csúcsaira olyan módon írunk nemnegatív egész számokat, hogy minden csúcson az a szám szerepeljen, ahány olyan szomszédja van az adott csúcsnak, melyre páros számot írtunk. Bizonyítsuk be, hogy az ilyen kitöltések száma kettőhatvány.

Javasolta: Imolay András (Budapest)

(7 pont)

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

1. Megoldás: Tekintsük a következő feladatot. A \(\displaystyle G\) gráf minden csúcsán van egy lámpa és egy kapcsoló. Ha megnyomjuk valamelyik kapcsolót, akkor állapotot vált (ha fel volt kapcsolva akkor le, ha le volt kapcsolva akkor felkapcsolódik) az összes lámpa, ami vagy ugyanazon a csúcson van, mint a kapcsoló, vagy valamelyik szomszédos csúcson. A kérdés az, hogy ha kezdetben minden lámpa le van kapcsolva, akkor hányféleképpen tudunk megnyomni néhány kapcsolót (mindet legfeljebb egyszer) úgy, hogy a végén minden lámpa fel legyen kapcsolva. Itt két kapcsolást nem tekintünk különbözőnek, ha ugyanazokat a kapcsolókat nyomjuk meg, csak más sorrendben, mivel könnyű meggondolni, hogy a sorrend nem számít, csak az, hogy melyik részhalmazt nyomjuk meg. Világos, hogy az eredeti feladat állítása ekvivalens azzal, hogy ennek a feladatnak kettőhatvány számú megoldása van, mivel ha van egy jó kapcsolás, akkor írjuk minden csúcsra azt a számot, hogy hány szomszédja van, ahol használtuk a kapcsolót, míg ha az eredeti feladatnak van egy megoldása, akkor azzal meg tudjuk oldani úgy a kapcsolós feladatot, hogy pontosan azokhoz a csúcsokhoz tartozó kapcsolókat nyomjuk meg, melyekre páros számot írtunk. Világos, hogy ez egy bijekció a két feladat megoldásai között, így elég a lámpás feladatot megoldani.

Először bizonyítjuk, hogy ha van megoldás, akkor kettőhatvány számú. Nevezzük a lámpák egy állapotát (azaz mindről meg van mondva, hogy fel vagy le van kapcsolva) elérhetőnek, ha van olyan kapcsolás sorozat, amivel megkapjuk ezt az állapotot a csupa lekapcsolt állapotból. A kulcs észrevétel az, hogy ha két állapot elérhető, akkor pontosan ugyanannyiféleképpen érhetők el. Lássuk ezt be:

Mostantól a nagybetűk mindig kapcsolók egy részhalmazát jelölik, és ha azt mondjuk, hogy megnyomjuk \(\displaystyle A\)-t, akkor azt értjük, hogy megnyomjuk az összes kapcsolót, amely az \(\displaystyle A\) részhalmazba esik. Ha azt mondjuk, hogy megnyomjuk \(\displaystyle A+B\)-t, az azt jelenti, hogy, megnyomjuk azokat, amik \(\displaystyle A\) és \(\displaystyle B\) közül pontosan egyben vannak benne. Azért így definiáljuk, mert ez ugyanaz, mintha megnyomnánk \(\displaystyle A\)-t, majd megnyomnánk \(\displaystyle B\)-t. Ehhez azt kell látni, hogy egyrészt, mint már korábban is állítottuk, a nyomások sorrendje nem számít, másrészt, ha egy kapcsolót megnyomunk kétszer, az olyan, mintha egyszer sem nyomtuk volna meg.

Tegyük fel, hogy van egy (nem csupa lekapcsolt) állapot amit el lehet érni, és az összes lehetséges nyomás, amivel odajutunk, az \(\displaystyle A_1, A_2, \ldots A_n\). Figyeljük meg, hogy ekkor az \(\displaystyle A_1+A_1\), \(\displaystyle A_1+A_2, \ldots , A_1+A_n\) mind különböző nyomások, és mind a csupa lekapcsolt állapotot adják, így a csupa lekapcsolt állapotot legalább \(\displaystyle n\)-féleképpen megkaphatjuk. Megfordítva, ha \(\displaystyle B_1, B_2, \ldots , B_k\) azon nyomások, amik a csupa lekapcsoltat adják, akkor \(\displaystyle A_1+B_i\) minden \(\displaystyle i\)-re különböző részhalmaz megnyomása, ami mindig a vizsgált állapotot adja, így \(\displaystyle n \geq k\) is teljesül, tehát ugyanannyi lehetőség van a csupa lekapcsoltba eljutni, mint egy tetszőleges állapotba, és ez minden elérhető állapotra igaz. Összesen \(\displaystyle 2^n\) nyomás lehetőség van, ahol \(\displaystyle n\) a \(\displaystyle G\) csúcsainak száma, és minden elérhető állapotot ugyanannyiféleképpen lehet megkapni, így ha elérhető, hogy minden lámpa világítson, akkor \(\displaystyle 2^n\) osztója, hogy hányféleképpen, azaz kettőhatvány.

Már csak azt kell igazolnunk, hogy minden \(\displaystyle G\) gráfra el tudjuk érni, hogy minden lámpát felkapcsoljunk. Ehhez szükségünk lesz az alábbi ismert feladatra: Minden \(\displaystyle H\) gráfnak két részre, \(\displaystyle V_1\)-re és \(\displaystyle V_2\)-re lehet osztani a csúcsait úgy, hogy a \(\displaystyle V_1\) által feszített részgráf minden csúcsa páros fokú legyen, és hasonlóan a \(\displaystyle V_2\) által feszített részgráfnak is minden foka páros legyen. Ennek a bizonyítását csak vázlatosan írjuk le:

Csúcsszám szerinti indukcióval bizonyítunk, a kezdőlépés \(\displaystyle 1,2,3\) csúcsú gráfokra egyszerű. Adott az \(\displaystyle n\) csúcsú \(\displaystyle G\) gráf. Ha minden csúcsa páros fokú, akkor a \(\displaystyle V_1\) álljon \(\displaystyle G\) összes csúcsából, \(\displaystyle V_2\) pedig legyen üres. Különben legyen \(\displaystyle v\) egy páratlan fokú csúcs. Tekintsük azt a \(\displaystyle G'\) gráfot, amit úgy kapunk, hogy a \(\displaystyle v\) csúcsot elhagyjuk, és megcseréljük az éleket a \(\displaystyle v\) szomszédain, azaz ha \(\displaystyle u\) és \(\displaystyle w\) is a \(\displaystyle v\) szomszédai, akkor \(\displaystyle G'\)-ben pontosan akkor lesz él \(\displaystyle uw\), ha \(\displaystyle G\)-ben nem volt. A többi élt nem változtatjuk, ugyanazok \(\displaystyle G'\)-ben, mint \(\displaystyle G\)-ben. \(\displaystyle G'\) kevesebb csúcsú, mint \(\displaystyle G\), így az indukciós feltevés szerint erre igaz az állítás, felvágható \(\displaystyle V_1\) és \(\displaystyle V_2\) részekre a csúcshalmaza. Mivel \(\displaystyle v\)-nek páratlan sok szomszédja van, így vagy \(\displaystyle V_1\) vagy \(\displaystyle V_2\) páros sok helyen metszi \(\displaystyle v\) szomszédságát. Ehhez a halmazhoz rakjuk hozzá \(\displaystyle v\)-t, így kapva a \(\displaystyle G\) gráf csúcshalmazának egy két részre osztását. Nem nehéz ellenőrizni, hogy ez megfelelő lesz. Ezzel az állítást igazoltuk, most ennek a segítségével belátjuk, hogy mindig fel tudjuk kapcsolni az összes lámpát.

Vegyünk fel egy új csúcsot, legyen ez \(\displaystyle u\), és kössük össze \(\displaystyle G\) összes páros fokú csúcsával. Így kaptunk egy \(\displaystyle G'\) gráfot, amiben \(\displaystyle u\)-n kívül biztosan minden csúcs foka páratlan. A \(\displaystyle G'\) gráfra alkalmazzuk a most bizonyított állítást, így kapunk egy \(\displaystyle V_1\), \(\displaystyle V_2\) felosztását a csúcsoknak. Feltehetjük, hogy \(\displaystyle V_2\)-ben van az \(\displaystyle u\) csúcs. Azt állítjuk, hogy ha a \(\displaystyle V_1\)-beli csúcsokat megnyomjuk, akkor minden lámpa felkapcsolódik. Ez azért igaz, mert ha \(\displaystyle w \in V_1\), akkor \(\displaystyle w\) páros fokú a \(\displaystyle V_1\) által feszített részgráfban \(\displaystyle G\)-ben, így páros sok szomszédját nyomjuk meg, illetve őt is, tehát összesen páratlan sokszor vált állapotot, azaz felkapcsolódik. Míg ha \(\displaystyle w \notin V_1\), akkor \(\displaystyle w\) páros fokú a \(\displaystyle G'\) gráf \(\displaystyle V_2\) által feszített részgráfjában. De \(\displaystyle G'\)-ben \(\displaystyle w\) foka páratlan, és páros sok \(\displaystyle V_2\)-beli csúccsal van összekötve, azaz páratlan sok \(\displaystyle V_1\)-beli csúccsal van összekötve, így páratlan sokszor fog a hozzá tartozó lámpa állapotot váltani, azaz felkapcsolódik. A feladat állítását bizonyítottuk.

2. Megoldás: Ha egy csúcson páratlan szám áll, ahhoz \(\displaystyle 0\)-t rendelünk, ha páros, akkor \(\displaystyle 1\)-et (ez a szokásoshoz képest fordított kódolás, de hamarosan világossá válik, miért hasznos).

A csúcsokhoz tartozó kódok már egyértelműen meghatározzák a csúcsokra írt számokat, ugyanis egyszerűen minden csúcsra azt a számot kell írnunk, ahány \(\displaystyle 1\)-es van a szomszédai között.

A kérdés tehát, hogy hányféleképpen írhatunk \(\displaystyle 0\)-kat és \(\displaystyle 1\)-eket a csúcsokra úgy, hogy minden csúcsra igaz, hogy a szomszédos csúcsokra írt számok összege (azaz az \(\displaystyle 1\)-esek száma, azaz a páros szomszédok száma, azaz a csúcsra írt szám) plusz \(\displaystyle 1\) egyenlő a csúcsra írt számmal modulo \(\displaystyle 2\).

Átfogalmazva, hányféleképpen írhatjuk fel a \(\displaystyle 0\) és \(\displaystyle 1\) értékeket a csúcsokra úgy, hogy minden csúcsra igaz, hogy ha összeadjuk a szomszédain és magán a csúcson lévő számokat, akkor mindig \(\displaystyle 1\)-et kapunk modulo \(\displaystyle 2\).

Vesszük a gráf adjacencia mátrixát, azaz az \(\displaystyle n\) csúcsú gráfhoz vesszük azt az \(\displaystyle n\times n\)-es mátrixot, aminek a főátlójában \(\displaystyle 0\)-k állnak, az \(\displaystyle i\)-edik sor \(\displaystyle j\)-edik oszlopában \(\displaystyle 1\) áll, ha a gráf \(\displaystyle i\)-edik és \(\displaystyle j\)-edik csúcsa össze van kötve, és \(\displaystyle 0\) áll különben. Ezt a szokásos adjacencia mátrixot úgy módosítjuk, hogy a főátlóba is \(\displaystyle 1\)-eseket írunk, így kapjuk az \(\displaystyle M\) mátrixot.

Észrevehetjük, hogy a kérdés ekvivalens azzal, hogy hány olyan \(\displaystyle n\) hosszú \(\displaystyle 0-1\) vektor van, aminek koordinátái az egyes csúcsokra írt kódoknak felelnek meg, amire igaz az, hogy ha megszorozzuk \(\displaystyle M\)-mel, akkor a csupa \(\displaystyle 1\) vektort kapjuk modulo \(\displaystyle 2\).

Tegyük föl, hogy létezik egy ilyen \(\displaystyle v\) vektor.

Ekkor \(\displaystyle \mathbb{Z}_2\) fölött (azaz mindent modulo \(\displaystyle 2\) számolva) pontosan azokra a \(\displaystyle w\) vektorokra teljesül, hogy \(\displaystyle Mw\) is a csupa \(\displaystyle 1\) vektor, amikre \(\displaystyle M(w-v)=0\).

Megnézzük, hogy legfeljebb hány egymástól független \(\displaystyle y\) vektor létezik, amire \(\displaystyle My=0\). Legyen ez a szám \(\displaystyle k\).

Ekkor ha a \(\displaystyle k\) független vektor közül néhányat kiválasztunk, és összeadjuk őket, akkor mindig olyan \(\displaystyle z=y_1+...+y_s\) vektort kapunk, amire \(\displaystyle Mz=M(y_1+...+y_s)=My_1+...+My_s=0\).

Az így összegként kapott vektorok ráadásul mind különbözőek, mert ha két különböző összeg ugyanazt a vektort adná, akkor kivonva őket egymásból azt kapnánk, hogy az \(\displaystyle y_1, y_2,...,y_k\) vektoroknak van egy olyan lineáris kombinációja, aminek \(\displaystyle 0\) az értéke, ami ellentmond annak, hogy ez \(\displaystyle k\) független vektor volt.

Tehát ekkor összegként találtunk \(\displaystyle 2^k\) különböző \(\displaystyle z\) vektort, amikre \(\displaystyle Mz=0\). Ezeken kívül pedig nem is létezik más, mert ha létezne még olyan \(\displaystyle z\) vektor, amire \(\displaystyle Mz=0\), de \(\displaystyle z\) nem áll elő néhány \(\displaystyle y_1, ..., y_k\) összegeként, akkor \(\displaystyle z\) is független lenne \(\displaystyle y_1,...,y_k\)-tól, és így nem \(\displaystyle k\) lenne a legtöbb független vektor, ami kiválasztható.

Tehát \(\displaystyle 2^k\) olyan \(\displaystyle z\) vektor létezik, amire \(\displaystyle Mz=0\), azaz \(\displaystyle 2^k\) olyan \(\displaystyle w\) vektor létezik, amire \(\displaystyle M(w-v)=0\), vagyis \(\displaystyle Mw=Mv\) a csupa \(\displaystyle 1\) vektor.

(Ugyanez a bizonyítás egyetemi szóhasználattal: Ha \(\displaystyle Mw=1\) megoldható, akkor a megoldásai egy affin alteret alkotnak, ami az \(\displaystyle Mz=0\) lineáris altér egy eltoltja, ha ez a lineáris altér \(\displaystyle k\) dimenziós, akkor \(\displaystyle 2^k\) eleme van.)

Azt kell még belátnunk, hogy létezik egyáltalán olyan \(\displaystyle v\), amire \(\displaystyle Mv\) a konstans \(\displaystyle 1\) vektor (\(\displaystyle \mathbb{Z}_2\) fölött).

Ismert, hogy ezt pontosan akkor nem lehet megoldani, ha létezik az \(\displaystyle M\) mátrixnak néhány sora, hogy az azok által meghatározott egyenleteket összeadva minden változónak \(\displaystyle 0\) lesz az együtthatója, de az egyenlet jobb oldalán mégsem \(\displaystyle 0\) áll.

(Ez az állítás Fredholm alternatíva tételként ismert.)

Az \(\displaystyle Mv=1\) által meghatározott egyenletek mindegyikének a jobb oldalán \(\displaystyle 1\) áll, így néhány egyenlet összegének akkor áll \(\displaystyle 1\) a jobb oldalán, ha páratlan sok egyenletet adunk össze, tehát akkor nincs megoldása \(\displaystyle Mv=1\)-nek, ha \(\displaystyle M\)-nek kiválasztható páratlan sok sora, amiknek az összege \(\displaystyle 0\).

Tegyük föl, hogy van páratlan sok ilyen sor, és vegyük a gráfnak a hozzájuk tartozó csúcsait. Az ezek által feszített részgráf páratlan csúcsú, így van olyan csúcs, aminek páros sok szomszédja van a részgráfban, különben a fokszámok összege páratlan lenne.

Az ehhez a csúcshoz tartozó koordinátánál páratlan sok \(\displaystyle 1\)-es szerepel a kiválasztott sorokban, mert páros sok szomszédjánál és önmagánál is szerepel egy \(\displaystyle 1\)-es. Tehát a sorok összege nem lehet minden koordinátában \(\displaystyle 0\). Ezzel a bizonyítást befejeztük.

Statisztika:

4 dolgozat érkezett.
7 pontot kapott:	Ben Gillott, Nádor Benedek, Varga Boldizsár.
5 pontot kapott:	1 versenyző.

A KöMaL 2022. februári matematika feladatai