Walking on a grid

George and John walk along the lines of a 3 × 3 3 \times 3 grid with George (labelled 'G') starting from the bottom-left corner and John (labelled 'J') starting from the top-right corner. George can only walk to the top or to the right while John can only walk to the bottom or to the left.

Find the total number of ways in which they can meet at the lattice points shown in the grid.

Clarification :-

  • The speeds of George and John are not necessarily equal.
  • It is possible for George not to move at all and John to travel along a route from the entire grid so that they meet at G. Conversely, they can also meet at J, if John doesn't move and George travel a route from the grid shown.

This problem is original.


The answer is 140.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Ashish Menon
Oct 22, 2017

Lets take the grid into co-ordinate plane as shown below.

The diagnol shown is y = x y = x . Observe that the number of points required for reaching at lattice points which are images with respect to each other through this line have the same value. So, we would find the number of ways of reaching the points for which y > x y > x only and then double them in the final answer for the points satisfying y < x y < x . The points lying on y = x y = x need to be counted only once.

The formula which is going to be used throughout this question is:- The number of ways of crossing a m × n m × n grid = ( m + n ) ! m ! × n ! \dfrac {(m + n)!}{m! × n!}

For point A, George can travel only through the straight line AG. John also can only travel through JA. So, the number of ways is 1 \color{#D61F06}{1} .

For point B, George can travel only along BG, while John can swap region ABPJ. The number of ways of crossing this is 4 ! 3 ! \dfrac {4!}{3!} . So, number of ways = 1 × 4 ! 3 ! = 4 1 × \dfrac {4!}{3!} \ = \ \color{#D61F06}{4} .

For point C, George can travel only along CG, while John can swap region ACOJ. The number of ways of crossing this is 5 ! 3 ! × 2 ! \dfrac {5!}{3! × 2!} . So, number of ways = 1 × 5 ! 3 ! × 2 ! = 10 1 × \dfrac {5!}{3! × 2!} \ = \ \color{#D61F06}{10} .

For point D, George can swap region ADKG i.e. 4 ! 3 ! \dfrac{4!}{3!} ways, while John can only travel along DJ. So, number of ways = 4 ! 3 ! × 1 = 4 \dfrac {4!}{3!} × 1 \ = \ \color{#D61F06}{4} .

For, point E, George can swap region BGKE i.e 3 ! 2 ! \dfrac {3!}{2!} ways while John can swap region DEPJ i.e, 3 ! 2 ! \dfrac {3!}{2!} ways. So, number of ways = 3 ! 2 ! × 3 ! 2 ! = 9 \dfrac {3!}{2!} × \dfrac {3!}{2!} \ = \ \color{#D61F06}{9} .

For point F, George can swap region AFLG i.e. 5 ! 3 ! × 2 ! \dfrac{5!}{3! × 2!} ways, while John can only travel along FJ. So, number of ways = 5 ! 3 ! × 2 ! × 1 = 10 \dfrac {5!}{3! × 2!} × 1 \ = \ \color{#D61F06}{10} .

So, for points y > x y > x , total ways = 1 + 4 + 10 + 9 + 10 = 38 1 + 4 + 10 + 9 + 10 \ = \ \color{#3D99F6}{38} .
Therefore, for points y < x y < x , total ways = 38 \color{#3D99F6}{38} .

For, point G, George needn't move while John can swap region AGNJ i.e, 6 ! 3 ! × 3 ! \dfrac {6!}{3! × 3!} ways. So, number of ways = 1 × 6 ! 3 ! × 3 ! = 20 1× \dfrac {6!}{3! × 3!} \ = \ \color{#D61F06}{20} .
For, point H, George can swap region CGKH i.e 2 ! 1 ! × 1 ! \dfrac {2!}{1! × 1!} ways while John can swap region DEPJ i.e, 4 ! 2 ! × 2 ! \dfrac {4!}{2! × 2!} ways. So, number of ways = 2 ! × 4 ! 2 ! × 2 ! = 12 2! × \dfrac {4!}{2! × 2!} \ = \ \color{#D61F06}{12} .

For, point I, number of ways is similar to that of H (by symmetry) = 12 \color{#D61F06}{12} .

For, point J, number of ways is similar to that of G (by symmetry) = 20 \color{#D61F06}{20} .

So, for points y = x y = x , total ways are 20 + 12 + 12 + 20 = 64 20 + 12 + 12 + 20 \ = \ \color{#3D99F6}{64} .

So, the net number of ways = 38 + 38 + 64 = 140 38 + 38 + 64 \ = \ \color{#69047E}{\boxed{140}} .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...