BdMO National Higher Secondary 2014/9

[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.

[samiul_samin]

Hint

Use Catalan Recurrence.
Use it twice.

Answer

$2$× Catalan number of $(n)$

[samiul_samin]

Catalan number

https://en.m.wikipedia.org/wiki/Catalan_number

[samiul_samin]

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

[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.

[samiul_samin]

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]

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]

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