TIFR CSE 2016 | Part A | Question: 7

Question

Let $S$ be the $4 \times 4$ square grid $\{(x, y): x, y \in \{0, 1, 2, 3\} \}$. A $monotone \: \: path$ in this grid starts at $(0, 0)$ and at each step either moves one unit up or one unit right. For example, from the point $(x, y)$ one can in one step either move to $(x+1, y) \in S$ or $(x, y+1) \in S$, but never leave $S$. Let the number of distinct monotone paths to reach point $(2, 2)$ starting from $(0, 0)$ bt $z$. How many distinct monotone paths are there to reach point $(3, 3)$ starting from $(0, 0)$?

• A. $2z+6$
• B. $3z+6$
• C. $2z+8$
• D. $3z+8$
• E. $3z+4$

Comments

Solution using Dynamic programming approach.

http://www.geeksforgeeks.org/count-possible-paths-top-left-bottom-right-nxm-matrix/

For $M*N$ Rectangular to reach (M,N) from (0,0) total possible ways are $\binom{M+N}{N}$

which means $\frac{(M+N)!}{M!*N!}$

Answer 1

Ans : C] 2z+8

Clearly a path of the desired type must consist of 3 moves to right and 3 moves to up.

Therefore, each such path can be represented by a bit string of 3 0’s and 3 1’s, with the 0’s representing moves to the right and the 1’s representing moves up.

The number of bit strings of length 3+3 containing exactly 3 0’s and 3 1’s is $\left ( \frac{6!}{3! * 3!} \right )$ = 20.

The number of bit strings of length 2+2 containing exactly 2 0’s and 2 1’s is z = $\left ( \frac{4!}{2! * 2!} \right )$ = 6.

Now, by substituting z=6 in options, only C gives 20.

Comments

very nice approach!