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.BdMO National Higher Secondary 2014/9
-
- Posts:1007
- Joined:Sat Dec 09, 2017 1:32 pm
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.
-
- Posts:1007
- Joined:Sat Dec 09, 2017 1:32 pm
Re: BdMO National Higher Secondary 2014/9
Hint
Answer
-
- Posts:1007
- Joined:Sat Dec 09, 2017 1:32 pm
Re: BdMO National Higher Secondary 2014/9
Catalan number
-
- Posts:1007
- Joined:Sat Dec 09, 2017 1:32 pm
Re: BdMO National Higher Secondary 2014/9
If my answer is wrong, please write the right answer.
- ahmedittihad
- 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.
-
- Posts:1007
- Joined:Sat Dec 09, 2017 1:32 pm
Re: BdMO National Higher Secondary 2014/9
I proved it for $n=1,2,3,4$.What is the way to prove it for every $n$?ahmedittihad wrote: ↑Sun Feb 18, 2018 9:28 amYour 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
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
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
-
- 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.