## BdMO National Higher Secondary 2014/9

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

### BdMO National Higher Secondary 2014/9

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.

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

### Re: BdMO National Higher Secondary 2014/9

Hint

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

### Re: BdMO National Higher Secondary 2014/9

Catalan number

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

### Re: BdMO National Higher Secondary 2014/9

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

### Re: BdMO National Higher Secondary 2014/9

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.

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

### Re: BdMO National Higher Secondary 2014/9

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$?

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

### Re: BdMO National Higher Secondary 2014/9

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

I think I am wrong

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

### Re: BdMO National Higher Secondary 2014/9

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 (3.24 KiB) Viewed 1952 times