21
$\begingroup$

There are $100$ students in a school, and they form $450$ clubs. Any two clubs have at least $3$ students in common, and any five clubs have no more than $1$ student in common. Must it be that some four clubs have exactly $1$ student in common?

$\endgroup$
  • 4
    $\begingroup$ Can there be identical clubs? $\endgroup$ – citronrose Dec 19 '14 at 22:42
1
$\begingroup$

I am not completely sure my argument is correct, but I would say that it is not possible to have at least 3 students in common with all other groups, and at most one between 5 groups.

If we look at the size $s$ of a club, there are ${s\choose 3}$ combinations of 3 members. Any other club must contain at least one of those $s\choose 3$ combinations. Thus, the average number of times such a combination occurs among other clubs, is $449/{s\choose 3}$. If this number is strictly greater than 3, there must be at least one of those combinations that occurs among 4 other clubs. This contradicts the second assumption of no five clubs sharing more than one member. Therefore, $s$ satisfies $449/{s\choose 3}>3$. This gives that $s\geq 11$.

This means that the average number of clubs that a person participates in is at least $11\cdot 450/100=49,5$. Therefore, there is at least one person $p$ participating in at least 50 clubs. Consider these 50 clubs. By the second assumption, no five of these clubs share any other member than $p$. However, the total number of other members of these clubs is at least $10\cdot 50=500$, and there are 99 other persons. Therefore, at least one of these 99 other persons must occur in 5 of those clubs. This gives a contradiction.

$\endgroup$
  • $\begingroup$ Your arguments seem to be OK. $\endgroup$ – Alex Ravsky Jan 30 '16 at 14:22
0
$\begingroup$

I'm not going to give a complete answer, I just want to point out a couple of things; also this is more a comment than an answer, but I write it here because of formatting stuff.

This looks like the typical problem about the inclusion-exclusion principle.

Let us denote the clubs by $A_1, A_2, \dots, A_{450}$. We have

$$ \left| \bigcup_{i=1}^{450} A_i \right| \leq 100 $$ $$ |A_i \cap A_j | \geq 3, \forall i,j $$ $$ |A_i \cap A_j \cap A_k \cap A_l \cap A_m| \leq 1, \forall i,j,k,l,m $$

Now we use the inequality that follows from the inclusion-exclusion principle

$$ 100 = \left| \bigcup_{i=1}^{450} A_i \right| \leq \\ \leq \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k|- \sum |A_i \cap A_j \cap A_k \cap A_l| + \sum |A_i \cap A_j \cap A_k \cap A_l \cap A_m| \leq \\ \leq \sum |A_i| - 3 \cdot {{450} \choose 2} + \sum |A_i \cap A_j \cap A_k|- \sum |A_i \cap A_j \cap A_k \cap A_l| + {{450} \choose 5} $$

I guess that now one should use some "trick" but I don't see it.

$\endgroup$
-1
$\begingroup$

The problem can be made easier to solve if we observe that if a set of clubs has X students in common then all subsets containing at least two clubs will have at least X students in common. For example, if we have five clubs : A, B, C, D, and E, and three students in all five of these clubs then clubs A, C, and E will have at least three students in common. Clubs B and E will have at least three students in common.

It may not be clear from the problem statement that the O.P. doesn't mean that every two club combination must have at three students in common. There are ${450*449\over 2} = 101025$ two club combinations in 450 clubs which way outside the 100 student parameter we are limited to. Looking at higher club combinations just makes things worse. There are ${450*449*448\over 6} = 15086400$ three club combinations

What I think the O.P. meant to say was that each of the 450 clubs must have three students in common with at least one other club and if any club has students in common with four or more clubs then it cannot have more than one student in common. Given these requirements must there be a club where it has exactly one student in common with three other clubs.

To provide a counter example I must show that all four club combinations have 0 students in common or it must have two or more students in common while satisfying the other conditions.

Let's assume that every three club combination doesn't have any students in common, so to solve this we divide the 450 clubs into 225 sets of 2 clubs. To satisfy the first requirement, that each club must have three students in common with at least one other club, we put three students in each set where all students are apart of both clubs in their respective set this would mean that a minimum of 675 students are required.

Now let's assume instead that every four club combination doesn't have any students in common. To solve this we divide the 450 clubs into 150 sets of 3 clubs. This would require 450 students by applying the same process the above paragraph and using the first observation above.

From this we can deduce that the more clubs students participate in the less students are required to satisfy the requirements.

So if one student is in all 450 clubs. Then every five club combination has one student in common. To provide a counter example, adding at least one student in common to each four club combination without adding students in common to any five club combination, requires ${450*449*448*447\over 24}=1685905200$ additional students.

Let's look at a slightly altered version of the problem where we have 20 clubs instead of 450 and instead of having 100 students we just want to find the minimum number of students to provide a counter example. Keeping all other requirements the same. Dividing the 20 clubs into four sets of five clubs, where each set has one student in five clubs, then adding two students to each four club combination in each set. This requires (2 students)(5 four club combinations in each set)(4 sets)+(4 original students) = 44 students. Trying a second case where dividing the 20 clubs into five sets of four clubs so each set has three students in all clubs so that only 15 students are required to satisfy the requirements with no four club combination having exactly one student in common.

Thus having a student in more than four clubs causes more problems than it solves. By dividing the 450 clubs into 112 sets of four clubs and one set of two clubs, we have three students in each set where they are in all clubs in their respective set so we need a minimum of 339 students to show a counter example. Thus there must be at least one four club combination with exactly one student in common, because the more clubs students are in the less students are required to provide a counter example, unless the student is in five or more clubs in which case the number of students increases greatly.

$\endgroup$

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.