BdMO National Higher Secondary 2014/9

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/9

Unread post by samiul_samin » Sat Feb 17, 2018 6:53 am

Screenshot_2018-02-17-06-47-29-1.png
Suppose that,you are on the left most bottom point of a $n\times n$ grid.You have to reach the rightmost and topmost point.But the rule is you can move just only toward the upper or right direction.Can't move down or to the left.Ans as there are mines at the squares which are along diagonal you can't go these places too.Determine,how many ways are there to reach the destination.

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

Re: BdMO National Higher Secondary 2014/9

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

Hint
Use Catalan Recurrence.
Use it twice.
Answer
$2$× Catalan number of $(n)$


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

Re: BdMO National Higher Secondary 2014/9

Unread post by samiul_samin » Sat Feb 17, 2018 10:49 pm

If my answer is wrong, please write the right answer.

User avatar
ahmedittihad
Posts: 181
Joined: Mon Mar 28, 2016 6:21 pm

Re: BdMO National Higher Secondary 2014/9

Unread post by ahmedittihad » Sun Feb 18, 2018 9:28 am

Your answer is right, but you have to prove this yourself. Just stating that it's a case of the catalan recurrence won't work.
Frankly, my dear, I don't give a damn.

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

Re: BdMO National Higher Secondary 2014/9

Unread post by samiul_samin » Sun Feb 18, 2018 9:30 am

ahmedittihad wrote:
Sun Feb 18, 2018 9:28 am
Your answer is right, but you have to prove this yourself. Just stating that it's a case of the catalan recurrence won't work.
I proved it for $n=1,2,3,4$.What is the way to prove it for every $n$?

User avatar
Tasnood
Posts: 73
Joined: Tue Jan 06, 2015 1:46 pm

Re: BdMO National Higher Secondary 2014/9

Unread post by Tasnood » Sat Feb 24, 2018 11:43 pm

It is easy to say that finding the number of ways means finding the number of strings. If we denote the upper move with $U$ and the right move with $R$, we have $nU$ and $nR$ to create the dominated strings.
At first, we assume there is no condition of mines. Then we have $2n$ places to arrange the $U$ and $R$. We can arrange $U$ in ${2n} \choose n$ ways. $R$ can be placed in $n$ places in $n \choose n$=$1$ ways. So the answer without restriction is $2n \choose n$

But if we take the first two terms $RU$ or $UR$, we will obviously pass through the first mine. This should be excluded. Thus,
$RU...$ $\Rightarrow$ There are $2n-2$ gaps and $(n-1)U$. So the number of arrangements=${2n-2}\choose{n-1}$. Same for $UR...$

Samely, if we take the first four terms $RRUU$ or $UURR$ [We won't take $RURU$ because it is the continuation of $RU$ counted before], we will go through the second mine. Thus,
$RRUU... \Rightarrow$ There are $2n-4$ gaps and $(n-2)U$. So the number of arrangements =${2n-4}\choose{n-2}$. Same for $UURR...$

At last, taking $(n-1)U$ and $(n-1)R$, we get: $UUU...RRR...\Rightarrow$ There are $2$ gaps and one $U$. So the number of arrangements= $2\choose1$. Also for $RRR...UUU...$

In this way, total number of arrangments will be:
${2n \choose n}-2\times {{2n-2}\choose{n-1}}-2\times {{2n-4}\choose{n-2}}-...-2\times2$; That we wanted :oops:

I think I am wrong :(

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

Re: BdMO National Higher Secondary 2014/9

Unread post by samiul_samin » Thu Feb 21, 2019 5:02 pm

samiul_samin wrote:
Sat Feb 17, 2018 6:53 am

Suppose that,you are on the left most bottom point of a $n\times n$ grid.You have to reach the rightmost and topmost point.But the rule is you can move just only toward the upper or right direction.Can't move down or to the left.Ans as there are mines at the squares which are along diagonal you can't go these places too.Determine,how many ways are there to reach the destination.
Screenshot_2019-02-21-17-01-22-1.png
Screenshot_2019-02-21-17-01-22-1.png (3.24 KiB) Viewed 1953 times

Post Reply