Change
BdMO National Higher Secondary 2014/6
-
- Posts:1007
- Joined:Sat Dec 09, 2017 1:32 pm
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
Change
-
- Posts:1007
- Joined:Sat Dec 09, 2017 1:32 pm
-
- 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
-
- 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