A B. 5253. feladat (2022. május)

B. 5253. Igaz-e, hogy ha \(\displaystyle \binom{n}{k}\) páros, akkor az \(\displaystyle n\) elemű \(\displaystyle S\) halmaz \(\displaystyle k\) elemű részhalmazai párokba rendezhetők úgy, hogy az egy párba tartozó részhalmazok szimmetrikus differenciája mindig 2 elemű?

(6 pont)

A beküldési határidő 2022. június 10-én LEJÁRT.

Megoldás. Azt fogjuk megmutatni, hogy igaz.

Tekintsük az \(\displaystyle S\) halmaz \(\displaystyle k\) elemű részhalmazait egy gráf csúcsainak, melyek közül kettőt pontosan akkor köt él össze, ha szimmetrikus differenciájuk 2. Jelölje ezt a gráfot \(\displaystyle G_{S,k}\).

Feltehetjük, hogy \(\displaystyle 1\leq k \leq n-1\), hiszen \(\displaystyle k=0\) és \(\displaystyle k=n\) esetén \(\displaystyle \binom{n}{k}\) páratlan.

Azt igazoljuk, hogy ha \(\displaystyle 1\leq k\leq n-1\), akkor a \(\displaystyle G_{S,k}\) gráf csúcsai párokba és esetleg még egyetlen hármas csoportba oszthatók úgy, hogy az egy párba tartozó csúcsok össze vannak kötve, a hármas pedig egy háromszög. (Hármas csoport pontosan akkor van, ha \(\displaystyle \binom{n}{k}\) páratlan.) Sőt, a hármas a gráf bármely 3 hosszú \(\displaystyle K\) köre lehet.

Ha \(\displaystyle k=1\) vagy \(\displaystyle k=n-1\), akkor bármely két \(\displaystyle k\) elemű részhalmaz szimmetrikus differenciája 2 elemű, így az állítás nyilvánvalóan teljesül (hiszen a gráf teljes és \(\displaystyle \binom{n}{k}\geq 2\)). A továbbiakban feltesszük, hogy \(\displaystyle 2\leq k\leq n-2\).

Ez az észrevétel \(\displaystyle n=2,3\) esetén igazolja az állítást, \(\displaystyle n>3\)-ra indukcióval bizonyítjuk az állítást. Tegyük fel, hogy \(\displaystyle n>3\) és \(\displaystyle (n-1)\)-ig már igazoltuk az állítást.

Három hosszúságú kör kétféle van. Az első típust úgy kapjuk, hogy páronként különböző \(\displaystyle a\), \(\displaystyle b\), \(\displaystyle c\) elemeket hozzáveszünk egy tetszőleges olyan \(\displaystyle T\) részhalmazhoz, amely ezek egyikét sem tartalmazza. Ez \(\displaystyle k\ge 1\) esetén létezik. A második típus \(\displaystyle k\ge 2\) esetén létezik, ekkor az \(\displaystyle \{a,b\}\), \(\displaystyle \{a,c\}\), \(\displaystyle \{b,c\}\) halmazokat bővítjük \(\displaystyle T\)-vel. Ha az összes részhalmaz komplementerére áttérünk, akkor ugyanazt a gráfot kapjuk, de első típusú körből második típusú kör lesz, és viszont. Ezért elegendő a második típusú körökre bizonyítani az állítást.

Megjegyezzük, hogy \(\displaystyle \binom{n}{k}=\binom{n-1}{k-1}+\binom{n}{k}\), négy esetet különböztetünk meg \(\displaystyle \binom{n-1}{k-1}\) és \(\displaystyle \binom{n}{k}\) paritása szerint.

1. eset: \(\displaystyle \binom{n-1}{k-1}\) és \(\displaystyle \binom{n}{k}\) páros (és így \(\displaystyle \binom{n}{k}\) páros).

Az \(\displaystyle S\) halmaz egyik eleme legyen \(\displaystyle s\). Az indukciós feltevés alapján az \(\displaystyle S\setminus\{s\}\) halmaz \(\displaystyle k\) elemű részhalmazai párokba sorolhatók megfelelő módon, hiszen \(\displaystyle \binom{n-1}{k}\) páros. Az \(\displaystyle s\)-et is tartalmazó \(\displaystyle k\) elemű részhalmazok megfelelő párbaállítását pedig úgy kaphatjuk, hogy vesszük az \(\displaystyle S\setminus\{s\}\) halmaz \(\displaystyle k-1\) elemű részhalmazainak egy megfelelő párbaállítását (az indukciós feltevés szerint ilyen van, hiszen \(\displaystyle \binom{n-1}{k-1}\) is páros), és mindegyik halmazhoz hozzávesszük \(\displaystyle s\)-et. Tehát ebben az esetben létezik megfelelő párosítás.

2. eset: \(\displaystyle \binom{n-1}{k-1}\) páros, \(\displaystyle \binom{n-1}{k}\) páratlan (és így \(\displaystyle \binom{n}{k}\) páratlan).

Legyen adott egy második típusú három hosszú \(\displaystyle K\) kör. Ha van olyan \(\displaystyle s\in S\), amely nincs benne \(\displaystyle T\cup\{a,b,c\}\)-ben, akkor eszerint válasszuk szét a csúcsok halmazát az 1. esethez hasonlóan. Mivel \(\displaystyle \binom{n-1}{k-1}\) páros, az \(\displaystyle s\)-et tartalmazó részhalmazok esetében van párosítás. Az \(\displaystyle s\)-et nem tartalmazó részhalmazok között viszont szerepel a három \(\displaystyle K\)-beli részhalmaz. Az indukciós feltevés szerint ezt a három csúcsot elhagyva van párosítás. A két párosítást összerakva a kívánt \(\displaystyle K\)-t tartalmazó csoportokra bontást kapjuk \(\displaystyle K\)-ra és párokra. De ilyen \(\displaystyle s\) mindig van: ha \(\displaystyle T\cup\{a,b,c\}=S\) lenne, akkor \(\displaystyle |T|=n-3\) és \(\displaystyle k=|T|+2=n-1\), amit kizártunk.

3. eset: \(\displaystyle \binom{n-1}{k-1}\) páratlan, \(\displaystyle \binom{n-1}{k}\) páros (és így \(\displaystyle \binom{n}{k}\) páratlan).

Ha van olyan \(\displaystyle s\in S\), amely az adott \(\displaystyle K\) háromszög mindhárom csúcsában benne van, akkor az indukció működik. Ha nincs, akkor a \(\displaystyle T\) halmaz üres. Ekkor tehát \(\displaystyle k=2\). Csináljuk a felbontást az \(\displaystyle s=c\) elem szerint. A \(\displaystyle c\)-t nem tartalmazó halmazok gráfjában van jó párosítás, legyen \(\displaystyle \{a,b\}\) párja \(\displaystyle \{a,d\}\) (ez feltehető, mert \(\displaystyle a\) és \(\displaystyle b\) szerepe szimmetrikus). Nyilván \(\displaystyle d\notin \{a,b,c\}\). A \(\displaystyle c\) elhagyásával kapott halmazok gráfja teljes. Tekintsük ebben az \(\displaystyle \{a\}\), \(\displaystyle \{b\}\), \(\displaystyle \{d\}\) csúcsokból álló háromszöget, és párosítsuk be a maradék csúcsokat tetszőlegesen. Ebből az eredeti esetben az \(\displaystyle \{a, c\}\), \(\displaystyle \{b, c\}\), \(\displaystyle \{d, c\}\) háromszög keletkezik. Végül az \(\displaystyle \{a, c\}-\{d, c\}\), \(\displaystyle \{b, c\}-\{d, c\}\) és \(\displaystyle \{a, b\}-\{a, d\}\) párokat vegyük ki, és húzzuk be helyettük az \(\displaystyle \{a, b\}-\{a, c\}\), \(\displaystyle \{a, b\}-\{b, c\}\) és \(\displaystyle \{a, d\}-\{d, c\}\) éleket. Ekkor egy megfelelő beosztást kapunk.

4. eset: \(\displaystyle \binom{n-1}{k-1}\) páratlan, \(\displaystyle \binom{n-1}{k}\) páratlan (és így \(\displaystyle \binom{n}{k}\) páros).

Legyen \(\displaystyle s\in S\) tetszőleges, és bontsuk a halmazokat eszerint két részre. Vegyünk \(\displaystyle s\)-től és egymástól is különböző \(\displaystyle a,b,c\in S\) elemeket. Legyen \(\displaystyle T\subseteq S\setminus \{a,b,c,s\}\) tetszőleges olyan halmaz, melyre \(\displaystyle |T|=k-2\). Ilyen van, mert \(\displaystyle k\le n-2\). Tekintsük az első típusú \(\displaystyle T\cup \{a\}\), \(\displaystyle T\cup \{b\}\), \(\displaystyle T\cup \{c\}\) kört a \(\displaystyle G_{S\setminus \{s\}, k-1}\) gráfban, ez kiegészíthető egy párosítással megfelelő részgráffá az indukciós feltevés szerint. Hasonlóan, az \(\displaystyle s\)-et nem tartalmazó elemekből álló részgráfban tekintsük a második típusú \(\displaystyle T\cup \{a,b\}\), \(\displaystyle T\cup \{a,c\}\), \(\displaystyle T\cup \{b,c\}\) kört, és ezt is egészítsük ki egy megfelelő párosítással. Ekkor az eredeti gráfban két háromszög keletkezik, és a többi csúcs már be lesz párosítva. Vegyük ki a két háromszög éleit, és helyette tegyük be az \(\displaystyle T\cup\{a,s\}-T\cup\{a,b\}\), \(\displaystyle T\cup\{b,s\}-T\cup\{b,c\}\), \(\displaystyle T\cup\{c,s\}-T\cup\{a,c\}\) éleket, ezzel teljes párosítást kapunk.

Statisztika:

23 dolgozat érkezett.
6 pontot kapott:	Bencsik Dávid, Bényei Borisz, Christ Miranda Anna, Chrobák Gergő, Csonka Illés, Duchon Márton, Fülöp Csilla, Jánosik Máté, Kalocsai Zoltán, Mohay Lili Veronika, Móricz Benjámin, Nádor Artúr, Simon László Bence, Somogyi Dalma, Tarján Bernát, Varga Boldizsár, Wiener Anna.
5 pontot kapott:	Virág Rudolf, Zömbik Barnabás.
4 pontot kapott:	1 versenyző.
1 pontot kapott:	3 versenyző.

A KöMaL 2022. májusi matematika feladatai