Change
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,.........,n1$}
Change
Change
 samiul_samin
 Posts: 1007
 Joined: Sat Dec 09, 2017 1:32 pm
 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.
Solution

 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.
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

 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.
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
Is my solution also wrong?Absur Khan Siam wrote: ↑Mon Mar 05, 2018 11:27 pmSorry, the solution above is wrong. I will edit it as soon as possible.(as I can't delete it now)

 Posts: 65
 Joined: Tue Dec 08, 2015 4:25 pm
 Location: Bashaboo , Dhaka
Re: BdMO National Higher Secondary 2014/6
Not yours, my one was wrong.(now edited)samiul_samin wrote: ↑Mon Mar 05, 2018 11:54 pmIs my solution also wrong?Absur Khan Siam wrote: ↑Mon Mar 05, 2018 11:27 pmSorry, the solution above is wrong. I will edit it as soon as possible.(as I can't delete it now)
"(To Ptolemy I) There is no 'royal road' to geometry."  Euclid