If we start at position $(1,1)$ (bottom-left) in a $(n,m)$-sized grid, and if we can only move one step up or one step right at a time, in how many ways can we reach $(n,m)$ (top-right) if we have to turn exactly $3$ times? Basically problem $3 (c)$ here.
My attempt: Assume for now that $n=4,m=5$. We have to make $3$ up moves and $4$ right moves. We're looking for all ways to write out $3$ $U$'s and $4$ $R$'s such that they form $4$ alternating groups (i.e. alternating between up group and down group). For example, $RRR-UU-R-U$. Division into $4$ groups ensures that we make $3$ turns.
That means $4$ $R$'s will be split into $2$ groups (in the above example, $RRR$ and $R$), and same with the $3$ $U$'s. There are $(n-1)=3$ ways to split $R$'s into 2 groups, and $(m-1)=2$ for $U$'s. The number of ways to arrange these 4 groups in an alternating fashion would be $2*\binom21*\binom21=8$. I guess the only remaining issue is what if either of $m,n$ are even? Since $n=4$, we're overcounting for the cases when $R's$ are split into $2$ groups of $2$ each. How do I account for this?
Also, most of other problems in that assignment aren't too difficult so I suspect even this one might have an elegant, simple solution with a final formula that's not too complicated. My attempt seems like too much work – would appreciate help.
Best Answer
In order for this to happen the robot must go right-up-right-up or up-right-up-right. These two situations are mirror images of each other, so we will concern ourselves with only right-up-right-up and then double it up to get the result.
The only things that matter is when we stop going right the first time, and when we stop going up the first time. It is clear that we can take anywhere from $1$ to $m-2$, inclusive, steps while going right the first time: if we took less, then we wouldn't have gone right in the first place, and if we took more we wouldn't have room to go right in the second part. This gives us $m-2$ possible ways to go right the first time.
Identical logic gives us $n-2$ possible ways to go up the first time.
Then, our moves for the second attempts at going right and are forced: both take exactly what remains.
So our final answer is $2\cdot(m-2)\cdot(n-2)\cdot1\cdot1 = 2(m-2)(n-2)$.