A class of 32 students is organized in 33 teams. Every team consists of three students and there are no identical teams. Show that there are two teams with exactly one common student.
The PHP as I know is like, there are 6 students and 5 groups, there must be a group that has two students according to the PHP.
How can solve the question by using PHP?
Best Answer
You take a map $f$ from the 33 teams to the 32 students, where you map each team to a student in that team. By the PHP there is a student to which two teams are mapped, so we have two teams with a student in common, but they might also have two students in common (not three because then they would be identical). This we can prove by contradiction.
So assume that we only have teams with two players in common. So we have team $T_1 = \{a,b,c\}$ and $T_2 = \{a,b,d\}$ (here $a,b,c,d$ are students) now we can change the map $f$ by setting $f(T_1) = c$. Again we have, by PHP, two teams that have a player in common.
If those two teams are different from $T_1,T_2$ change $f$ the same way we did there. If one of our teams with a team in common is, $w.l.o.g. T_1$ or $T_2$ (if it is another team where we changed the map it goes the same way) it has a player in common with a team $T_3$, by assumption they have two players in common, but then $T_3$ also has a player in common with $T_2$ and by assumption again two players in common so $w.l.o.g. T_3 = \{b,c,d\}$ change $f$ s.t. $f(T_2) = a,f(T_3) = b$
And again continue changing $f$ as described in the corresponding situations. If we now get a team $T_4$ with a player in common with either $T_1,T_2,T_3$ then again $T_4$, by assumption has to have two players in common with all three teams, but not equal, so $T_4 = \{a,c,d\}$ and change $f(T_4) = d$. Now no other team can have a player $a,b,c,d$ because by assumption this team would have to have two players in common with three of the four teams and then be equal to the fourth of the four teams, which can't be. And the four teams will never be mapped to the same player either, because of how we changed $f$.
So we can remove the four teams and $a,b,c,d$ from both domain and codomain of $f$ and still have a well defined function from 29 teams to 28 players and not compromise our PHP, if we continue this, we get 25 teams and 24 students, and so on, until we have 1 team and 0 students, which is not possible. Therefor our assumption that teams can only have two students in common is false.
Now we only have to show that there actually is a possibility to choose 33 teams that are all different. For that just take the teams $T_1,...,T_{33}$ and the students $s_1,...,s_{32}$ take for $i<31$ take $T_i = \{s_i,s_{i+1},s_{i+2}\}$ and $T_{31} = \{s_{31},s_{32},s_{1}\}$,$T_{32} = \{s_{32},s_{1},s_{2}\}$,$T_{33} = \{s_{1},s_{3},s_{4}\}$ then clearly no two teams are equal.