3D Treasure Hunt
Some treasure has been hidden in a three-dimensional grid! Can you work out a strategy to find it as efficiently as possible?
This problem follows on from Treasure Hunt, which you may wish to explore first.
Imagine you are looking for treasure in a strange three-dimensional treasure island, where treasure can be hidden at any point on a grid defined by three coordinates.
When you enter a guess in the interactivity below, it tells you the shortest distance you would have to travel along grid lines to reach the treasure.
For example, if the treasure is at (1, 2, 3) and you enter (3, 3, 3), the interactivity will tell you that the treasure is a distance of 3 steps away (2 steps in the x direction, 1 in the y direction and 0 in the z direction).
Can you find a reliable strategy for choosing coordinates that will locate the treasure in the minimum number of moves?
If you have not met this type of problem before - solving it in 2D first is a very good idea.
It is worth looking at some very simple cases first and spending some time understanding the distances in 3D.
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
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 - 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:
- 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}$ - 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?$ - 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$? - 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$?
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.
Why do this problem?
This problem offers students an opportunity to explore coordinates in three dimensions, within the engaging context of trying to find some hidden treasure. Students can also test out their strategic thinking by considering efficient ways to find the treasure in the fewest number of guesses.Possible approach
Introduce the problem by showing the interactivity to the class. You could do this by inputting a guess and then asking students to suggest examples of points which are the required distance from the guess. Explain that the idea is to try to narrow down the possibilities to find the treasure.
Give students some time to work on the problem using the interactivity. If computers or tablets are unavailable, students could instead work in pairs, taking it in turns to choose where the treasure is and work out the distances. Encourage them to keep score of the number of guesses they needed to find the treasure.
Bring the class together and invite them to share useful ideas and efficient strategies. Encourage the students to consider all the points that satisfy each condition, and to look at the surface made in three dimensions by these points.
Key questions
Which points satisfy the conditions given so far?How can you narrow down the possibilities?
Is it better to guess a point in the middle of the region or at an edge?