Az A. 637. feladat (2015. február)

A. 637. Legyen \(\displaystyle n\) pozitív egész. Legyen \(\displaystyle \mathcal{F}\) egy olyan halmazrendszer, amely egy \(\displaystyle n\) elemű \(\displaystyle X\) halmaz összes részhalmazának több, mint a felét tartalmazza. Bizonyítsuk be, hogy \(\displaystyle \mathcal{F}\)-ből mindig kiválasztható \(\displaystyle \lceil\log_2n\rceil+1\) halmaz úgy, hogy ezek együtt szeparálják \(\displaystyle X\) elemeit, vagyis \(\displaystyle X\) bármely két különböző eleméhez van olyan kiválasztott halmaz, amely a kettő közül pontosan egyet tartalmaz.

Schweitzer Miklós Emlékverseny, 2014

(5 pont)

A beküldési határidő 2015. március 10-én LEJÁRT.

Megoldás. Az \(\displaystyle X\) halmaz részhalmazai a szimmetrikus differencia művelettel, mint összeadással egy \(\displaystyle \mathbb{F}_2\) feletti \(\displaystyle V\) vektorteret alkotnak. Megadható egy \(\displaystyle \lceil\log_2 n\rceil\) elemű \(\displaystyle \cal U\) családja nem feltétlenül \(\displaystyle \cal F\)-beli részhalmazoknak, ami szeparálja \(\displaystyle X\)-et. Legyen \(\displaystyle W\) az \(\displaystyle \cal U\) által generált altér. Ennek eltoltjai particionálják \(\displaystyle V\)-t, így találhatunk olyan \(\displaystyle W+c\) eltoltat, amelyikben az elemek több, mint fele \(\displaystyle \cal F\)-ben van. Legyen \(\displaystyle d\in(W+c)\cap\cal F\) tetszőleges és tekintsük az \(\displaystyle \{x\in W\mid x+d\in{\cal F}\}\) halmazt. Minthogy ez \(\displaystyle W\) elemeinek több, mint felét tartalmazza, így generálja \(\displaystyle W\)-t és kiválasztható belőle \(\displaystyle W\) egy \(\displaystyle \cal Z\) bázisa. Itt \(\displaystyle \cal Z\) az \(\displaystyle \cal U\) által generált \(\displaystyle W\) altér bázisa, így

\(\displaystyle |\mathcal Z| \le |\mathcal U|= \lceil\log_2 n\rceil \)

(az egyenlőség is könnyen látszik, de nem kell). Tekintsük az \(\displaystyle \cal F\) (legfeljebb) \(\displaystyle \lceil\log n\rceil+1\) eleméből álló

\(\displaystyle \{d\}\cup\{z+d\mid z\in \mathcal Z\}\)

halmazt. Ez megfelel a feladat elvárásainak, hiszen az általa generált altér tartalmazza \(\displaystyle W\)-t, és így szeparálja \(\displaystyle X\)-et, márpedig az \(\displaystyle X\) bármely két rögzített elemét nem szeparáló részhalmazok alteret alkotnak \(\displaystyle V\)-ben, így egy részhalmaz pontosan akkor szeparálja \(\displaystyle X\)-et, ha az általa generált altér szeparálja.

Megjegyzés. A feladat szerzői Lángi Zsolt, Naszódi Márton, Pach János, Tardos Gábor és Tóth Géza.

A fenti megoldás Mészáros Andrástól származik, és a Schweitzer-versenybizottság bocsátotta rendelkezésünkre. A Schweitzer-verseny eredménye, feladatai és a feladatok megoldásai megtalálhatók a verseny honlapján: http://www.bolyai.hu/schweitzer.htm

Statisztika:

0 dolgozat érkezett.

A KöMaL 2015. februári matematika feladatai