Take the Money and Run
If someone offers you $100 million to track down a briefcase and they give you weekly updates about your distance to it, you'd be a fool not to accept
This was a timed post. The way these work is that if it takes me more than an hour to complete the post, an applet that I made deletes everything I’ve written so far and I abandon the post. You can find my previous timed post here.1
$100 million to find a box2 within one year, with 52 updates about your distance to the box along the way. If you don’t get the box, you die. If you’re offered these terms, take the bet because you’re basically being promised $100 million!
This type of problem has a name: multilateration. This is a well-studied geometry concept and it’s fundamental to modern Global Positioning Systems (GPSs). With it, you can pinpoint the location of practically anyone or anything, to the degree of precision you’re allowed by going off of just a few separate distance readings.
Practically, multilateration means that you are going to make a lot of money on this bet, and you’ll be able to do it quickly. As an applied example, consider one of my hobbies: geocaching. In geocaching, you are tasked with finding an object like a container given only its GPS coordinates, down to three decimal places in Degrees Decimal Minutes (DD° MM.mmm′) format or five decimal places using Decimal Degrees (DD.ddddd°). If you’re unfamiliar, the latter is standard latitude and longitude, and when you get down to that degree of precision, that’s about where GPSs cut out, and it allows you to be within about six feet of the container of interest.
Six feet is close enough that you can’t miss the container. But during geocaching, people are right at the object when they write down the coordinates. How long would it take you to find an arbitrary object at that level of precision given only a set of distances? The answer is surprisingly little time! If you’re given exact distances, to an arbitrary level of precision, then it should take you at most two iterations after the initial distance to get to five decimals of precision in Decimal Degrees. Then, it’s over.
I’m calling this level of precision the “Direct find zone”, because you can’t miss it:
If you were given geocache-level precision on the distance estimates, that would mean giving you three decimal places, so a distance like 100.123 miles or 7.651 miles. When your distances are that precise, it will take you up to about five weeks to get very clear on the location of the cache if the distances are provided in miles, and three weeks if they’re provided in kilometers.3
But let’s be even more fair. Let’s assume that you’re not given arbitrarily precise distances, but are instead given precision to a single decimal place, so you might be told your $100 million check is in a box 100.1 miles away, or that it’s 39.3 miles from your current position. In that scenario, you’re still in a good position: it should take you at most about 18 weeks with miles or 16 with kilometers, then you’ll find your box!
Now, let’s see an applied example of this. I’m going to show you four randomly selected scenarios in what should be the hardest country to get around in distance-wise. In Russia, if you can get around and you get geocache-tier distance estimates, you’ll find the box to four decimal places quickly. Nowhere is a safe hiding spot if you’re smart about where you go to receive the next distance estimate.4
So, what’s my advice? If you’re getting reasonably precise distances, take the bet!
Now imagine if we didn’t live with the convenience of modern air travel. Imagine instead that we lived in the early 20th century and you took this bet in a big country like America, Canada, China, or Russia. Well, then, you might be boned.
On this one, I somewhat cheated, because I finished everything, but noticed I needed to clean up the .gif, so I stopped the timer after writing my last words and waited on the .gif to re-render, which brought me over the time limit. I hope you can all excuse this oversight, but it did not interfere with my writing time, just the placement of a single image.
Assumed stationary.
The way to figure this is simple:
If the reported distance is rounded to the nearest Δ, one reading fails to give you an exact circle, but instead gives you an annulus with thickness of Δ.
Once you zoom into a small enough region, that annulus looks like a straight strip of width Δ.
The bound assumes that after the initial clue, you can choose two more measurement locations so the resulting strips cross at a near-right angle. Two width-Δ strips crossing orthogonally leaves a patch with area on the order of Δ² (coarse_area_m2 = distance_precision_m * distance_precision_m).
After you narrow down to a given Δ by Δ patch, the bound assumes each additional well-placed reading can cut the remaining feasible patch roughly in half.
If each reading halves the area, then after k additional readings, the remaining area is Δ² / 2ᵏ.
To get the area no larger than the target coordinate cell area, i.e., target_area = (lat step) * (long step at a given number of degrees north, for which I used 60)
You solve Δ² / 2ᵏ = target_area, giving k >= log2(Δ² / target_area)
Rounding gives us k = ceil(log2(Δ² / target_area))
Then add the initial two coarse localization steps: upper_bound = 2 + ceil(log2(Δ² / target_area))
The reason for the halving assumption at Step 4 is that over a tiny remaining patch of distance, the annulus is well-approximated by a strip between two nearly parallel lines. Accordingly, if you choose your next location to receive a distance well enough, the patch only spans two adjacent rounded outcomes, so the boundary between those two outcomes is effectively a single line cutting the patch into two parts, and if you place the boundary near the patch’s area-median, whichever outcome you get leaves roughly half the area. The other assumption is that you can always pick a within-country next position so the new rounded distance boundary nearly bisects the current feasible set.
I also ran a more stringent simulation with 32 Monte Carlo hunts per clue at a given precision level, and with geocache-level precision, the 90th percentile number of weeks for five digits of precision was 15 weeks with miles and 13 with kilometers. Rounded to a single decimal place, those worst-case results were beyond 52 weeks, and they even were as such at four decimal places for miles. Although, at the same level, it was 15 weeks for kilometers.
The difference between this simulation and the earlier bounds is that I incorporated rounded annuli that intersect in messy shapes, I stopped you from going outside the country to help set up the bounds, I made it so you had to use real waypoints like a given city, town, village, etc., and I had finite Monte Carlo noise. Obviously this is too stringent to be realistic and it imposes limitations that are not implied in the challenge, so it is a way of generating a bound that is too strict.
And good places to go are calculable!