Willy Avoids Fences

Willy lives at the origin and is trying to go to school at Maya Angelou Elementary, which is located at ( 6 , 4 ) (6,\,4) . He needs to get to school by making successive movements one unit to the right or one unit up.

Unfortunately, the evil businessman Rockefeller Tycoon has put up fences between ( 1 , 1 ) (1,\,1) and ( 2 , 1 ) (2,\,1) and between ( 3 , 4 ) (3,\,4) and ( 4 , 4 ) (4,\,4) . Willy can no longer move along those paths.

In how many ways can Willy get to school?


The answer is 113.

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.

2 solutions

Saadmaan Sakib
Jul 11, 2016

The problem statement itself has one major error I guess.

He needs to get to school by making successive movements one unit to the left or one unit up.

It should be one unit to the right or one unit up , because otherwise,it's impossible to go to the topmost right corner of the grid from the origin.

And the rest is simple. First count the number of ways from (0,0) to (6,4) . It should be 10C4 = 210. Then,count the number of ways from (0,0) to (1,1) and (2,1) to (6,4) . It should be 2C1 7C3 = 70. Then,count the number of ways from (0,0) to (3,4) and (4,4) to (6,4) . It should be 7C3 2C0 = 35. Then,count the number of ways from (0,0) to (1,1) and (2,1) to (3,4) and (4,4) to (6,4) . It should be 2C1 4C1 2C0 = 8,which should be subtracted.

Hence,the final count is = 210-(70+35-8) = 113

Problem statement updated, thanks!

Henry Maltby - 4 years, 11 months ago
Henry Maltby
Jun 10, 2016

There are ( 10 6 ) = 210 \binom{10}{6} = 210 ways for Willy to get from ( 0 , 0 ) (0,\,0) to ( 6 , 4 ) (6,\,4) that go through either wall (possibly both , possibly neither ).

There are ( 2 1 ) ( 7 3 ) = 2 35 \binom{2}{1} \cdot \binom{7}{3} = 2 \cdot 35 ways for Willy to get from ( 0 , 0 ) (0,\,0) to ( 6 , 4 ) (6,\,4) that go through the first wall.

There are ( 7 3 ) ( 2 0 ) = 35 1 \binom{7}{3} \cdot \binom{2}{0} = 35 \cdot 1 ways for Willy to get from ( 0 , 0 ) (0,\,0) to ( 6 , 4 ) (6,\,4) that go through the second wall.

There are ( 2 1 ) ( 4 1 ) ( 2 0 ) = 2 4 1 \binom{2}{1} \cdot \binom{4}{1} \cdot \binom{2}{0} = 2 \cdot 4 \cdot 1 ways for Willy to get from ( 0 , 0 ) (0,\,0) to ( 6 , 4 ) (6,\,4) that go through both walls.

Therefore, there are 210 2 35 35 1 + 2 4 1 = 210 70 35 + 8 = 113 210 - 2 \cdot 35 - 35 \cdot 1 + 2 \cdot 4 \cdot 1 = 210 - 70 - 35 + 8 = \boxed{113} ways for Willy to get from ( 0 , 0 ) (0,\,0) to ( 6 , 4 ) (6,\,4) that go through neither walls.

What is the formula used to calculate the paths that go through both walls. I've checked the wiki, and no general formula is stated.

Djordje Veljkovic - 4 years, 4 months ago

Log in to reply

The principle is called The principle of inclusion and exclusion

Abhisek Panigrahi - 3 years, 7 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...