BdMO Online Forum

There are $n$ players in a chess tournament.Every player plays every other player exactly once and there are no draws.Prove that ,the players can be lebeled $1,2,... ... ...,n$ so that $i$ beats $i+1$ for each $i \subset$ {$1,2,3,.........,n-1$}
Change

I am giving my solution.If there is any gap in this proof,please make it clear to me.
Solution This is also the problem of BdMO National Secondary 2014/9.

Let us construct a directed graph $T$ consisting $n$ nodes where each node represents a player.
An edge $x \rightarrow y$ represent player $x$ has lost $y$.
Thus, this graph consists of $\binom{n}{2}$ edges.

"The players can be labeled $1,2,.......,n$ so that $i$ beats $i+1$" is equivalent to "The graph contains such a path that each node is visited exactly once".

We can prove it by induction on $n$.
For $n \leq 2$, it is clear that such path exists.
Suppose that the statement holds for $n$ and and consider a tournament graph $T_1$ of $n+1$ vertices.
We select a node $v_0$ of $T_1$ and consider a directed path among $v_1, v_2 , v_3, ..... , v_n$ in $T_1 \setminus {v_0}$.
According to the inductive hypothesis, such path exists.
Let the set of vertex that comes to $v_0$ is $V_{in}$ and the set of vertex that leaves $v_0$ is $V_{out}$.
If $|V_{in}| = 0$ , we set $v_0$ at the beginning of the path.
if $|V_{out}| = 0$ , we set $v_0$ at the end of the path.
Otherwise, if $|V_{in}| \neq 0$ and $|V_{out}| \neq 0$, it turns out that there exists at least two adjacent vertices $v_i , v_i+1$ such that the edges $v_i \rightarrow v_0$ and $v_0 \rightarrow v_i+1$ exists.
Thus it is possible to construct such path for $n+1$.

Therefore , by induction , it is possible for all $n$.

Hence, it is always possible to label the players according to the given condition.

Sorry, the solution above is wrong. I will edit it as soon as possible.(as I can't delete it now)
UPD: : solution edited.

Absur Khan Siam wrote: ↑

Mon Mar 05, 2018 11:27 pm

Sorry, the solution above is wrong. I will edit it as soon as possible.(as I can't delete it now)

Is my solution also wrong?

samiul_samin wrote: ↑

Mon Mar 05, 2018 11:54 pm

Absur Khan Siam wrote: ↑

Mon Mar 05, 2018 11:27 pm

Sorry, the solution above is wrong. I will edit it as soon as possible.(as I can't delete it now)

Is my solution also wrong?

Not yours, my one was wrong.(now edited)