An ant wishes to travel from point A to point B along the black lines in the maze shown below. The ant can only either travel upwards and rightwards, and cannot cross any of the grey zones in the maze. Calculate the number of ways the ant can travel between the two points.

*
Clarification: The ant travels along the black lines and not along the white squares as a whole. After all, it starts and ends at two predetermined points A & B (which aren't squares).
*

*
This problem is part of the set
2015 Countdown Problems
.
*

The answer is 1560.

**
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.

what do u mean by this (1x6x17 + 1 ways+ 17)ways please explain

Rishabh Jain
- 6 years, 6 months ago

Log in to reply

the first way you have 8 possible ways to turn right

7 of them will lead you to 17 possible ways up and the last one has only one way to the end so it is (17x7 + 1)

the second way you have 6 possible ways up

5 of them leads to 6 possible ways right which 5 of them will lead to 13 possible ways up to end while the last has one one way. and the last possible way up leads to 13 possible ways up to end so it is (5x6x13 + 5 + 13)

and so on

mohamed mohsen
- 6 years, 6 months ago

How is it that you can multiply it out like that? Because there are five paths the ant can take I got 5 for my answer.

Ashley Clegg
- 6 years, 6 months ago

Log in to reply

It is "travel along the black lines" not the white blocks

mohamed mohsen
- 6 years, 6 months ago

Log in to reply

Can you please explain this so that I can understand the solution: "First way is 7 squares up and 17 right > (1x6x17 + 1 + 17) ways"

Ravi Theja KJK
- 6 years, 6 months ago

OH thank you I didn't realize that. This makes so much more sense now.

Ashley Clegg
- 6 years, 6 months ago

If I follow your logic then I have to say your count is off. There are only two ways. If the ant stays on black lines but cannot touch grey areas then all the ant can do is either immediately 7 lines up and then 17 lines to the right ( 1 path) or 17 lines to the right and then 7 lines up ( 2nd path). All the other paths you describe make you tough grey region.

Julian Fuller
- 6 years, 6 months ago

Log in to reply

@Julian Fuller – The question says "cannot cross grey zones" not touch

mohamed mohsen
- 6 years, 6 months ago

Log in to reply

@Mohamed Mohsen – Vertical crossing and horizontal crossing should be viewed in the same manner

Julian Fuller
- 6 years, 6 months ago

thanks for explanation..

Samuel Polontalo
- 6 years, 6 months ago

Clarification: The ant travels along the black lines and not along the white squares as a whole. After all, it starts and ends at two predetermined points A & B (which aren't squares).

A solution would be Mohammed Ahmend's solution where the number of ways to reach any point (excluding A) is the sum of the number of ways to reach the point immediately to the left of A as well as that directly below A. A recurrence table can be then set up as shown below:

1 | 8 | 15 | 22 | 34 | 72 | 110 | 148 | 195 | 288 | 381 | 474 | 580 | 752 | 924 | 1096 | 1285 | 1560 |

1 | 7 | 7 | 7 | 12 | 38 | 38 | 38 | 47 | 93 | 93 | 93 | 106 | 172 | 172 | 172 | 189 | 275 |

1 | 6 | 5 | 26 | 9 | 46 | 13 | 66 | 17 | 86 | ||||||||

1 | 5 | 5 | 21 | 9 | 37 | 13 | 53 | 17 | 69 | ||||||||

1 | 4 | 5 | 16 | 9 | 28 | 13 | 40 | 17 | 52 | ||||||||

1 | 3 | 5 | 11 | 9 | 19 | 13 | 27 | 17 | 35 | ||||||||

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |

0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

3 Helpful
0 Interesting
0 Brilliant
0 Confused

we can solve this problem with DP bottom up approach,

cell(i,j) = cell(i-1,j) + cell(i,j-1)

initially, cell(1,0) = cell(0,1) = 1

like this one: http://s5.postimg.org/d8httfhmf/image.jpg

sorry for calculation's mistake :P :D

2 Helpful
0 Interesting
0 Brilliant
0 Confused

×

Problem Loading...

Note Loading...

Set Loading...

There are 5 white-square ways

First way is 7 squares up and 17 right > (1x6x17 + 1 + 17) ways

Second way is 5 squares right ,7 squares up and 13 right > (5x6x13 + 5 + 13) ways

Third way is 9 squares right ,7 squares up and 9 right > (9x6x9 + 9 + 9) ways

Fourth way is squares right ,7 squares up and 13 right > (13x6x5 + 13 + 5) ways

Fifth way is 17 squares right and 7 squares > (17x6x1 + 17 + 1) ways

Adding all up gives 1560 ways