At least $3$ players take part in a tennis tournament. Each participant plays exactly one match against each other participant. After the tournament has ended, we find out that each player has won at least one match. (There are no ties in tennis). Show that in the tournament, there was at least one trio of players $A,B,C$ such that $A$ beat $B$, $B$ beat $C$, and $C$ beat $A$.
Problem
Source: Argentina TST 2011, Problem 5
Tags: combinatorics proposed, combinatorics, graph theory
31.08.2014 20:28
The tournament is not transitive, so it contains a cycle. Any cycle of length longer than 3 has a chord; no matter which way this chord is directed, it divides the cycle into two pieces, one of which is a cycle of strictly shorter length than the original cycle. (Surely this is a classic result and has appeared before, but I was not able to find it with a cursory search.)
11.04.2015 13:43
Yes JBL surely. However I did this without graphs.Assume that a player $x$ has lost the maximum number of times,say $j$ times.By problem there exists a player $y$ whom player $x$ has defeated.If the problem condition is to be violated then every player who has defeated $x$ has also defeated $y$.Then $y$ was defeated atleast $j+1$ times,contradicting our assumption that $x$ has lost the maximum number of times.
02.08.2018 12:49
It's well known that every directed graph with indegree(outdegree) of every vertex at least $1$ contains a cycle.Also it is well known that if a tournoment has a directed cycle has a directed triangle so we are done.