2015 Countdown Problem #3: An A-maze-ing Maze

Probability Level 5

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.

3 solutions

Mohamed Mohsen
Nov 21, 2014

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

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

Rishabh Jain - 6 years, 6 months ago

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

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

mohamed mohsen - 6 years, 6 months ago

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

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

mohamed mohsen - 6 years, 6 months ago

@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

Wee Xian Bin
Dec 6, 2014

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

Mohamed Ahmed
Nov 21, 2014

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

i literally did the same thing xd

Kenny Lau - 6 years, 6 months ago

same here (and calculation's mistake on the first time too XD)

展豪張 - 5 years, 3 months ago

2015 Countdown Problem #3: An A-maze-ing Maze

The answer is 1560.

3 solutions

0 pending reports