The village chatterboxes are exchanging their gossip by phone every day so that any two of them talk to each other exactly once. A certain day, every chatterbox called up at least one of the other chatterboxes. Show that there exist three chatterboxes such that the first called up the second, the second called up the third, and the third called up the first.
Problem
Source: Slovenia National MO 2005 2nd Grade P4
Tags: combinatorics
05.04.2021 06:57
The problem just says that in a directed tournament, where every degree has outdegree at least $1$, prove there exists a directed triangle. First check that if there are less than $4$ vertices, then this is obviously true. Now, pick any 4 vertices, call them $a,b,c,d$. WLOG let $a \rightarrow b, b \rightarrow c $. Now, if $c \rightarrow a$, then $a,b,c$ forms a directed triangle, so $a \rightarrow c$. Since $c$ must have outdegree $1$ at least, $c \rightarrow d$. Now see that either $d \rightarrow a$ or $d \rightarrow b$, but in both cases, a directed triangle is formed. The end
07.04.2021 14:03
I think L567's proof works only if a,b,c,d are the only 4 vertices. If there are more vertices, the requirement that c must have outdegree at least one could be satisfied by some vertex other than d. Obviously this could be fixed by choosing d to be some vertex to which c is directed. But then the same problem applies to vertex d; to satisfy the outdegree condition, it could be directed to some vertex other than a or b. Is that so easily fixed?
07.04.2021 14:34
Oops you're right, my solution doesnt work
07.04.2021 15:25
I'd love to see a 'cool' proof along the lines of L567's argument above. Best I can do is as in following outline: 1. Standard proof that every directed tournament has a Hamiltonian path through each vertex exactly once 2. Consider the 'final' vertex on that path. Since its outdegree is at least one, it must connect to some other vertex. Hence there is a cycle of some n vertices. 3. Standard proof that if there is a cycle of n>3 vertices, there must be a cycle of 3 vertices.