Szerk
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)
1. megoldás. A megoldás során nem fogjuk használni, hogy a körlapok sugara egész szám.
A következő észrevétellel kezdjük a megoldást: ha egy ötelemű halmaz és a komplementere is izolálható, akkor létezik olyan egyenes, amely elválasztja egymástól az ötelemű halmazt és a komplementerét (és a 10 pont egyikén sem halad át). Valóban, tekintsük a két izoláló zárt körlapot. Ha nincs közös pontjuk, akkor tetszőleges egyenes megfelel, amelynek nincs közös pontja a körlapokkal (ilyen pl. a hatványvonaluk). Ha van közös pontjuk, akkor a metszetük nem tartalmazhatja a 10 pont egyikét sem, így ekkor bármelyik egyenes megfelel, amelynek a két körlappal csak a metszetükön belül van közös pontja (a hatványvonal itt is megfelelő).
Jelölje \(\displaystyle N\) az olyan ötelemű halmazokat, amelyek izolálhatók és a komplementerük is izolálható. Mivel 10 pontot \(\displaystyle \frac12\binom{10}{5}\) féle módon lehet 5-5 pontra bontani, így legfeljebb \(\displaystyle \frac12\binom{10}{5}+N\) izolálható ötelemű részhalmaza van a 10 pontnak. Azt kell tehát belátnunk, hogy \(\displaystyle N\le \frac{1}{6}\binom{10}{5}\).
Most azt fogjuk megmutatni, hogy legfeljebb annyiféle módon lehetséges egy 10 elemű ponthalmazt két ötelemű részre bontani egy egyenessel, ahányféle olyan irány van, amellyel nem lehet 5-5 pontra bontani a 10 pontot (sőt, valójában pontosan ennyiféle módon lehet). Ismert, hogy ilyen irányból véges sok van, ugyanis minden olyan egyenessel megvalósítható a felbontás, amely nem párhuzamos olyan egyenessel, amely legalább két ponton átmegy az adott pontok közül. Itt jegyezzük meg, hogy egy adott irányhoz csak egyféle kettéosztás tartozhat, hiszen ha két párhuzamos egyenes egyaránt 5-5 pontra bontja a 10 pontot, akkor a két egyenes között nem lehet adott pont.
Először minden iránynak megfeleltetünk egy pontot egy rögzített körvonalon a következő módon: rögzítsünk egy egyenest, és ezt feleltessük meg a körvonal egy rögzített \(\displaystyle P_0\) pontjának. Ezután vegyük azt az irányított \(\displaystyle \alpha\) szöget, amennyivel a rögzített egyenest elforgatva a megadott egyenessel párhuzamos egyenest kapunk (ez a szög egyértelmű mod \(\displaystyle \pi\)). Végül az iránynak feleltessük meg azt a \(\displaystyle P\) pontot a körvonalon, amelyre a \(\displaystyle P_0OP\sphericalangle=2\alpha\) (ez a szög egyértelmű mod \(\displaystyle 2\pi\), vagyis a pont jól definiált a körvonalon). Jelöljük meg azokat a pontokat a körvonalon, amelyek olyan iránynak felelnek meg, amellyel párhuzamos egyenessel nem lehet 5-5 pontra bontani a 10 pontot: ezek körívekre bontják a körvonalat, méghozzá annyi darab körívre, ahány pontot megjelöltünk. Körív alatt most ezeket a köríveket fogjuk érteni.
Ha tekintünk egy egyenest, amely 5-5 pontra bontja a 10 pontot, akkor lehet találni egy kellően kicsi szöget, amennyivel az egyenest elforgatva (bármelyik irányban) nem változik az, ahogyan az egyenes a 10 pontot kettéosztja: ez éppen azt jelenti, hogy egy köríven belül nem változhat meg a kettéosztás. Ezzel igazoltuk a fenti állításunkat, és azt is látjuk, hogy legfeljebb \(\displaystyle \binom{10}{2}\) olyan irány van, amellyel párhuzamos egyenessel nem lehet 5-5 pontra bontani a megadott 10 pontot.
Sajnos \(\displaystyle 42=\frac{1}{6}\binom{10}{5}<\binom{10}{2}=45\), így kéne találni legalább 3 olyan irányt, amellyel párhuzamos egyenessel nem lehet 5-5 pontra bontani a 10 pontot. Ha a 10 pont konvex burkának legalább 3 csúcsa van, akkor készen vagyunk, mert a konvex burok oldalegyenesei megfelelőek lesznek, ellenkező esetben pedig az összes pont egy egyenesre esik, és ekkor csak egy olyan irány van, amellyel párhuzamosan nem lehet 5-5 pontra bontani a 10 pontot. Ezzel a bizonyítást befejeztük.
Megjegyzés. Vödrös Dániel azt is megmutatta, hogy a pontpárok által meghatározott irányok közül csak minden második lehet olyan, hogy azzal párhuzamosan nem lehet 5-5 pontra bontani a 10 pontot, ezzel jelentősen javítva a becslést.
Diaconescu Tashi (Transylvania College, Kolozsvár, Románia, 12. o. t.)* Vödrös Dániel (Budapesti Fazekas M. Gyak. Ált. Isk. és Gimn., 11. o. t.)* és Sami El Hajjar (Milwaukee, University School of Milwaukee, USA, 11. o. t.) dolgozata alapján
2. megoldás. Először belátunk egy halmazrendszerekkel kapcsolatos állítást, amely Alain Pajor nevéhez fűzödik.
Á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, amelyeket \(\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, amelyeket \(\displaystyle \mathcal{F_1}\)-beli halmazokkal nem lehet szétszabdalni. Végül \(\displaystyle \mathcal{G_3}\) álljon \(\displaystyle H\) azon részhalmazaiból, amelyeket \(\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 az \(\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, illetve \(\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 \frac{2}{3}\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.
Megjegyzés. Egy halmazrendszer Vapnik–Chervonenskis dimenziója az a legnagyobb \(\displaystyle k\) szám, amelyre lehet találni egy olyan \(\displaystyle k\) elemű halmazt, amely szétszabdalható a halmazrendszer által. Azt mutattuk meg, hogy a feladatban az izolálható halmazokból álló halmazrendszer VC-dimenziója legfeljebb 3. A fenti Pajor-féle állításból pedig az következik, hogy ha egy \(\displaystyle n\) elemű halmaz részhalmazaiból álló halmazrendszer legalább \(\displaystyle \binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{k-1}\) darab halmazból áll, akkor a VC-dimenziója legalább \(\displaystyle k\).
13 dolgozat érkezett. 7 pontot kapott 9, 6 pontot 1 versenyző. 0 pontos 2, nem versenyszerű 1 dolgozat
A KöMaL kiadásának, a versenyek teljes lebonyolításának, díjazásának és a díjkiosztóval egybekötött Ifjúsági Ankétok szervezésének költségeit 2007 óta a MATFUND Középiskolai Matematikai és Fizikai Alapítvány fizeti.
Kérjük, személyi jövedelemadója 1%-ának felajánlásával álljon a több, mint 125 éve alapított Középiskolai Matematikai és Fizikai Lapok mellé!
Nem kell túl sokáig keresgélnünk az interneten a fejtörő feladatok között ahhoz, hogy sík vagy tér kitöltésére vonatkozó feladványra bukkanjunk. Ezek egyik fajtája az, amikor néhány síkidom vagy test valamilyen keretben van elhelyezve úgy, hogy látszólag teljesen kitöltik azt, de van még külön egy további eleme a játéknak.
Legutóbb szeptemberi számunkban foglalkoztunk bújócska típusú ördöglakatokkal. Elkészítésre ajánlottunk olvasóinknak egy pálcás változatot, ahol a ,,szokásos'' trükk nem működik, mivel az átbújtatás után (lásd ábra) a pálca nem fér át a hurkon a zsinór rövidsége miatt. Azonban vegyük észre, hogy ebben az átbújtatott állapotban valójában annyi a célunk, hogy a hurok a dupla zsinór másik oldalára kerüljön. Ezt úgy is elérhetjük, ha a téglatest formájú ,,alapot'' bújtatjuk át a hurkon.