Thursday, February 16, 2012

Ant's travel in a grid


There is an ant which can walk around on a planar grid. The ant can move one space at a time left, right, up or down. That is, from (x, y) the ant can go to (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Points where the sum of the digits of the x coordinate plus the sum of the digits of the y coordinate are greater than 25 are inaccessible to the ant.


For example, the point (59, 79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 25. How many points can the ant access if it starts at (1000, 1000), including (1000, 1000) itself?


If we look at the question carefully ant can move only in the increasing fashion of x and y. Because if it tries to reduce initial x or y (1000,1000) in both cases the sum of digits will become more than 25. e.g 1000-1=999(9+9+9=27).

So ant can only increase x and y and it can not decrease x and y (1000,1000). the will be only in the positive area of x and y coordinates. In this manner if we increase X coordinate with Y fixed at 1000. we will see that ant can move up to (1698,1000). Sum(1698,1000) = 1+6+9+8+1 = 25

Now we can follow a staircase pattern from here by decreasing X by 1 and increasing Y by 1. But then we will get a loop hole at (1689, 1009). So we need to set y as 1000 again at X = 1689. Following the staircase pattern, same problem will happen again at (1599, 1090), so we need to set Y as 1000 again at X = 1599. The final graph will be as given below.

Total number of points will be:
600*601/2 + 2*90*91/2 + 2*9*10/2 = 188580