10
$\begingroup$

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.
Improve this question
$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$
    – COTO
    Commented Jun 14, 2015 at 21:15
  • $\begingroup$ 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 ;)) $\endgroup$
    – Conor O'Brien
    Commented Jun 14, 2015 at 23:59

2 Answers 2

Reset to default
9
$\begingroup$

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!

Improve this answer
$\endgroup$
4
  • $\begingroup$ You mean a 240 degree region, 120 both ways from the center. $\endgroup$
    – user1502
    Commented Jun 14, 2015 at 23:31
  • $\begingroup$ @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. $\endgroup$
    – frodoskywalker
    Commented Jun 15, 2015 at 7:39
  • $\begingroup$ 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. $\endgroup$
    – user1502
    Commented Jun 15, 2015 at 7:51
  • $\begingroup$ Yes, that's what I was trying to say. I'll edit to clarify in a few hours. $\endgroup$
    – frodoskywalker
    Commented Jun 15, 2015 at 8:00
2
$\begingroup$

Here's an image of what's happening:

enter image description here

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.

My final answer:

It is not possible because although you can always get closer, a single point means you can always zoom in so any distance gained is arbitrary.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Yes, the treasure is at a single point. But could you make your answer clearer? First, how do you "get close"? Then, how do you walk circles around points? Finally your last claim isn't right -- even if you're very, very far from the treasure, the pointer might still jump up to 120 degrees, because it can point up to 60 degrees to either side of the treasure. $\endgroup$
    – Brian
    Commented Jun 14, 2015 at 17:40
  • $\begingroup$ You get close by walking in the direction the pointer points to. If you keep following that direction you will undoubtedly be getting closer. Then, when the direction starts varying greatly, you choose a general area to walk in a circle. From the pointer you will know that it is in there because the pointer will point into that circle at all points on its circumference. I do agree that it may jump up to 120 degrees though so I'll edit my answer. $\endgroup$
    – Quark
    Commented Jun 14, 2015 at 17:44
  • $\begingroup$ Sorry, I'm still concerned. There are a lot of details that need to be filled in. First the pointer is not guaranteed to point in a cardinal direction (maybe this was unclear?) so you can't necessarily walk in exactly that direction. Do you mean to step in the cardinal direction closest to the direction of the pointer? Can you explain why you will "undoubtedly be getting closer"? Also, what do you mean by "varying greatly"? $\endgroup$
    – Brian
    Commented Jun 14, 2015 at 17:50
  • $\begingroup$ I don't understand what you mean about walking over the point with the treasure, either. For instance, imagine the following scenario: when you are standing one spot to the west of the treasure, the pointer points NE. When you stand on the treasure, it points N. And when you stand one spot to the east, it points NW. Now, given that, how do you know you have found the treasure? $\endgroup$
    – Brian
    Commented Jun 14, 2015 at 17:53
  • $\begingroup$ @Brian I see your point and I'm revising my answer. $\endgroup$
    – Quark
    Commented Jun 14, 2015 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.