Problem A. 842. (January 2023)

A. 842. \(\displaystyle n\) people live in a town, and they are members of some clubs (residents can be members of more than one club). No matter how we choose some (but at least one) clubs, there is a resident of the town who is the member of an odd number of the chosen clubs. Prove that the number of clubs is at most \(\displaystyle n\).

Proposed by Dömötör Pálvölgyi, Budapest

(7 pont)

Deadline expired on February 10, 2023.

First solution:

Assign to each set of clubs the people who are members of an odd number of clubs in the set.

Suppose that the same people are assigned to club-sets \(\displaystyle A\) and \(\displaystyle B\). Then, if \(\displaystyle H\) is the symmetric difference of \(\displaystyle A\) and \(\displaystyle B\), it is easy to see that every person is a member of an even number of clubs in \(\displaystyle H\), which contradicts the assumption. Therefore, the number of club-sets is less or equal to the number of person-sets, which is \(\displaystyle 2^n\). Hence, there are at most \(\displaystyle n\) clubs.

\(\displaystyle \\\)

Second solution:

For each club, take its indicator vector: this is a \(\displaystyle n\)-long vector over \(\displaystyle \mathbb{F}_2\) (i.e., the coordinates are understood modulo \(\displaystyle 2\)), and the \(\displaystyle k\)-th coordinate is \(\displaystyle 1\) if the \(\displaystyle k\)-th person is a member of the club, otherwise \(\displaystyle 0\).

According to the condition of the problem, the sum of any non-empty subset of indicator vectors modulo \(\displaystyle 2\) never yields the constant \(\displaystyle 0\) vector. This is equivalent to the indicator vectors being linearly independent over \(\displaystyle \mathbb{F}_2\). Since they belong to a \(\displaystyle n\)-dimensional space, this means that there can be at most \(\displaystyle n\) of them.

Statistics:

17 students sent a solution.
7 points:	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 points:	1 student.

Problems in Mathematics of KöMaL, January 2023