Feladat:	2019. évi Kürschák matematikaverseny 2. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Fleiner Zsigmond ,  Pach Péter Pál ,  Velich Nóra
Füzet:	2020/február, 68 - 70. oldal		PDF  |  MathML
Témakör(ök):	Kürschák József (korábban Eötvös Loránd), Részhalmazok, Számhalmazok
Hivatkozás(ok):	Feladatok: 2020/február: 2019. évi Kürschák matematikaverseny 2. feladata

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   I. megoldás. Számoljuk meg kétféleképpen, hogy hány olyan $\left(A\mathrm{,}B\mathrm{,}C\right)$ rendezett hármas van, melyre $A$ és $B$ az $\text{F}$ halmazrendszer két különböző eleme, $C\subseteq \left\{\mathrm{1,2,}\text{...}\mathrm{,}n\right\}$ pedig egy olyan nemüres részhalmaz, melyre az $A\cap C$ és $B\cap C$ halmazok elemszámának paritása különbözik. $\left(*\right)$ Először is megjegyezzük, hogy bármely (véges) nemüres $S$ halmaz részhalmazainak pontosan a fele páros, illetve páratlan méretű. Sőt, általánosabban, ha $T\supseteq S$ egy (véges) halmaz, akkor $T$ részhalmazainak éppen a fele metszi (a nemüres) $S$-et páros, illetve páratlan elemszámú halmazban (hiszen $S$ minden részhalmaza ugyanannyiféleképpen, $2^{|T\setminus S|}$-féleképpen, egészíthető ki $T$ részhalmazává). Ezt az észrevételt a megoldás során többször is fel fogjuk használni. Legyen $|\text{F}|=t$. Először $A$ és $B$ megválasztásával kezdjük: $A$-ra $t$ lehetőség van, ezután $B$-re $\left(t-1\right)$, hiszen $A\ne B\in \text{F}$. Ezután pontosan azok a $C$ nemüres halmazok megfelelők, melyek az $A\Delta B$ (nemüres) halmazt (vagyis $A$ és $B$ szimmetrikus differenciáját) páratlan sok elemben metszik. Ezt a feltételt $\left(*\right)$ alapján a részhalmazok fele teljesíti (és nincs köztük az $\varnothing$), így a megfelelő $C$ halmazok száma $2^{n-1}$. Tehát a megfelelő $\left(A\mathrm{,}B\mathrm{,}C\right)$ hármasok száma $t\left(t-1\right)2^{n-1}$. Most ugyanezt másféleképpen is megszámoljuk: először $C$-t választjuk meg, erre ($2^n-1$)-féle lehetőség van. Ezután az olyan $\left(A\mathrm{,}B\right)$ párok lesznek megfelelők, melyekre $|A\cap C|$ és $|B\cap C|$ paritása különböző. Az $A\in \text{F}$ halmaz tetszőlegesen megválasztható, majd ezután a feltétel szerint éppen $t/2$ esetben lesz $|B\cap C|$ paritása megfelelő (vagyis $|A\cap C|$ paritásától különböző). Így a hármasok száma $\left(2^n-1\right)t\left(t/2\right)$. A $t\left(t-1\right)2^{n-1}=\left(2^n-1\right)t\left(t/2\right)$ ($t$-ben másodfokú) egyenlet megoldásai $t=0$ és $t=2^n$. Tehát az üres halmazon és az összes részhalmazt tartalmazó halmazrendszeren kívül nincs megfelelő $\text{F}$. Ez a két halmazrendszer pedig teljesíti a feltételeket: ha $\text{F}$ az üres halmazrendszer, akkor $A\cap X$ elemszáma 0-szor lesz páros, 0-szor lesz páratlan; ha pedig $\text{F}$ az összes részhalmazt tartalmazó halmazrendszer, akkor $\left(*\right)$ szerint bármely nemüres $X$-re $A\cap X$ elemszáma $2^{n-1}$ esetben páros, $2^{n-1}$ esetben páratlan. Tehát két megfelelő halmazrendszer van: az üres halmaz és az $\left\{\mathrm{1,2,}\text{...}\mathrm{,}n\right\}$ összes részhalmazát tartalmazó halmazrendszer.     II. megoldás (Fleiner Zsigmond és Velich Nóra megoldása alapján). Megmutatjuk, hogy csak az üres halmazrendszer és az összes részhalmazt tartalmazó halmazrendszer megfelelő. Legyen ismét $|\text{F}|=t$. Készítsünk egy $t\times 2^n$ méretű táblázatot, melynek sorai az $\text{F}$-beli halmazoknak, oszlopai pedig az $\left\{\mathrm{1,2,}\text{...}\mathrm{,}n\right\}$ részhalmazainak felelnek meg. Bármely $A\in \text{F}$ és $X\subset \left\{\mathrm{1,2,}\text{...}\mathrm{,}n\right\}$ halmazok esetén az $A$-nak megfelelő sor és az $X$-nek megfelelő oszlop közös mezőjébe írjunk $\left(+1\right)$-et, ha $|A\cap X|$ páros, illetve $\left(-1\right)$-et, ha $|A\cap X|$ páratlan. Ebben a táblázatban számítsuk ki a számok összegét kétféleképpen: oszloponként és soronként is. A feltétel szerint bármely nemüres $X$ esetén az $A\in \text{F}$ halmazoknak pontosan a felére lesz $|A\cap X|$ páros, illetve páratlan, vagyis az $X$-nek megfelelő oszlopban a számok fele $+1$, fele $-1$; az összegük $0$. Az üres halmaz minden $A\in \text{F}$-et a páros üres halmazban metsz, tehát az üres halmaznak megfelelő oszlopban mind a $t$ elem $+1$. Azt kaptuk, hogy a táblázatban az elemek összege $t$. Ha $\varnothing \in \text{F}$, akkor az $\varnothing$-nak megfelelő sorban csupa $+1$ áll, ezek összege $2^n$. Tekintsünk most egy tetszőleges nemüres $A\in \text{F}$ elemet és a neki megfelelő sort. Mivel az $A$ nemüres, az $\left\{\mathrm{1,2,}\text{...}\mathrm{,}n\right\}$ részhalmazaival vett metszeteinek éppen a fele páros, iletve páratlan; az ilyen sorokban az elemek összege $0$. Összességében, a táblázat összege $2^n$, ha $\varnothing \in \text{F}$, és $0$, ha $\varnothing \notin \text{F}$. A kétféle összeszámolásból azt kaptuk, hogy $t=0$ vagy $t=2^n$, vagyis $\text{F}$ az üres halmazrendszer, vagy pedig $\left\{\mathrm{1,2,}\text{...}\mathrm{,}n\right\}$ összes részhalmazából áll. Azt, hogy ez a két halmazrendszer teljesíti a feltételeket, ugyanúgy ellenőrizhetjük, mint az I. megoldásban.