Az A. 842. feladat (2023. január)

A. 842. Egy faluban \(\displaystyle n\) ember él, akik klubokba járnak (egy ember több klubnak is lehet tagja). Akárhogy választunk ki néhány (de legalább egy) klubot, lehet találni a faluban egy olyan embert, aki a kiválasztott klubok közül páratlan soknak tagja. Mutassuk meg, hogy a klubok száma legfeljebb \(\displaystyle n\).

Javasolta: Pálvölgyi Dömötör (Budapest)

(7 pont)

A beküldési határidő 2023. február 10-én LEJÁRT.

Első megoldás:

Minden klubhalmazhoz rendeljük hozzá azon emberek halmazát, akik páratlan sok klubnak tagjai a halmazól.

Tegyük föl, hogy az \(\displaystyle A\) és \(\displaystyle B\) klubhalmazokhoz ugyanazokat az embereket rendeltük. Ekkor ha \(\displaystyle H\) az \(\displaystyle A\) és \(\displaystyle B\) klubhalmazok szimmetrikus differenciája, akkor könnyű látni, hogy minden ember páros sok klubnak a tagja \(\displaystyle H\)-ból, ez ellentmondás a feltétellel. Tehát a klubhalmazok száma kisebb-egyenlő az emberhalmazok számánál, ami \(\displaystyle 2^n\). Tehát legfeljebb \(\displaystyle n\) klub van.

\(\displaystyle \\\)

Második megoldás:

Minden klubnak vegyük az indikátorvektorát: ez egy \(\displaystyle n\) hosszú vektor \(\displaystyle \mathbb{F}_2\) fölött (azaz modulo \(\displaystyle 2\) értendők a koordinátáti), és a \(\displaystyle k\)-adik koordinátája akkor \(\displaystyle 1\), ha a \(\displaystyle k\)-adik ember tagja a klubnak, különben \(\displaystyle 0\).

A feladat feltétele szerint az indikátorvektorok tetszőleges nemüres részhalmazát összeadva modulo \(\displaystyle 2\), sose kapjuk a konstans \(\displaystyle 0\) vektort. Ez éppen azzal ekvivalens, hogy az indikátorvektorok függetlenek \(\displaystyle \mathbb{F}_2\) fölött. Mivel egy \(\displaystyle n\) dimenziós térbe tartoznak a vektorok, ez azt jelenti, hogy legfeljebb \(\displaystyle n\) lehet belőlük.

Statisztika:

17 dolgozat érkezett.
7 pontot kapott:	Bognár 171 András Károly, Diaconescu Tashi, Foris Dávid, Lovas Márton, Molnár-Szabó Vilmos, Móricz Benjámin, Nádor Benedek, Németh Márton, Seres-Szabó Márton, Sida Li, Simon László Bence, Szakács Ábel, Sztranyák Gabriella, Tarján Bernát, Varga Boldizsár, Wiener Anna.
2 pontot kapott:	1 versenyző.

A KöMaL 2023. januári matematika feladatai