Page 1 of 1

BdMO National Higher Secondary 2014/9

Posted: Sat Feb 17, 2018 6:53 am
by samiul_samin
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.

Re: BdMO National Higher Secondary 2014/9

Posted: Sat Feb 17, 2018 8:55 pm
by samiul_samin
Hint
Use Catalan Recurrence.
Use it twice.
Answer
$2$× Catalan number of $(n)$

Re: BdMO National Higher Secondary 2014/9

Posted: Sat Feb 17, 2018 8:57 pm
by samiul_samin

Re: BdMO National Higher Secondary 2014/9

Posted: Sat Feb 17, 2018 10:49 pm
by samiul_samin
If my answer is wrong, please write the right answer.

Re: BdMO National Higher Secondary 2014/9

Posted: Sun Feb 18, 2018 9:28 am
by ahmedittihad
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.

Re: BdMO National Higher Secondary 2014/9

Posted: Sun Feb 18, 2018 9:30 am
by samiul_samin
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$?

Re: BdMO National Higher Secondary 2014/9

Posted: Sat Feb 24, 2018 11:43 pm
by Tasnood
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 :(

Re: BdMO National Higher Secondary 2014/9

Posted: Thu Feb 21, 2019 5:02 pm
by samiul_samin
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