MathDB

A. 842

Part of KoMaL A Problems 2022/2023

Problems(1)

People in clubs

Source: KoMaL A. 842

2/11/2023
nn 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 nn.
Proposed by Dömötör Pálvölgyi, Budapest
combinatoricskomal