Problem C. 1875. (November 2025)

C. 1875. Thanks to a generous donation, during the lunch break of the KöMaL Ankét on Saturday, \(\displaystyle m\) types of books were distributed among the \(\displaystyle n\) students present. There were multiple copies available of each book type, and everyone could choose freely: they could take books of several types, but at most one copy of each type. We know that for any two books there were a difference of at least three students between the set of students choosing each book. Prove that \(\displaystyle m \leq \frac{2^{n}}{n+1}\).

Proposed by Zoltán Paulovics, Budapest

(5 pont)

Deadline expired on December 10, 2025.

Sorry, the solution is available only in Hungarian. Google translation

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}\).

Statistics:

104 students sent a solution.
5 points:	54 students.
4 points:	9 students.
3 points:	7 students.
2 points:	1 student.
1 point:	7 students.
0 point:	9 students.
Unfair, not evaluated:	15 solutionss.

Problems in Mathematics of KöMaL, November 2025