In Alaska there are three caves with $n$ bears in each of them. They are friendly bears, so every bear from any of the caves is on speaking terms with at least $n+1$ bears from the other two caves. Show that there are three bears, no two from the same cave, who are on speaking terms with each other.
I want to say that this is some version of the handshake lemma, but not sure where I want to start.
To simplify the exposition, I shall say that two bears from different caves are friends iff they are on speaking terms with each other. Assume that there is no three bears which are mutually friends. Choose a bear $b$ who has a maximal number $m$ of friends from one of the other two caves. Let $B$ denotes the bear $b$’s cave and $A$ denotes the cave with these $m$ friends of $b$. Let $c$ be a $b’$s friend from the cave $C$. Then $c$ can have at most $n-m$ friends in cave $A$. Therefore $c$ has at least $n+1-(n-m)=m+1$ friends in cave $B$, a contradiction.