Picturing the Treasure

The previous three puzzles all had a generic, though inefficient, solution strategy: Try all possible rearrangements and see if any meet the constraints. This one demands geometrical insight.

A pirate’s trunk filled with millions of dollars worth of jewels is buried in the sand on a flat part of the deep ocean floor. Your client has dropped sensors in the area to try to locate the trunk. The sensors can be dropped to a precise location, but their reports of distance to the treasure trunk are accurate only to within 10 percent. The first sensor reports the treasure to be at a distance of 450 meters (so the real distance from that sensor falls between 405 meters and 495 meters). A second sensor reports the treasure to be at 350 meters (real distance is between 315 meters and 385 meters). Because your client doesn’t want you to hire your own ship, he tells you only relative positions of the sensors. Specifically, he tells you the first sensor is at position (0,0) and the second is at position (300, 400).

Warm-Up

If the sensor estimates of distance to the treasure were precisely correct (no plus or minus 10 percent), how could you use one more sensor to find the exact position of the treasure?

Solution to Warm-Up

Draw a circle of radius 450 around (0,0) and another circle of radius 350 around (300, 400). The two circles meet at two points, as you can see in Figure 2-3.

Figure 2-3: The larger circle has a radius of 450 meters and the smaller has a radius of 350 meters. Their centers at (0,0) and (300,400) are 500 meters apart by the Pythagorean theorem.

Finding these two points algebraically is a bit of a challenge. Start with the two equations for the circles:

After suitable subtractions, you get the following equation for the line containing the chord linking the intersection points:

Substituting for the y value into equation (1) yields:

Solving the quadratic and substituting back into the equation for the chord line gives two intersection points:

The geometrical approach (even a scribbled picture) is vastly better and leads immediately to the instruction: Place a sensor on one of these intersection points. Either the sensor lands on the treasure or the treasure is at the other intersection point. In fact, you could place a sensor anywhere closer to one intersection point than the other.

Unfortunately, the distance between the sensors and the treasure is accurate only to within 10 percent, as noted. Please answer the questions in that imperfect world:

1. Where would you place a third sensor to guarantee the most accurate estimate possible of the location of the treasure trunk?

2. Suppose your client gave you two more sensors (that is, a third and fourth) that have to be dropped simultaneously. Could you find the treasure to within a single rectangle whose area is well under 5,000 square meters? How about under 2,000 square meters?

3. Suppose you had been called in before the first two sensors were dropped, but you were given only three sensors altogether. Two were extremely accurate (to within a centimeter) whereas the other was accurate only to within 10%. Assuming you had to drop two sensors at positions (0,0) and (300,400), in which order should you drop the sensors and which sensors should you use when and where to be able to locate the treasure to the smallest possible rectangular area?

Solution to Picturing the Treasure

1. Where would you place a third sensor to guarantee the most accurate estimate possible of the location of the treasure trunk?

Augment each circle with an inner circle and an outer circle corresponding to the possible distances, as shown in Figure 2-4.

Figure 2-4: The larger circle has a bigger uncertainty, reflecting the 10% accuracy.

Once again, if you put a sensor at one of the nominal intersection points (say the same one you would have used in the warm-up), either you will find that the treasure is within 60 meters or that it is hundreds of meters away. In that case, it is within 60 meters of the other nominal intersection point. Why 60 meters? Because 60 > √((35²) + (45²)) and the rectangles are approximately 70 by 90. However, one can step literally “out of the box” and get a better solution, as suggested by Ivan Rezanka. If we placed the third sensor along the line segment between center points (-46.75, 447.56) and (442.75, 80.44) but, say, closer to (-46.75, 447.56), then we could distinguish which rectangle the treasure is in and obtain even a more accurate estimate within that rectangle. The best place to put that sensor is a problem I leave to you.

2. Suppose your client gave you two more sensors (that is, a third and fourth) that have to be dropped simultaneously. Could you find the treasure to within a single rectangle whose area is well under 5,000 square meters? How about under 2,000 square meters?

As mentioned, the first two sensors limit the search to two rectangles of lengths 70 meters by 90 meters. These are centered at the points of exact intersection: (-46.75, 447.56) and (442.75, 80.44). You might think it could be a good idea to put the two sensors in the centers of the two rectangles. However, if we consider the case of each rectangle, then we realize that we might be better off to put the sensor in the right rectangle. For example, suppose we put each sensor 30 meters from the center along the center line and parallel to the longer side of the rectangle (see Figure 2-5).

Figure 2-5: For each approximate rectangle surrounding an intersection point, put the sensor 30 meters to the right of the center of the rectangle. Thus, not only will one know which rectangle contains the treasure, but also more or less where in the rectangle. For example, if the sensor reading is greater than 42.3 meters, then the treasure trunk is in the subrectangle to the right of the portion completely covered by the circle.

If the sensor is within 38.1 meters of the treasure, then the treasure is limited to the right half of the rectangle plus less than half of the left half of the rectangle, a total rectangular area of less than 53.1 by 70, as illustrated in Figure 2-6. (Why 38.1? Because 38.1 is the distance between the right upper and lower corners of the rectangle and the sensor position.) Because of the 10% inaccuracy, however, the sensor might be within 38.1 meters of the treasure, yet the device would read 42.3 meters (that is, 4.2 meters more). Moreover, such a reading could also be approximately 4.2 meters too little. This limits the accuracy to (15 + 42.3 + 4.2) by 70, which is under 4,310 square meters. If the sensor reading is greater than 42.3 meters of the treasure, we would know for sure that the treasure is limited to those portions of the rectangle not completely covered by the circle (70 by 60).

Figure 2-6: Given a sensor reading of d, the sketch shows the nominal circle, the smaller error circle (dashed), and the larger error circle (dashed). The treasure must be inside the dotted rectangle.

However, that second number is conservative. For example, if the measured distance is 50, then the rectangle encompassing the treasure ranges from roughly 28 to the left of the sensor to 55 away from the sensor in the horizontal direction, describing a rectangle of sides (55 - 28) by 70 having an area of 1,890 square meters.

This leads to a much better approach (see Figure 2-6). Consider placing the sensor 25 meters to the right of the right border of each 70 by 90 rectangle (that is, 70 meters from the center of the rectangle), assuming the 90 meter long borders of the rectangle are horizontal. Any distance from the sensor would describe an arc through the rectangle. If that distance were d, then the leftmost point within the rectangle would be d - 25 to the left of the right border of the rectangle (and would lie on the center line of the rectangle). The rightmost points would be where the arc intersects the top and bottom edges of the rectangle, as you can see in the figure. There would be two rightmost points at the upper and lower rectangular edges. Their position can be determined by the Pythagorean theorem. Since a sensor reading of d could mean an actual distance between 0.9d and 1.1d, we will take the left-most point from the 1.1d reading and the rightmost point from the 0.9d reading. So, choosing this position for the sensor gives us a single rectangle to search whose area is under 1,940 square meters.

3. Suppose you had been called in before the first two sensors were dropped, but you were given only three sensors. Two were extremely accurate (to within a centimeter), whereas the other was accurate only to within 10%. Assuming you had to drop two sensors at positions (0,0) and (300,400), in which order should you drop the sensors and which sensors should you use when and where to be able to locate the treasure to the smallest possible rectangular area?

   This question turns out to be surprisingly easy to answer. Use the accurate sensors at positions (0,0) and (300,400). By the argument in the warm-up, that leaves only two tiny areas where the treasure could be. The inaccurate sensor could be used to decide which area had the sensor. What’s counterintuitive is that one might think it better to use the inaccurate sensor first and then use the accurate ones. A follow-up question is what to do if you have three sensors, all of different accuracies.