Problem B. 5253. (May 2022)

B. 5253. Is it true that if \(\displaystyle \binom{n}{k}\) is even, then the \(\displaystyle k\)-element subsets of an \(\displaystyle n\)-element set \(\displaystyle S\) can be paired up so that the symmetric difference of every pair should have exactly 2 elements?

(6 pont)

Deadline expired on June 10, 2022.

Sorry, the solution is available only in Hungarian. Google translation

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.

Statistics:

23 students sent a solution.
6 points:	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 points:	Virág Rudolf, Zömbik Barnabás.
4 points:	1 student.
1 point:	3 students.

Problems in Mathematics of KöMaL, May 2022