Az A. 929. feladat (2026. március)

A. 929. Legyen \(\displaystyle \mathcal{P}\) egy tízelemű ponthalmaz a síkon. Egy \(\displaystyle \mathcal{Q}\subseteq \mathcal{P}\) ponthalmazra azt mondjuk, hogy izolálható, ha létezik olyan pozitív egész sugarú zárt körlap, amely \(\displaystyle \mathcal{Q}\) pontjait tartalmazza, de \(\displaystyle \mathcal{P}\setminus\mathcal{Q}\) pontjait nem. Bizonyítsuk be, hogy \(\displaystyle \mathcal{P}\) ötelemű részhalmazainak legalább harmada nem izolálható.

Javasolta: Bán-Szabó Áron (Palaiseau)

(7 pont)

A beküldési határidő 2026. április 10-én LEJÁRT.

Megoldás. Először belátunk egy halmazrendszerekkel kapcsolatos állítást.

Álljon az \(\displaystyle \mathcal{F}\) halmazrendszer a \(\displaystyle H\) alaphalmaz néhány részhalmazából (azaz \(\displaystyle \mathcal{F}\subset 2^H\)). A \(\displaystyle H\) halmaz egy \(\displaystyle G\) részhalmazát szétszabdalhatónak nevezzük, ha \(\displaystyle G\) összes részhalmaza megkapható \(\displaystyle G\cap F\) alakban, ahol \(\displaystyle F\in \mathcal{F}\). Azt állítjuk, hogy \(\displaystyle H\) szétszabdalható részhalmazaiból legalább \(\displaystyle |\mathcal{F}|\) darab van (ahol \(\displaystyle |\mathcal{F}|\) az \(\displaystyle \mathcal{F}\) elemszámát jelöli).

Ezt az állítást az \(\displaystyle \mathcal{F}\) elemszáma szerinti teljes indukcióval látjuk be. Az állítás igaz, ha \(\displaystyle |\mathcal{F}|=1\), hiszen az üres halmaz szétszabdalható. Most tegyük fel, hogy \(\displaystyle |\mathcal{F}|\ge 2\), és az állítást már igazoltuk minden olyan halmazrendszer esetén, amelynek \(\displaystyle |\mathcal{F}|\)-nél kevesebb eleme van.

Mivel \(\displaystyle |\mathcal{F}|\ge 2\), ezért lehet találni olyan \(\displaystyle h\in H\) elemet, amelyhez olyan \(\displaystyle \mathcal{F}\)-beli elem is van, amelynek eleme \(\displaystyle h\), és olyan is, amelynek nem. Álljon \(\displaystyle \mathcal{F_1}\) azokból az \(\displaystyle \mathcal{F}\)-beli halmazokból, amelyeknek nem eleme \(\displaystyle h\), \(\displaystyle \mathcal{F_2}\) pedig azokból, amelyeknek eleme. A \(\displaystyle h\) választása miatt \(\displaystyle |\mathcal{F_1}|,|\mathcal{F_2}|<|\mathcal{F}|\), így ezekre alkalmazható majd az indukciós feltevés, és mivel \(\displaystyle \mathcal{F_1}\) és \(\displaystyle \mathcal{F_2}\) diszjunkt uniója \(\displaystyle \mathcal{F}\), így \(\displaystyle |\mathcal{F}|=|\mathcal{F_1}|+|\mathcal{F_2}|\).

Most álljon \(\displaystyle \mathcal{G_1}\) a \(\displaystyle H\) azon \(\displaystyle \mathcal{F_1}\)-beli halmazok által szétszabdalható részhalmazaiból, melyeket \(\displaystyle \mathcal{F_2}\)-beli halmazokkal nem lehet szétszabdalni. Hasonlóan, \(\displaystyle \mathcal{G_2}\) álljon \(\displaystyle H\) azon \(\displaystyle \mathcal{F_2}\)-beli halmazok által szétszabdalható részhalmazaiból, melyeket \(\displaystyle \mathcal{F_1}\)-beli halmazokkal nem lehet szétszabdalni. Végül \(\displaystyle \mathcal{G_3}\) álljon \(\displaystyle H\) azon részhalmazaiból, melyeket \(\displaystyle \mathcal{F_1}\)-beli és \(\displaystyle \mathcal{F_2}\)-beli halmazokkal is szét lehet szabdalni. A definíció alapján világos, hogy \(\displaystyle \mathcal{G_1}\), \(\displaystyle \mathcal{G_2}\) és \(\displaystyle \mathcal{G_3}\) páronként diszjunktak egymástól, továbbá \(\displaystyle \mathcal{G_1}\cup\mathcal{G_3}\) a \(\displaystyle H\) alaphalmaz \(\displaystyle \mathcal{F_1}\) által szétszabdalható részhalmazaiból áll, így indukciós feltevés szerint \(\displaystyle |\mathcal{G_1}|+|\mathcal{G_3}|\ge |\mathcal{F_1}|\) és \(\displaystyle |\mathcal{G_2}|+|\mathcal{G_3}|\ge |\mathcal{F_2}|\). Vegyük még észre, hogy \(\displaystyle \mathcal{G_1},\mathcal{G_2},\mathcal{G_3}\subset H\setminus\{h\}\), hiszen az \(\displaystyle \mathcal{F_1}\)-beli halmazokkal nem lehet a \(\displaystyle h\)-t tartalmazó halmazt szétszabdalni, hiszen egyik \(\displaystyle \mathcal{F_1}\)-beli halmaz sem tartalmazza a \(\displaystyle h\)-t, és hasonlóan, az \(\displaystyle \mathcal{F_2}\)-beli halmazokkal sem lehet a \(\displaystyle h\)-t tartalmazó halmazt szétszabdalni, hiszen mindegyik \(\displaystyle \mathcal{F_2}\)-beli halmaz tartalmazza \(\displaystyle h\)-t. Végül a bizonyítás befejezéséhez azt kell észrevenni, hogy ha \(\displaystyle G\in \mathcal{G_3}\), akkor \(\displaystyle G\cup \{h\}\) is szétszabdalható \(\displaystyle \mathcal{F}\) által, hiszen a \(\displaystyle h\)-t nem tartalmazó részhalmazai mind megkaphatók az \(\displaystyle \mathcal{F_1}\)-beli halmazok segítségével, a \(\displaystyle h\)-t tartalmazó részhalmazai pedig mind megkaphatók a \(\displaystyle \mathcal{F_2}\)-beli halmazok segítségével, így a szétszabdalható halmazok száma legalább \(\displaystyle |\mathcal{G_1}|+|\mathcal{G_2}|+2|\mathcal{G_3}|=(|\mathcal{G_1}|+|\mathcal{G_3}|)+(|\mathcal{G_2}|+|\mathcal{G_3}|)\ge |\mathcal{F_1}|+|\mathcal{F_2}|=|\mathcal{F}|\).

Térjünk most rá a feladat megoldására. Az \(\displaystyle \mathcal{F}\) halmazrendszer álljon a \(\displaystyle 10\)-elemű ponthalmazunk izolálható részhalmazaiból. Azt kell észrevenni, hogy a szétszabdalható ponthalmazok legfeljebb háromeleműek lehetnek. Ehhez azt kell megmutatni, hogy a négyelemű halmazoknak van olyan részhalmaza, amely nem metszhető ki belőle egy izolálható részhalmazzal, azaz ezzel ekvivalens módon egy körrel, hiszen az a kör, amely kimetszi az izolálható ponthalmazt a \(\displaystyle 10\)-elemű ponthalmazból, az ugyanúgy metszi a \(\displaystyle 10\)-elemű halmaz részhalmazait, mint a tekintett izolálható ponthalmaz.

Ha a tekintett négy pont konvex burka legfeljebb \(\displaystyle 3\) csúcsot tartalmaz, akkor a konvex burok csúcsainak halmaza nem metszhető ki, hiszen a kör konvex alakzat, azaz ha tartalmazza a konvex burok csúcsait, akkor az összes pontot tartalmazza.

Ha a tekintett négy pont konvex burka négy csúcsból áll, azaz egy \(\displaystyle ABCD\) konvex négyszögünk van, akkor valamely két szemközti szögének összege legalább \(\displaystyle 180^\circ\). Az általánosság rovása nélkül feltehető, hogy \(\displaystyle ABC\sphericalangle+CDA\sphericalangle\ge 180^\circ\). Ekkor az \(\displaystyle \{A,C\}\) halmaz nem izolálható, hiszen ha lenne olyan kör, amely tartalmazza \(\displaystyle A\)-t és \(\displaystyle C\)-t, de \(\displaystyle B\)-t és \(\displaystyle D\)-t nem, akkor messe az \(\displaystyle AC\) egyenes a körvonalat az \(\displaystyle A'\) és a \(\displaystyle C'\) pontban, és legyen \(\displaystyle B'\) és \(\displaystyle D'\) két tetszőleges pont a körvonalon az \(\displaystyle AC\) egyenes \(\displaystyle B\)-vel ill. \(\displaystyle D\)-vel megegyező oldalán, és ekkor \(\displaystyle ABC\sphericalangle\le A'BC'\sphericalangle<A'B'C'\sphericalangle\), és hasonlóan megmutatható, hogy \(\displaystyle CDA\sphericalangle<C'D'A'\sphericalangle\), ami viszont ellentmondás, hiszen \(\displaystyle A'BC'\sphericalangle+C'D'A'\sphericalangle=180^\circ\).

Így tehát a szétszabdalható halmazok száma legfeljebb \(\displaystyle \binom{10}{0}+\binom{10}{1}+\binom{10}{2}+\binom{10}{3}=176\), vagyis az izolálható halmazok száma is legfeljebb ennyi. Nekünk ennél egy kicsit jobb becslés kell, mert \(\displaystyle \frac23\binom{10}{5}=168\), azonban ez egyszerű, hiszen az összes egyelemű halmaz izolálható, vagyis ötelemű izolálható halmazból legfeljebb \(\displaystyle 176-10=166\) van, és kész a bizonyítás.

Statisztika:

13 dolgozat érkezett.
7 pontot kapott:	Aravin Peter, Bodor Mátyás, Bolla Donát Andor, Diaconescu Tashi, Forrai Boldizsár, Kis Ágoston, Morvai Várkony Albert, Sami El-Hajjar, Vödrös Dániel László.
6 pontot kapott:	Rajtik Sándor Barnabás.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2026. márciusi matematika feladatai