Problem

Source: Stars of Mathematics 2007, Day 1, Problem 4

Tags: game, graph theory, discrete maths, combinatorics



At a table tennis tournament, each one of the $ n\ge 2 $ participants play with all the others exactly once. Show that, at the end of the tournament, one and only one of these propositions will be true: $ \text{(1)} $ The players can be labeled with the numbers $ 1,2,...,n, $ such that $ 1 $ won $ 2, 2 $ won $ 3,...,n-1 $ won $ n $ and $ n $ won $ 1. $ $ \text{(2)} $ The players can be partitioned in two nonempty subsets $ A,B, $ such that whichever one from $ A $ won all that are in $ B. $