Number of students in school club : $4$ Circles Venn Diagram Puzzle

Question

There are $200$ students in a class. Each student is a member of at least on of the clubs Eagles, Falcons, Tigers and Pythons.

1. If each club has $100$ students, then the number of students who are members of all the four clubs is at the most .....

2. If each club has $120$ students, then the number of students who are members of at the most two clubs is at the least .....

3. If each club has $140$ students, then the number of students who are members of at least three clubs is at least ....

I came across this question and I tried to solve it using the $4$ circles Venn diagram but it is a very chaotic way to solve this (Too many variables come into picture and it all got messed up) and even I was only able to solve the first question.

Any way or method to simplify the solution approach for this question? Any help is appreciated.

Thanks!

Answer 1

Denote the clubs by $E,F,T,P$ respectively.

There are many regions produced in Venn diagram such as $E \cap F \cap T$ and $E-T-F-P$. To put maximum students into $E \cap F \cap T\cap P$, we'd like to put zeros in most of them, while keeping the numbers of students only in a single club minimum.

Let the number of students who are only members of club $E$ be $A$ and those present in all clubs be $B$. If all other regions have zero students, then number of students who are only members of other clubs is also $A$.

We get $A+B=100$ and $4A+B=200$. Taking difference, $3A=100$. This is non-integer. But we may just take $A=33$ and $1$ balance can be put into $(E \cap F)-T-P$ and $(T \cap P)-E-F$ each.

Thus we got maximum for the case of $100$ $(1\pmod 3)$ owing to restriction by divisibility by $3$. Can you now solve for $120$ $(0\pmod 3)$ and $140$ $(2\pmod 3)$?

Answer 2

The set $A$ is the set of all students that are member of the first club, the set $B$ is the set of all students that are member of the second club. The sets $C,D$ are the sets of students of the third and fourth club.

The set of all student can be partitioned to 16 different sets with regards to A,B,C,D. There is not student that is not member of any club. So the set $ A'\cap B' \cap C' \cap D'$ is empty. The symbol $X'$ is the complement of the set $X.$ We define the set $P_{\mathit{BD}}=A'\cap B \cap C' \cap D$, and other members of the partion,
$P_A, P_B, P_C, P_D, P_\mathit{AB}, P_\mathit{AC}, P_\mathit{AD}, P_\mathit{BC}, P_\mathit{BD}, P_\mathit{CD}, P_\mathit{ABC}, P_\mathit{ABD}, P_\mathit{ACD}, P_\mathit{BCD}, P_\mathit{ABCD}$ in a similar way.

We define the variable $\mathit{bd}=|P_{BD}|$ and the other fifteen nonegative integer variables $a, b, c, d, \mathit{ab}, \mathit{ac}, \mathit{ad}, \mathit{bc}, \mathit{bd}, \mathit{cd}, \mathit{abc}, \mathit{abd}, \mathit{acd}, \mathit{bcd}, \mathit{abcd}$ are defined in a similar way.

The number of students that are in the first club is $$|A|=a+\mathit{ab}+\mathit{ac}+\mathit{ad}+\mathit{abc}+\mathit{abd}+\mathit{acd}+\mathit{abcd}$$ and this number is $S$, where $S=100$ in your first question, and $S=120$ and $S=140$ in your other questions. But we do our reasoning for arbitrary $S.$ For $|B|$, $|C|$, $|D|$ are defined in a similar way. So we get the four equations

$$a+\mathit{ab}+\mathit{ac}+\mathit{ad}+\mathit{abc}+\mathit{abd}+\mathit{acd}+\mathit{abcd}=S\\ b+\mathit{ab}+\mathit{bc}+\mathit{bd}+\mathit{abc}+\mathit{abd}+\mathit{bcd}+\mathit{abcd}=S\\ c+\mathit{ac}+\mathit{bc}+\mathit{cd}+\mathit{abc}+\mathit{acd}+\mathit{bcd}+\mathit{abcd}=S\\ d+\mathit{ad}+\mathit{bd}+\mathit{cd}+\mathit{abd}+\mathit{acd}+\mathit{bcd}+\mathit{abcd}=S$$

Because the number of a students is $200$ additionally the following equation holds $$a+b+c+d+\mathit{ab}+\mathit{ac}+\mathit{ad}+\mathit{bc}+\mathit{bd}+\mathit{cd}+\mathit{abc}+\mathit{abd}+\mathit{acd}+\mathit{bcd}+\mathit{abcd}=200 $$

The number $\mathit{abcd}$ is the number of students that are member of all four clubs. This is the number we want to maximize. So this is an integer optimization problem that we have to solve.

Now let us assume that we have already found a assignments of the students to the clubs that these five equations hold but $abcd$ may not be as large as possible. The following i such an assignment: $$a=3,b=10,c=13,d=72,\\\mathit{ab}=7,\mathit{ac}=5,\mathit{ad}=2,\mathit{bc}=0,\mathit{bd}=1,\mathit{cd}=4,\\\mathit{abc}=62,\mathit{abd}=5,\mathit{acd}=1,\mathit{bcd}=0,\\\mathit{abcd}=15 \tag{x.1}$$

We want to try to change the assignment of some students to the clubs so that still all clubs have $S$ members but the number $\mathit{abcd}$ increases.

Here is an example:

Assume there is a student $x$ that is member of the set $P_\mathit{ABC}$ but not $D.$ So $x$ contributes $1$ to the number $\mathit{abc}$ and nothing to any of the other fourteen variables. Also assume there is another student $y$ that is member of the sets $A,B,D$ but not member of $C.$ So $y \in P_\mathit{ABD}.$ The student $y$ contributes $1$ to the variable $\mathit{abd}$ and nothing to the other variables.

Now we will resolve the membership of $x$ of the club $C$, that is , we will remove $x$ from $C$. But we make $y$ a member of $C$. Now $x$ is only a member of $A$ and $B$ and $y$ is a member of all clubs now. The club $C$ lost a member but another student joined the club, so the club has still $S$ members. But the number of students that are member of all clubs increase by one. All in all the following happend: the variables $\mathit{abc}$ and $\mathit{abd}$ decreased by $1$, the variables $\mathit{abcd}$ and $\mathit{ab}$ increased by one.

We can apply this operation on our example $(x.1)$ and this results in

$$a=3,b=10,c=13,d=72,\\\mathit{ab}=8,\mathit{ac}=5,\mathit{ad}=2,\mathit{bc}=0,\mathit{bd}=1,\mathit{cd}=4,\\\mathit{abc}=61,\mathit{abd}=4,\mathit{acd}=1,\mathit{bcd}=0,\\\mathit{abcd}=16 \tag{x.2}$$

we can repeat this action 4 times and get $$a=3,b=10,c=13,d=72,\\\mathit{ab}=12,\mathit{ac}=5,\mathit{ad}=2,\mathit{bc}=0,\mathit{bd}=1,\mathit{cd}=4,\\\mathit{abc}=57,\mathit{abd}=0,\mathit{acd}=1,\mathit{bcd}=0,\\\mathit{abcd}=16 \tag{x.3}$$

There are a lot of such operations that enables us to decrease one or more of the variables $\mathit{ab}, \mathit{ac}, \mathit{ad}, \mathit{bc}, \mathit{bd}, \mathit{cd}, \mathit{abc}, \mathit{abd}, \mathit{acd}, \mathit{bcd}$ by changing the club membership of one or more studens and keppeng the numbers $|A|$,$|B|$,$|C|$,$|D|$ constant and never decreases $\mathit{abcd}.$

There are other way to change the membership of the elements to the sets A,B,C,D such that the size of A,B,C and D remain the same and the size of $\mathit{abcd}$ does not increase. If we do the correct changes after a finite number of steps we arrive at a system (maybe after changin the names) such that

1. the size of A, B, C and D did not change
2. the sets $P_\mathit{AC}, P_\mathit{AD}, P_\mathit{BC}, P_\mathit{BD}, P_\mathit{CD}, P_\mathit{ABD}, P_\mathit{ACD}, P_\mathit{BCD}$ are empty and so $\mathit{ac}=\mathit{ad}=\mathit{bc}=\mathit{bd}=\mathit{cd}=\mathit{abd}=\mathit{acd}=\mathit{bcd}=0$
3. Either $P_\mathit{AB}$ is empty and $\mathit{abc} \in \{0,1,2\}$ or $P_\mathit{ABC}$ is empty and $\mathit{ab} \in \{0,1\}$
4. $\mathit{abcd}$ is maximal

Conclusion

(The meaning of the variable $\mathit{abcd}$ and the other variables consisting of the letters $a,b,c,d$ is defined above)

If $m$ is the maximum possible size of $\mathit{abcd}$ then $m$ satisfies at least one of these systems of equations of nonnegative integer variables for $(u,v)\in \{(0,0), (1,0), (2,0), (0,1), (0,2)\}$:

$$ ab=u\\ abc=v\\ a+ab+abc+m=S\\ b+ab+abc+m=S\\ c+abc+m=S\\ d+m=S\\ a+b+c+d+m=200 $$

For $S=100$ only the system with $(u,v)=(1,0)$ has an integer solutions, and we get $m=66$, and $a=b