Let $n \geq 14$ be a positive integer. In a city there are more than $n$ clubs, all of them have exactly 14 members. At each group of $n+1$ clubs there is a person who is member of at least 15 of these $n+1$ clubs. Show that it is possible to select $n$ people such that all clubs have a member among these people.

This question is from Hungary. I tried to proceed by induction on the number $n$ and I could prove the base case $n=14$. However I don't know how to go on. Any help is welcome.

  • $\begingroup$ Pigeon-hole principle. $\endgroup$ – Rogelio Molina Jun 5 '15 at 7:12
  • $\begingroup$ @RogelioMolina Could you provide a detailed proof? $\endgroup$ – PSPACEhard Jun 5 '15 at 7:19
  • 1
    $\begingroup$ @RogelioMolina How do you use Pigeonhole principle to prove this problem? $\endgroup$ – jack Jun 5 '15 at 16:11
  • $\begingroup$ It is a hunch, I could be wrong, but I will look into the problem later today if I get a chance. I would start by drawing a graph, members as vertices and coloured edges for clubs, one colour for each club. $\endgroup$ – Rogelio Molina Jun 5 '15 at 17:04

Let us pick any $n$ clubs, and call this the base set of clubs. The rest of the clubs are currently considered uncovered. We also have a (currently empty) solution set $S$, where we aim to have the final set of $n$ members who will cover all of the clubs. Repeat the following process until there are (1) no more uncovered clubs, or (2) we have repeated $n$ times.

  1. Pick any uncovered club.
  2. Apply the given condition on this set of $n+1$ clubs: the base set + the club picked in $(1)$. From the problem statement, we get a member, say $M$, that is in atleast $15$ of these clubs.
  3. Add $M$ to our solution set $S$, and mark as covered, all clubs not in the base set, and having $M$ as a member.

Now there are 2 cases. Either (1) we ran the above steps $k$ times, $k \leq n$ and we have no more uncovered sets. Or (2) we ran the above steps exactly $n$ times, and there are still some uncovered sets.

Case (1): The only problem here is that some of the base sets might still not be covered. Note that each of the $k$ members in $S$ are present in at least $14$ of the base sets. That accounts for at least $14k$ slots out of the available $14n$ slots in the base set. Which means atleast $14k/14 = k$ base sets have been covered, leaving us with at most $n-k$ uncovered base sets. Pick one member from each of these (at most) $n-k$ base sets and add them to our solution set $S$, and we have a valid final solution set.

Case (2): We have exactly $n$ members in our solution. Each of those $n$ members are present in atleast 14 of our base sets, thus taking up atleast $14n$ base slots, which happen to be all of our base slots. Hence if we now consider the following $n+1$ clubs: base set + any uncovered club, we get a contradiction to the given condition in the problem statement.

EDIT: It seems that the choice of $14$ and $15$ in the problem statement is arbitrary, any two consecutive numbers would have served the purpose.

  • $\begingroup$ Make sense! Great! $\endgroup$ – PSPACEhard Jun 5 '15 at 8:12
  • 1
    $\begingroup$ @mathosopher I don't think your solution is true. Let's say for example, $M$ is a member of all $n+1$ clubs (the $n$ clubs from the base set + the club picked in (1)). When you change the club picked in (1) and keep the base set constant, the member $M$ is still a person satisfying the condition of the problem (i.e. $M$ is a member of at least 15 clubs). Repeating this process $n$ times the only member we have is $M$. So your assumption of: '(2) we have repeated $n$ times' => '(2) we have exactly $n$ members in our solution' doesn't seem to be true. $\endgroup$ – jack Jun 5 '15 at 16:09
  • $\begingroup$ @mathosopher Actually your solution can be easily fixed. It's possible to find a group of $n$ clubs such that every person from this group is member of at most 14 from these $n$ clubs (otherwise we are done by induction). We consider this group the base set of clubs. So what I wrote above does not hold anymore. Thanks for your solution! $\endgroup$ – jack Jun 5 '15 at 23:46
  • $\begingroup$ @jack Nice catch! And an even nicer fix! $\endgroup$ – mathosopher Jun 6 '15 at 3:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.