GO Classes DPP | GATE CS | Discrete Mathematics| Combinatorics

Answer 1

To find the number of different valid routes, we can reframe the problem as an arrangement of $6$ North moves ($N$) and $8$ East moves ($E$).

We can use the $6$ $N$s to create "gaps" where the $E$s can be placed.

$$ \_ \text{ } N \text{ } \_ \text{ } N \text{ } \_ \text{ } N \text{ } \_ \text{ } N \text{ } \_ \text{ } N \text{ } \_ \text{ } N \text{ } \_ $$

There are $7$ available gaps (including the ends). Let $x_i$ be the number of East moves in the $i$-th gap.

We must place exactly $8$ East moves, so:

$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 = 8$$

The constraint is that we cannot have $3$ East moves in a row. This means each gap can hold at most $\mathbf{2}$ East moves.

So, $0 \le x_i \le 2$ for all $i$.

We can solve this by considering how many gaps have $0$, $1$, or $2$ East moves.

Let $n_0$, $n_1$, and $n_2$ be the number of gaps containing $0$, $1$, and $2$ East moves, respectively.

We have two equations:

1. Total gaps: $n_0 + n_1 + n_2 = 7$

2. Total East moves: $0(n_0) + 1(n_1) + 2(n_2) = 8 \implies n_1 + 2n_2 = 8$

From the first equation, $n_1 = 7 - n_0 - n_2$. Substitute this into the second equation:

$$(7 - n_0 - n_2) + 2n_2 = 8$$

$$7 - n_0 + n_2 = 8 \implies n_2 = n_0 + 1$$

Now we can test all possible integer values for $n_0$ to find our valid cases:

• Case $\mathbf{1}$: $n_0 = 0$

  $n_2 = 1$

  $n_1 = 7 - 0 - 1 = 6$

  Check: $(6 \times 1) + (1 \times 2) = 8$.

  Ways to arrange: $\frac{7!}{0!6!1!} = \mathbf{7}$

• Case $\mathbf{2}$: $n_0 = 1$

  $n_2 = 2$

  $n_1 = 7 - 1 - 2 = 4$

  Check: $(4 \times 1) + (2 \times 2) = 8$.

  Ways to arrange: $\frac{7!}{1!4!2!} = \frac{7 \times 6 \times 5}{2} = \mathbf{105}$

• Case $\mathbf{3}$: $n_0 = 2$

  $n_2 = 3$

  $n_1 = 7 - 2 - 3 = 2$

  Check: $(2 \times 1) + (3 \times 2) = 8$.

  Ways to arrange: $\frac{7!}{2!2!3!} = \frac{7 \times 6 \times 5 \times 4}{4} = \mathbf{210}$

• Case $\mathbf{4}$: $n_0 = 3$

  $n_2 = 4$

  $n_1 = 7 - 3 - 4 = 0$

  Check: $(0 \times 1) + (4 \times 2) = 8$.

  Ways to arrange: $\frac{7!}{3!0!4!} = \frac{7 \times 6 \times 5}{6} = \mathbf{35}$

(If $n_0 = 4$, $n_2 = 5$, the sum of gaps would be at least 9, which is $>7$, so there are no more cases.)

Finally, add the possibilities from all the valid cases together:

$$\text{Total routes} = 7 + 105 + 210 + 35 = \boxed{357}$$

The correct option is A.

Answer 2

in between north we have 7 gaps

_n_n_n_n_n_n_

so now we need to arrange the remaing 8 east moves
we can do it in 1 east or 2 east ways

1x+2y = 8

x y   k=x+y
6 1   7         7C7 = 7
4 2   6         7C6.6C2 = 105
2 3   5         7C5 5C3 = 210
0 4   4         7C4 = 35

7 + 105 + 210 + 35 =  357