# hunting for treasure on an infinite grid

You are hunting for treasure located at some point on an infinite square grid. You have two tools: a pointer, which points toward the treasure; and a shovel, which you can use to dig for it. Here's the catch: both tools are imperfect. The pointer might point toward the treasure or it might be off by up to 60 degrees. And the shovel will break if you try to dig in five different places.

Can you find the treasure?

FINE PRINT:

• The treasure is guaranteed to be at a point of the grid.
• You can use the pointer from any point of the grid.
• If you use the pointer while you are standing on top of the treasure it can point in any direction. Otherwise it will point in a direction within 60 degrees of the direction to the treasure.
• You can only find the treasure by digging it up with the shovel, and you can only use the shovel four times.
• When you say "the pointer can be off by up to 60°", do you mean that there's some static error $-\frac{\pi}{3} \leq \theta _0 \leq \frac{\pi}{3}$ such that no matter where you're located, if the angle from you to the treasure is $\theta$, the pointer will read $\theta + \theta _0$? If so, one can easily locate the treasure by measuring $d\theta$ along some quadrature in the neighbourhood of your present location and continually moving in the direction of increasing $d\theta$.
– COTO
Jun 14 '15 at 21:15
• I'll cover a case of the proof of finding it: Suppose the shovel is neodymium. Then, align the compass so that the error is $0^\circ$, and we are done. $Q.E.D.$ (I'll leave it to you guys to find out the rest of the cases ;)) Jun 14 '15 at 23:59

It is

possible

Proof:

Forget where the pointer is telling you the treasure is, look at where it can't be.

For every pointing, there is a 120 degree region (centred opposite the pointing) that the treasure cannot be in. If we travel along the x-axis (back and forth, in increasing steps, so that we will definitely pass the y co-ordinate of the treasure) we will eventually exclude one half of the grid, divided along the line we have walked. Call this procedure a chop

We now chop along the y-axis. Assuming wlog that the treasure is in quadrant 1 (or the boundary line), we now chop increasingly large values of y until we find an upper bound for y. Repeat for x. We have now bounded the treasure on four sides. Walk the points 1 unit from the boundary, excluding them or finding we cannot exclude them until we have a 5x5 square of points.

Now let's revert to looking at what the pointing tells us. The outer points tell us nothing other than 'in this central 3x3 region' (120 degrees can cover the entire 3x3 square from any of those points).

Within the 3x3 region, the corners can point such that they cover all 9 points. The sides can cover 7 points; they must exclude an adjacent corner and side. These cannot all coincide, there are at least 2 pairs of side and corner removed like this.

.XX
.XX
..X


Now, whatever the pointing at the central point, it cannot cover both the upper left and the lowest X (135 degrees), so one of these is excluded. At this stage, we have only 4 points left so we get digging!

• You mean a 240 degree region, 120 both ways from the center.
– user1502
Jun 14 '15 at 23:31
• @Hurkyl No, I'm saying that there is a specific 120 degree region for each pointing that must be excluded, no matter where the pointer chooses. Jun 15 '15 at 7:39
• Each pointing excludes a $240^\circ$ arc. I think I've worked out what you're trying to say, though: your analysis is ignoring the information that was actually given to you, and is instead working with the $120^\circ$ arc that would be excluded no matter what the result of pointing was.
– user1502
Jun 15 '15 at 7:51
• Yes, that's what I was trying to say. I'll edit to clarify in a few hours. Jun 15 '15 at 8:00

Here's an image of what's happening: From the picture (red = target, black = current position), it can be seen that:

At a worst case scenario, when walking within 60 degrees of the target, the new distance to the target (red line) is decreased. By continually walking in the direction that the pointer points to, the distance to the object will be decreased at a logarithmic rate. I'm not sure the exact point can be determined even if you can always get closer. I'll leave this as a partial answer unless there are any clarifications.