## BdMO National Higher Secondary 2014/6

samiul_samin
Posts: 1007
Joined: Sat Dec 09, 2017 1:32 pm

### BdMO National Higher Secondary 2014/6

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

samiul_samin
Posts: 1007
Joined: Sat Dec 09, 2017 1:32 pm

### Re: BdMO National Higher Secondary 2014/6

Hint

samiul_samin
Posts: 1007
Joined: Sat Dec 09, 2017 1:32 pm

### Re: BdMO National Higher Secondary 2014/6

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.

Absur Khan Siam
Posts: 65
Joined: Tue Dec 08, 2015 4:25 pm
Location: Bashaboo , Dhaka

### Re: BdMO National Higher Secondary 2014/6

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.
Last edited by Absur Khan Siam on Wed Mar 07, 2018 10:39 pm, edited 4 times in total.
"(To Ptolemy I) There is no 'royal road' to geometry." - Euclid

Absur Khan Siam
Posts: 65
Joined: Tue Dec 08, 2015 4:25 pm
Location: Bashaboo , Dhaka

### Re: BdMO National Higher Secondary 2014/6

Sorry, the solution above is wrong. I will edit it as soon as possible.(as I can't delete it now)
UPD: : solution edited.
Last edited by Absur Khan Siam on Wed Mar 07, 2018 6:27 pm, edited 2 times in total.
"(To Ptolemy I) There is no 'royal road' to geometry." - Euclid

samiul_samin
Posts: 1007
Joined: Sat Dec 09, 2017 1:32 pm

### Re: BdMO National Higher Secondary 2014/6

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?

Absur Khan Siam
Posts: 65
Joined: Tue Dec 08, 2015 4:25 pm
Location: Bashaboo , Dhaka

### Re: BdMO National Higher Secondary 2014/6

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)
"(To Ptolemy I) There is no 'royal road' to geometry." - Euclid