Student Network


In a school, there are $5$ classrooms. Each student in a classroom knows exactly one student from each of the other $4$ classrooms. Prove that the number of students in each classroom is exactly the same.

(Assume if student $A$ knows student $B$, then student $B$ also knows student $A$)


Source: BdMO 2017 National Junior P7


Proof Based Problems  


  4 Upvotes                    0 Downvotes


Solution

Disclaimer: The solutions we've shared are just one exciting approach, and there are surely many other wonderful methods out there. We’d love to hear your alternative solutions in the community thread below, so let's keep the creativity flowing!

For the sake of contradiction, assume that $2$ classrooms have different number of students.

Let the classrooms be $A,B$ and let the number of students in $A$ be $a$ and the number if students in $B$ be $b$.

Without loss of generality, $a>b$.


For each student in $A$, there is one student in $B$ such that they know each other. Using Pigeon Hole Principle, there are $2$ students in $A$ such that they know the same person from $B$.


So, $B$ knows $2$ person from $A$. This contradicts the fact that each student knows exactly one student from each classroom. Hence, it is proved that all classroom has equal number of students.

This is a proof based problem added for learning purposes and does not accept submissions.

You can view the solution by clicking on the solution tab.