BdMO National Higher Secondary 2014/6

Discussion on Bangladesh Mathematical Olympiad (BdMO) National
User avatar
samiul_samin
Posts: 1007
Joined: Sat Dec 09, 2017 1:32 pm

BdMO National Higher Secondary 2014/6

Unread post by samiul_samin » Sat Feb 17, 2018 8:03 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
Put' belongs to' sign at the place of 'subset sign'

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

Re: BdMO National Higher Secondary 2014/6

Unread post by samiul_samin » Sat Feb 17, 2018 8:03 pm

Hint
There is no draw!

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

Re: BdMO National Higher Secondary 2014/6

Unread post by samiul_samin » Tue Feb 20, 2018 4:07 pm

I am giving my solution.If there is any gap in this proof,please make it clear to me.
Solution
Suppose lebel the chairs from $1$ to $n$.We have to prove that we can get them sit in these lebeled chairs so that the players sit in the $i$ no chair beats $i+1$ for each $i\in${$1,2,3,...,n$}
The player number of chess tournament is $n$.
Total number of mathes=$n(n+1)/2$
Every player plays $n-1$ matches.
Suppose,a particular player of these $n$ players,played $n-1$ mathes and

Win $n-1$ matches $\rightarrow$ will take the leftmost seat
Win $n-2$ matches $\rightarrow$ will take the next chair placed at right after previous step
Win $n-3$ matches $\rightarrow$ will take the next chair placed at right after previous step
.
.
.
.
.
.
.
.
.
Win $1$ match $\rightarrow$ will take the next chair placed at right after previous step
Win $0$ matches $\rightarrow$ will take the rightmost chair

It can be done for every players.If any two players share same number of match winning,the player who lost at the game of those two players will take the chair just placed at the right of the particular those two players match winner.
So,it is always possible to lebel them according to the condition of the question.[Proved]
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

Unread post by Absur Khan Siam » Mon Mar 05, 2018 11:16 pm

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

Unread post by Absur Khan Siam » 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)
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

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

Re: BdMO National Higher Secondary 2014/6

Unread post by samiul_samin » 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?

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

Re: BdMO National Higher Secondary 2014/6

Unread post by Absur Khan Siam » Wed Mar 07, 2018 6:28 pm

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

Post Reply