 |
Az A. 842. feladat (2023. január) |
A. 842. Egy faluban 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 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 A és B klubhalmazokhoz ugyanazokat az embereket rendeltük. Ekkor ha H az A és B klubhalmazok szimmetrikus differenciája, akkor könnyű látni, hogy minden ember páros sok klubnak a tagja H-ból, ez ellentmondás a feltétellel. Tehát a klubhalmazok száma kisebb-egyenlő az emberhalmazok számánál, ami 2n. Tehát legfeljebb n klub van.
Második megoldás:
Minden klubnak vegyük az indikátorvektorát: ez egy n hosszú vektor F2 fölött (azaz modulo 2 értendők a koordinátáti), és a k-adik koordinátája akkor 1, ha a k-adik ember tagja a klubnak, különben 0.
A feladat feltétele szerint az indikátorvektorok tetszőleges nemüres részhalmazát összeadva modulo 2, sose kapjuk a konstans 0 vektort. Ez éppen azzal ekvivalens, hogy az indikátorvektorok függetlenek F2 fölött. Mivel egy n dimenziós térbe tartoznak a vektorok, ez azt jelenti, hogy legfeljebb 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
|
|