recategorized by
732 views
5 votes
5 votes

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

  1. $2z+6$
  2. $3z+6$
  3. $2z+8$
  4. $3z+8$
  5. $3z+4$
recategorized by

1 Answer

Best answer
6 votes
6 votes
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.
selected by
Answer:

Related questions

50 votes
50 votes
6 answers
3
Rohith AP asked Dec 13, 2015
5,968 views
Let $n = m!$. Which of the following is TRUE?$m = \Theta (\log n / \log \log n)$$m = \Omega (\log n / \log \log n)$ but not $m = O(\log n / \log \log n)$$m = \Theta (\log...