3D Treasure Hunt

Erin used this method to find the treasure:

There is no real way to be completely sure that you will get the answer, but I normally first submit (5,5,5) and see how far away the treasure is. I find it is easiest to first get the nearest to it just using the first two co-ordinates, and then just scroll through the depths to get to it. This will generally work in about ten turns.

David from St Peter's College, Adelaide disagreed:

My intuition told me that I should attempt the center of the map first. However, after a few attempts, I realised that choosing a center to start is not a good option. The optimal way is to choose a corner to start.

James from the UK explained why, and used this simple method:

After playing with the game for a bit, I realised that one of the things that makes it hard to work out where the treasure is that even if you know one of the coordinates is "1 away" it's 1 too small or 1 too big!

But if you're at an end-point (i.e. 0 or 9), you don't have that problem.

So, thinking about just one coordinate for a minute, if you know how far you are away from both end points, you can guarantee to know the exact coordinate of where the treasure is, e.g. if you are 3 away from 9 and 6 away from 0 then you must be at 6.

You can do this for all three directions in just four guesses, by guessing the following four sets of coordinates:

(0,0,0)

(0,0,9)

(0,9,0)

(9,0,0)

(Then you need a fifth guess to go and dig up the treasure).

For example:

Image

 The treasure is 7 steps closer to (0,0,0) than to (0,0,9)

So the treasure is at (?,?,1), since 1 is 1 step from 0 and 8 steps from 9 (so 7 steps closer to 0)

The treasure is 1 step further from (0,0,0) than from (0,9,0)

So the treasure is at (?,5,1) (5 is 5 steps from 0 and 4 steps from 9)

The treasure is 9 steps closer to (0,0,0) than to (9,0,0)

So the treasure is at (0,5,1)

In fact, James' method is enough to find the treasure on the fourth guess. Once you know that the treasure is at (_,5,1), and you know that it is 6 steps from (0,0,0), you can find the missing coordinate.

Trevor used algebra to represent the location of the treasure and described a different method:

For the sake of my explaination, lets use $(x,y,z)$ where $x$ is the blocks along, $y$ is the blocks up, and $z$ is the blocks across (using the example given)

Let's say that after putting in the coordinates $(0,0,0),$ the outcome will be "$21$ blocks away". Let's get rid of $z$ first. Now let's increase the value of $z$. You will notice immediately that the number of blocks away either starts decreasing or increasing. The correct value of $z$ can be found when the number of blocks away can no longer decrease any more (in other words, if you have hit $0$ or $9$ or if the number of blocks away starts increasing again).

Now for $x$ and $y.$ Let's say that the value of $z$ before was $5$ (ie you are at $(0,0,5)$). Now the treasure is $16$ blocks away (because it was $21$ blocks away from $(0,0,0)$), so  that must mean that $x+y=16.$

Trevor then used algebra to search for $x$ and $y$ beginning from as close as possible to half of the distance from $(0,0,z)$ (in this case, half of $16$, so $(8,8,5)$). Every time the treasure got closer, Trevor added or subtracted half of the new distance from each of the $x$ and $y$ coordinates. If the treasure got further away, Trevor redid the last step, but with adding instead of subtracting or vice versa.

David used algebra to show how another method works:

Let's pick $(0,0,0)$ to start. Now, if the program tells us the distance is $C,$ where $1 \le C \le 9,$ then we can try $(C,0,0)$ as our second guess. For example, if the distance from $(0,0,0)$ is $7$ steps, then we try $(7,0,0)$ as the second guess. Now, assume the program told us the distance from $(7,0,0)$ is $6$ steps. From the above two information, we can come up with two equations.

$|x - 0|+|y - 0|+|z - 0|=7$ simplified to $x + y + z = 7$ (since $x,y,z$ are all positive, $|x|=x,$ etc) (where $|m|$ means the absolute value of $m,$ so $|m|=m$ if $m\ge0$ and $-m$ otherwise)

$|x - 7| +|y - 0| + |z -0| = 6$ simplified to $-x + y + z = -1$ (since $(x-7)$ is negative, $|x-7|=7 - x $)

From           $x + y + z = 7$

                $-x + y + z = -1$

Solve the system equations, we get $x = 4, y + z= 3$

Now, try $(4,3,0)$ for the third guess, (because the biggest possible value for now that y-coordinate could be is $3$) and we were told treasure is only $2$ steps away from $(4,3,0).$ We can write down the third equation

$|x-4|+|y-3|+|z|=2$ and simplify that,

   $(3 - y) + z =2  \Rightarrow z - y = -1$  (as $x=4, |x-4|=0, y-3$ is negative, since $y \lt 3,$ $|y - 3|= 3 - y $)

From $y + z= 3$ and $z - y = -1 ,$ we can get $y=2$ and $z=1,$ and finally we find the treasure $(4,2,1)$

Another example:

Image

$x + y + z =15  $   (from guess 1)

$|x - 9| + |y - 6| + z = 18   $     (guess 2)

As $(x-9) \le 0,$ since $x \le 9,$ $|x - 9|= 9 - x.$ For $|y - 6|,$ assume it is equal to $y - 6$ first, and use it solve for $x,$ and if the value for solved $x$ is the integer in between $0$ to $9,$ then $|y - 6|= y - 6,$ otherwise $|y - 6|= 6 - y.$ Then using the same method from example 1 to calculate $z$ and $y$ coordinates, we get $(0,8,7).$ Only 4 guesses are required for finding the 3-D treasure.

Andrew from TFS in Canada showed the same method generally using algebra:

1. Place a guess at the origin point $(0,0,0).$ This will give you a distance value $d_1$ which will guide your next guess. You can create this equation which starts to locate the treasure:
   
   $\begin{align}&x + y + z = d_1\\ \Rightarrow & y = d_1 - z - x \end{align}$
2. Place a guess at $(0,0,d_1).$ This will give you a distance value $d_2$ which will guide your next guess. This will allow you to create this equation:
   
      $|x - 0| + |y - 0| + |z - d_1| = d2$
   
      (since $z \le d_1, |z - d_1| = d_1 - z$)
   
   $\Rightarrow x + y + d_1 - z = d_2$
   
   $\Rightarrow y = d_2 - d_1 + z - x$
   
   Note: If $d_1\gt9$, this won't be possible. However, it will still work if you guess $(0,0,9)$ instead of $(0,0,d_1). In that case, how will the equation be different?$
3. Place a guess at $(d_1,0,0).$ This will give you a distance value $d_3$ which will guide your next guess. This will allow you to create this equation:
   
      $|x - d1| + |y - 0| + |z - 0| = d_3$
   
      (since $x\lt d_1,$ $|x - d_1| = d_1 - x$) 
   
   $\Rightarrow z + y + d_1 - x = d_3\\ \Rightarrow y = d_3 - d_1 - z + x$
   
   What would you need to do here if $d_1$ was greater than $9$?
4. Compare the three equations to determine the position of the treasure:
   
   $\begin{align} &y = d_2 - d_1 + z - x = d_1 - z - x \\
   
   \Rightarrow &2z = 2d_1 - d_2 \\
   
   \Rightarrow& z = \frac{2d_1 - d_2} 2\\
   
   \Rightarrow& y = d_3 - d_1 - z + x = d_1 - z - x\\
   
   \Rightarrow &2x = 2d_1 - d_3\\
   
   \Rightarrow &x = \frac{2d_1 - d_3}2\\
   
   \Rightarrow & y = d_1 - z - x \\
   
   \Rightarrow & y = d_1 -\frac{2d_1 - d_2}2 - \frac{2d_1 - d_3}2\\
   
   \Rightarrow & y = d_1 - \frac{4d_1 - d_2 - d_3}2 \end{align}$
   
   What would happen here if $d_1$ was greater than $9$?

The treasure is located at: $$\left(  \frac{2d_1 - d_2} 2  ,  \frac{2d_1 - d_3}2  , d_1 - \frac{4d_1 - d_2 - d_3}2  \right)$$

Where is it if $d_1$ is greater than $9$?

Michael sent in a method expressed in a very neat way, which looks like magic because you can't see why it works. Can you see the similarities between Andrew's method and Michael's method? Can you use the algebra in Andrew's method to explain how Michael's method works?

Use $d(1,2,3)$ to mean the distance from $(1,2,3)$ to the treasure

The key coordinates for starters are $(0,0,0)$ with $d(0,0,0) = a$ and $(0,0,9)$ with $d(0,0,9) = b$

Then find $c = \frac12(a-b+9)$ and $d = a-c$

Now the key coordinate is $(0,9,c)$ and $d(0,9,c)= e$

Then find $f= \frac12(d-e+9)$ and $g = e+f-9$

The treasure is at $(g,f,c)$

So I snapped it in four movements max.

Note: If the treasure is on one of the 3 key coordinates then you will snap it with less than 4 movements.