There are three colleges in a town. Each college has $n$ students. Any student of any college knows $n+1$ students of the other two colleges. Prove that it is possible to choose a student from each of the three colleges so that all three students would know each other.
Problem
Source:
Tags: combinatorics, maximum and minimum
08.04.2011 20:45
let A be the person who knows more people from exactly one of two other schools and the problem will be solved.
09.04.2011 03:15
Yes indeed that is what I used in my solution. Suppose the schools are $A,B,C$. Let $M$ be the maximal number of students all in one school knowing some same person. Suppose $v$ is in school $B$ and knows $M$ people from $C$. Clearly $v$ knows someone from $A$, call him $w$. But then $w$ cannot know any person from $C$ that $v$ also knows otherwise we get a triangle. Hence he knows at most $n-M$ people from $C$. And hence knows at least $n+1-(n-M)=M+1$ people from $B$ which contradicts the maximality of $M$.
08.09.2011 09:25
Could someone explain how does contradicting the maximality of M proves that it is possible to choose a student from each of the three colleges so that all three students would know each other, please?
09.09.2011 16:43
slightly unrelated question but, in this setting, it is true (and if so how would it be proven) that there exists two colleges out of the three so that every student from one college can be partnered off with a student from the other college (ofc the partners must know each other)?
21.03.2024 23:26
We uploaded our solution https://calimath.org/pdf/FranceTST2002-4.pdf on youtube https://youtu.be/6yfpahKs7SE.
22.03.2024 11:15
This question was also asked here with a little bit different phrasing https://artofproblemsolving.com/community/u537207h2623380p29627990 and here is my solution: https://artofproblemsolving.com/community/c6h2623380p29627990 a good extremal problem