There are $2005$ players in a chess tournament played a game. Every pair of players played a game against each other. At the end of the tournament, it turned out that if two players $A$ and $B$ drew the game between them, then every other player either lost to $A$ or to $B$. Suppose that there are at least two draws in the tournament. Prove that all players can be lined up in a single file from left to right in the such a way that every play won the game against the person immediately to his right.
Problem
Source: MOP 2006 Homework - Black Group
Tags: combinatorics unsolved, combinatorics
19.05.2014 19:32
Let's look at the problem using graph theory. Let's draw an edge oriented from $A$ to $B$ if $A$ beats $B$. We should prove that the maximal oriented path contains all the vertices. Suppose this is not the case, then divide the set of points in two disjoint sets, $U,V$, where $U$ containts the vertices from the maximal path and $V$ the others. Denote the path $A_1 -A_2-..-A_k$. Everybody from $V$ loses or draws with $A_1$ and beats or draws with$A_k$ due to maximality. A player can't have two draws. Suppose this is the case and $A$ draws with $B$ and $C$. Suppose $B$ defeats $C$. Then, for the drawing couple $A,C$, we have a vertex $(B)$ who does not lose with either of $A,C$, impossible. We can't have draws inside $V$ because if $X,Y \in V$ draw, $A_1$ must lose with one of them and we find a longer path ($V-A_1-..-A_k$). Now start from $A_k$. Look if he beats someone from $V$(obviously, it doesn't), pass to $A_{k-1}$. Look if it beats someone from $V$. If he doesn't go to $A_{k-2}$ and so on and if he does, stop.. We have two options: 1. We stop at an $i$ with $A_i$ beating someone from $V$, $X$, which can't have made a draw with $A_{i+1}$ (which exists since $i<k$) by obvious reasons, so $X$ won with $A_{i+1}$, but this way, we can add $X$ to our path, impossible. So, we never stop, which means we reach $A_1$ and nobody won over someone from $V$. But $A_i$ can't lose with someone from $V$, so $A_1$ draws with everybody from $V$, but $A_1$ can have at mots one draw, so $V$ has exactly one vertex, $Y$. $Y$ can't draw with $A_k$ since nobody can draw 2 times, $Y$ can't lose with $A_k$ because in this case we find a longer path, so $A_k$ loses with $Y$. $A_k$ loses with $A_1$, otherwise $Y-A_k -A_1 -A_2-...-A_{k-1}$ is an oriented path containing all the vertices. Now, we have a draw inside $U$ say for $L$ and $M$, then one of $L,M$ has to defeat $V$ (since $V$ can't take any more draws)$, impossible because we are in case 2. So, our assumption was wrong, and we are done.
03.11.2014 06:54
From MariusBocanu's post we know that one person cannot have $2$ draws. Suppose we have $2$ pairs who drew each other $(A,B),(C,D)$. Then from question we can determine that $A\rightarrow C\rightarrow B\rightarrow D\rightarrow A$ (where $X\rightarrow Y$ mean $X$ defeats $Y$), or $A\rightarrow D\rightarrow B\rightarrow C\rightarrow A$. Hence we pick out all $k$ drawing pairs among the $2005$ people and arrange as follow: $(A_1,B_1)....(A_k,B_k)$, such that $A_i\rightarrow A_{i+1}\rightarrow B_i\rightarrow B_{i+1}\rightarrow A_1$ and a non empty group $C$ with the remaining people. First, as $C$ has no draws there must be an oriented path with everyone. Let it be $C_1\rightarrow ....C_l$. Now at $(A_1,B_1)....(A_k,B_k)$ we have two cases. Case 1: $A_k\rightarrow B_1, B_k\rightarrow A_1$. Then there is an oriented cycle $A_1\rightarrow ...A_k\rightarrow B_1\rightarrow ...B_k\rightarrow A_1$. From the question we know that $C_1$ lost to at least one of $A_i,B_j$ (WLOG $A_i$), then our desired oriented path will be $A_{i+1}\rightarrow ...A_k\rightarrow B_1\rightarrow ...B_k\rightarrow A_1\rightarrow ...A_i\rightarrow C_1\rightarrow ....C_l$. Case 2: $A_k\rightarrow A_1, B_k\rightarrow B_1$ (Then $k\geq 3$). WLOG $C_1$ lost to $A_k$ among $(A_k,B_k)$. Then the desired oriented path is $B_3\rightarrow ...\B_k\rightarrow B_1\rightarrow B_2\rightarrow A_1\rightarrow ...A_k\rightarrow C_1\rightarrow ....C_l$.