There are 40 participants in an art workshop. Each one of them signed up for one or more of the following courses: handicraft, ceramics and Chinese paintings. One of the combinations of courses must have at least n participants. Find the largest possible value of n.
Anyone know how to do this? It is not for homework or anything I just wanna know the way to do it.
There must be at least 14 participants signed up for one of the three classes (by the pigeonhole principle), and this is the best possible $n$ if one means simply that some (single) combination of a class must attract at least $n$ participants.
However if instead we mean to count participants whose entire signup selections agree, then the number $n$ will come down. There are seven possible (nonempty) selections of classes (as computed by $2^3 - 1$, discarding the empty subset of no classes), and distributing the 40 participants as evenly as possible across these combinations gives as few as $n=6$ in the largest number of participants. One again argues by pigeonhole principle that $n=6$ will not be improved upon (if only 5 or fewer signed up for any one of the seven combinations, we'd have at most 35 participants).