A C. 1875. feladat (2025. november)

C. 1875. Egy nagylelkű adománynak hála a KöMaL Ankét szombati ebédszünetében \(\displaystyle m\) fajta könyvet osztottak szét a jelenlévő \(\displaystyle n\) diák között. A könyvek mindegyikéből rendelkezésre állt több példány is, továbbá mindenki kedvére válogathatott: többfajta könyvből is vihettek, de egy fajtából legfeljebb egyet.

Tudjuk, hogy bármely két könyv esetén legalább három diákban különbözött a könyveket választók halmaza. Bizonyítsuk be, hogy \(\displaystyle m \leq \frac{2^{n}}{n+1}\).

Javasolta: Paulovics Zoltán (Budapest)

(5 pont)

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

Megoldás. Tekintsük a diákok \(\displaystyle n\) fős \(\displaystyle H\) halmazának azon \(\displaystyle m\) darab részhalmazát, amelyekre teljesül, hogy az egyik fajta könyvből pontosan a részhalmazba tartozó diákok kaptak. Ezen \(\displaystyle m\) halmaz mindegyikéhez rendeljük hozzá \(\displaystyle H\) azon részhalmazait, amelyek pontosan egy elemben térnek el tőlük. Így mind az \(\displaystyle m\) halmazhoz \(\displaystyle n\) másikat rendeltünk hozzá, hiszen egy rögzített halmaz esetén, ha egy diák benne van, akkor kivesszük, ha nincs, akkor betesszük – ezt minden diákra egyesével megtehetjük –, így pedig \(\displaystyle n\) darab „új” halmazt kapunk. (Úgy is mondhatnánk, hogy bármely \(\displaystyle X\) halmaz esetén minden diákra vesszük a diákot tartalmazó \(\displaystyle Y\) halmaz és az \(\displaystyle X\) halmaz szimmetrikus differenciáját.) Világos, hogy mind az \(\displaystyle m(n+1)\) halmaz különböző részhalmaza \(\displaystyle H\)-nak. Tehát átrendezés után: \(\displaystyle m \leq \frac{2^{n}}{n+1}\).

Statisztika:

A C. 1875. feladat értékelése még nem fejeződött be.

A KöMaL 2025. novemberi matematika feladatai