Grid Walking # 1 \#1

Consider the folowing 10 × 7 10 \times 7 grid ,

Joe wants to go from ( 0 , 0 ) (\, 0,0 )\, to ( 10 , 7 ) (\, 10,7 )\, . At any point he can only go one unit up or one unit right

Now Joe can go to ( 10 , 7 ) (\, 10,7 )\, in multiple ways. Each path from ( 0 , 0 ) (\, 0,0 )\, to ( 10 , 7 ) (\, 10,7 )\, is a set of points that have been covered by Joe ( in a particular order like shown below) For eg.

( 0 , 0 ) (\, 0,0 )\, ( 0 , 1 ) (\, 0,1 )\, ( 0 , 2 ) (\, 0,2 )\, ( 0 , 3 ) (\, 0,3 )\, ( 0 , 4 ) (\, 0,4 )\, ( 0 , 5 ) (\, 0,5 )\, ( 0 , 6 ) (\, 0,6)\, ( 1 , 6 ) (\, 1,6 )\, ( 2 , 6 ) (\, 2,6 )\, ( 3 , 6 ) (\, 3,6 )\,

( 4 , 6 ) (\, 4,6 )\, ( 5 , 6 ) (\, 5,6 )\, ( 6 , 6 ) (\, 6,6 )\, ( 7 , 6 ) (\, 7,6 )\, ( 8 , 6 ) (\, 8,6 )\, ( 9 , 6 ) (\, 9,6 )\, ( 10 , 6 ) (\, 10,6 )\, ( 10 , 7 ) (\, 10,7 )\, is a path from ( 0 , 0 ) (\, 0,0 )\, to ( 10 , 7 ) (\, 10,7 )\,

Now the rule is that no two points ( A , B ) (\, A,B )\, and ( C , D ) (\, C,D)\, in this set of points ( a path ) should satisfy these properties ( both ) A = C A=C and B D > 1 B-D>1

how many ways are there to go from ( 0 , 0 ) (\, 0,0 )\, to ( 10 , 7 ) (\, 10,7 )\, ?


The answer is 330.

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

Chan Tin Ping
Nov 4, 2017

Let > means Joe go right 1 unit, ^ means Joe go up 1 unit. The special condition of this question is as same as Joe cannot walk up twice consecutive. Hence, the answer is equivalent as the ways to arrange 10 > and 7 ^ , such that no 2 consecutive ^ .

First, separate all 7 ^ ,which means put 1 > in two consecutive ^ . Hence, we got the basic arrangement ^>^>^>^>^>^>^ (we already use 6 >, which left 4 >.) Now, we need to arrange the 4 >. Let see some examples, >>^>>^>^>^>^>^>^>, ^>>>^>>^>^>^>^>^>. We can find that we make 7 ^ as 7 dividing line. Hence, the ways of arrangement is equal to ways of arrange 4 > into 8 distinct bins.

Hence, the answer is ( 4 + 8 1 4 ) = 330 \binom{4+8-1}{4}=330

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...