Az A. 888. feladat (2024. október)

A. 888. Legyen $\displaystyle n$ egy rögzített pozitív egész szám. Határozzuk meg a legkisebb $\displaystyle k$ pozitív egész számot, melyre teljesül a következő állítás: tetszőleges $\displaystyle G$ egyszerű, összefüggő gráf és $\displaystyle V_1$, $\displaystyle V_2$, $\displaystyle \ldots$, $\displaystyle V_n$ minimális vágások esetén legfeljebb $\displaystyle k$ csúcs választható ki úgy, hogy bármely két kiválasztott csúcshoz létezzen egy $\displaystyle 1 \leq i \leq n$ egész szám, melyre a két kiválaszott csúcsot elválasztja $\displaystyle V_i$.

A gráf $\displaystyle V$ csúcshalmazának két diszjunkt nemüres részre való bontását minimális vágásnak nevezzük, ha a két rész között haladó élek száma minimális.

Javasolta: Imolay András (Budapest)

(7 pont)

A beküldési határidő 2024. november 11-én LEJÁRT.

Azt állítjuk, hogy $\displaystyle k=2n$. Erre egy jó példa egy $\displaystyle 2n$ csúcsból álló kör. Legyenek a csúcsai sorban $\displaystyle v_1, v_2, \ldots , v_{2n}$, és legyenek a vágások $\displaystyle V_i=\{v_i, v_{i+1}, \ldots , v_{i+n-1}\}$ minden $\displaystyle 1 \leq i \leq n$ esetén. Először is figyeljük meg, hogy ezek tényleg minimális vágások, ugyanis mindegyik $\displaystyle V_i$-ből pontosan két él lép ki, és nincs a csúcsoknak olyan részhalmaza, amiből csak egy él lép ki (azaz nincs hídél). Továbbá gondoljuk meg, hogy itt ki lehet választani az összes csúcsot, azaz bármelyik csúcspárhoz van olyan $\displaystyle V_i$, ami pontosan egyet tartalmaz közülük. Valóban, tetszőleges két csúcsot választva legalább $\displaystyle n-1$ csúcs van köztük a kör egyik ívén, és ekkor jó vágás lesz az, ahol az egyik rész az egyik csúcsot és a következő $\displaystyle n-1$ csúcsot tartalmazza a legalább $\displaystyle n-1$ csúcsból álló ívről.

Most térjünk rá annak a bizonyítására, hogy miért nem lehet $\displaystyle k>2n$. Legyen $\displaystyle G=(V,E)$ tetszőleges gráf, és legyenek $\displaystyle V_1, V_2, \ldots , V_n$ minimális vágások. Minden $\displaystyle v$ csúcshoz rendeljük hozzá egy kódot, ami egy $\displaystyle n$-hosszú $\displaystyle 0-1$ sorozat, melynek az $\displaystyle i.$ jegye pontosan akkor $\displaystyle 1$, ha $\displaystyle v \in V_i$. Figyeljük meg, hogy két csúcshoz pontosan akkor van olyan $\displaystyle V_i$, ami pontosan az egyiküket tartalmazza, ha a hozzájuk rendelt kód különböző. Azaz azt kell bizonyítanunk, hogy a csúcsokhoz rendelt kódok között legfeljebb $\displaystyle 2n$ darab különböző van.

Nevezzünk egy kódot párosnak, ha páros sok 1-es szerepel benne, különben páratlannak. Minden $\displaystyle x$ kódhoz legyen $\displaystyle V_x$ azon csúcsok halmaza, akikhez az $\displaystyle x$ kódot rendeltük. Tetszőleges $\displaystyle S$ vágásra $\displaystyle d(S)$ jelölje azt, hogy hány él megy a vágás két része között. A bizonyítás kulcsa a következő lemma.

Lemma.

$\displaystyle \sum_{i=1}^n d(V_i) \geq \sum_{x \text{ páros}} d(V_x) \quad \text{ és } \quad \sum_{i=1}^n d(V_i) \geq \sum_{x \text{ páratlan}} d(V_x).$

Bizonyítás: Csak az első egyenlőtlenséget bizonyítjuk, a másik ugyanúgy megy. Az egyenlőtlenség mindkét oldala éleket számol le, egy élet leszámolhat akár többször is. Azt fogjuk megmutatni, hogy a bal oldal minden élet legalább annyiszor megszámol, mint a jobb oldal. Legyen $\displaystyle e \in E$ tetszőleges él, és legyen $\displaystyle x$ és $\displaystyle y$ a két végpontjának a kódja. Ezek szerint a kódok szerint esetekre bontunk.

• Ha $\displaystyle x$ és $\displaystyle y$ is páratlan, akkor a jobb oldalon egyszer sem számoljuk meg $\displaystyle e$-t, így igaz az állítás.
• Ha $\displaystyle x \neq y$ és $\displaystyle x$ és $\displaystyle y$ közül pontosan egy páros, akkor a jobb oldalon egyszer számoljuk meg $\displaystyle e$-t, és a bal oldalon is megszámoljuk legalább egyszer, mert különböző $\displaystyle e$ végpontjainak a kódja, és így legalább egy vágás elválasztja őket egymástól.
• Végül ha $\displaystyle x$ és $\displaystyle y$ is páros, akkor $\displaystyle x=y$ esetén egyik oldalon sem számoljuk meg őket, ha pedig $\displaystyle x\neq y$, akkor a jobb oldalon kétszer számoljuk meg $\displaystyle e$-t, de a bal oldalon is legalább ennyiszer, mert $\displaystyle x$ és $\displaystyle y$ kódja legalább két helyen eltér egymástól, és az ezekhez a helyekhez tartozó vágások elválasztják $\displaystyle e$ végpontjait egymástól.

A lemmát használva már nem nehéz befejezni a bizonyítást. Mivel a $\displaystyle V_i$ vágások minimálisak, és pozitív az értékük (mert $\displaystyle G$ összefüggő), így az mindkét egyenlőtlenség jobb oldalán legfeljebb $\displaystyle n$ darab nemnulla összeadandó szerepelhet. Azonban ha $\displaystyle d(V_x)=0$, akkor a csúcsokat az üres halmazra és $\displaystyle V$-re választottuk szét, és ekkor vagy egyik csúcsnak sem $\displaystyle x$ a kódja, vagy mindegyiknek $\displaystyle x$ a kódja, és az utóbbi lehetetlen, mert $\displaystyle G$ összefüggő. Ekkor tehát a legfeljebb $\displaystyle n$ különböző páros kód tartozik a csúcsokhoz, és ugyanígy, páratlan kódból sem lehet több, mint $\displaystyle n$-féle rendelve a csúcsokhoz, és ezzel a bizonyítást befejeztük.

Statisztika:

12 dolgozat érkezett.
7 pontot kapott:	Aravin Peter, Bodor Mátyás, Czanik Pál, Holló Martin, Varga Boldizsár.
6 pontot kapott:	Szakács Ábel.
5 pontot kapott:	1 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	3 versenyző.

A KöMaL 2024. októberi matematika feladatai