Thursday, February 16, 2012

Ant's travel in a grid

Problem: 

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.

Example

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?

Solution:

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

Reference
                  http://tech-queries.blogspot.in/2010/03/ants-travel-in-grid.html