# Using a Watch as a Compass

Direction-finding using only the sun and an analog watch is a trick that I remember first reading about when I was in elementary school.  I think it was in one of Seymour Simon’s Einstein Anderson “science detective” stories, but I’m not sure; being a kid was a long time ago.

More recently, I saw it mentioned again in a shark movie that I happened to sit through, The Reef.  In the movie, a sailboat runs aground and capsizes in shallow water; rather than stay with the boat, the people on board try to swim north toward a distant island.  It doesn’t go well.

Before leaving the boat, one guy looks at his watch, looks at the sun, mumbles a few calculations, then says, “That’s north,” and off they go.  I wondered if those calculations were correct, particularly since the movie was set in Australia– the Southern Hemisphere– and the method didn’t sound quite like I remembered it.  After some additional searching on the web, along with some experiments and calculations of my own, I learned that descriptions of this “Boy Scout” survival trick are frequently incorrect, incomplete, or misleading.  But more interestingly, such descriptions are almost never accompanied by a warning of just how inaccurate the method can be, even when it is used properly.  My suggestion: keep your GPS-equipped smart phone with you at all times.

How it works: If you are north of the tropics, hold your watch face horizontal, and turn so that the hour hand points toward the sun.  Then the ray bisecting the angle between the hour hand and 12 o’clock noon points approximately true south.  (I will deal with the Southern Hemisphere later.)  See the figure below for an example.

Example of using a watch as a compass (Northern Hemisphere, 10:30 am).

The first potential source of confusion is which direction is north and which is south: do you bisect the “small” angle or the “large” angle between the hour hand and 12 o’clock?  Some sources suggest that “north will be the direction further from the sun”– that is, bisecting the smaller angle points south.  Although this is usually the case, it can fail when the sun is up before 6:00 am or after 6:00 pm.  It seems simpler to just remember that south bisects the angle that sweeps in time from the hour hand toward noon (clockwise in the morning, counter-clockwise in the afternoon).

How well it works: This is what I found most interesting about this problem.  One survivalist blog (a somewhat amusing phenomenon, if you think about it) makes the strangely precise and grossly false claim that “the accuracy of this method is within 8 degrees (US and Canada).”  In fact, the error in the estimate of direction quite often exceeds 30 degrees, and can even exceed 80 degrees depending on where– and when– you are.

There are two primary sources of error.  The most obvious source of error is the accuracy of your watch.  Several online sites state that “the direction will be correct if the watch is set for true local time, without adjustments for Daylight Savings Time [sic].”  More precisely, the method is more accurate if your watch reads 12 o’clock when the sun is at its highest point in the sky, due directly south.

The problem is that “standard time” and “apparent solar time” rarely coincide exactly.  Everyone in a particular time zone thinks it is the same time, despite the fact that those on the eastern edge of a time zone will see the sun rise approximately one hour earlier than those on the western edge.  To make matters worse, the time zones in the U.S. are rather erratically shaped, resulting in even larger differences than would be the case if time zone boundaries were simple, straight lines of longitude, 15 degrees apart:

The time zones in the contiguous 48 states.

The second source of error is the latitude of your position: as several online sites suggest, “the further you are from the equator, the more accurate this method will be.”  This is essentially true, and is by far the larger of the two sources of error.  What is often left out, however, is that the method isn’t simply less accurate near the equator, it effectively doesn’t work “at all.”  In the tropics– the band around the earth between about 23.5 degrees south and 23.5 degrees north– not only is the sun higher in the sky, making it more difficult to accurately estimate its direction in the first place, the sun’s motion is also not as well-behaved (why?), so that the error in your estimate of direction can approach 180 degrees, even assuming an accurate estimate of the sun’s direction.

So how well does it work?  As approximately “best case” behavior, following is a plot showing the error in estimated direction over the course of the year 2012, at the Northwest Angle Inlet in Lake of the Woods, Minnesota (the northernmost point in the contiguous 48 states).

Compass error in Lake of the Woods, MN, for the year 2012.

The general shape of this plot is typical; the method works best in the fall and winter months, with the worst case behavior in the middle of the year.  Even this far north, errors can exceed 30 degrees.

At the other extreme, the following plot is for the Florida Keys, which suffer from being just north of the Tropic of Cancer, where errors are the worst.  However, the method still works reasonably well during the “cold” months.

Compass error in the Florida Keys for the year 2012.

Finally, back to the Southern Hemisphere.  Here, the method is only slightly different: if you are south of the tropics, then point 12 o’clock at the sun, and north bisects the angle between the hour hand and 12 o’clock noon (with the same “sweeping in time” sense described above).  I found several different incorrect variations on this online; perhaps the most disappointing was an otherwise very cool interactive Mathematica demonstration on the Wolfram web site.

And the method used in the Australian shark movie?  The description of the method turned out to be correct… but the action takes place at approximately 10 degrees south latitude, where all bets are off.  At any rate, it wasn’t enough to escape a great white shark.

References:

1. Meeus, Jean, Astronomical Algorithms (2nd Ed.). Richmond: Willmann-Bell, Inc., 2009.
2. Muller, Eric, Shapefile of the Time Zones of The United States. [link]

# Light Bulb Puzzle Solution

Last week’s post presented several variants of the following general problem: you have a number of light bulbs, and you need to determine the highest floor in a building from which a bulb may be dropped without breaking.  All light bulbs are identical in that they all have the following properties:

1. If a light bulb is dropped from a given floor and breaks, then any other light bulb will also break if dropped from that or any higher floor.
2. If a light bulb is dropped from a given floor and does not break, then neither it nor any other light bulb will break if subsequently dropped from that or any lower floor.
3. A light bulb may be dropped any number of times until it breaks, after which it is unusable and cannot be dropped again.

A “drop” consists of taking a single light bulb in the elevator up to a particular floor, dropping the light bulb from that floor, taking the elevator back down, and checking whether the dropped light bulb broke.

If the building has $f=100$ floors, and you have $b$ light bulbs at your disposal, what is the least number of drops $d$ required to guarantee that after at most $d$ drops you can determine the highest floor from which a light bulb may be dropped without breaking?

Each variant of the problem from last week simply changed the value of $b$, the number of available light bulbs.  The basic idea is most clearly illustrated with the simplest case of $b=1$; with just a single light bulb, we can do no better than dropping from floor 1, then floor 2, 3, 4, etc., until the bulb finally breaks, requiring $d=f=100$ drops in the worst case.

At the other extreme, suppose that we have “plenty” of light bulbs that we can afford to break (i.e., $b \geq f$).  In this case, intuition correctly suggests that a binary search is the right approach: for a 100-floor building, start by dropping a light bulb from floor 50.  If it breaks, then drop a second bulb from floor 25, otherwise drop the second bulb from floor 75, reducing the number of “candidate” floors by approximately half with each drop.  The maximum number of drops required is $d=\lceil\log_2(f+1)\rceil$, or 7 drops in the case of the original interview question from last week:

Problem 1: “Given 20 ‘destructible’ light bulbs (which breaks at certain height), and a building with 100 floors, how do you determine the height that the light bulb breaks?” – Asked at QUALCOMM

As I said last week, I suspect that this question actually contains a typo, since 20 light bulbs is “more than plenty;” we will only ever actually use 7 of them.  Things get more interesting if we have a more limited supply of light bulbs to break.  In the usual statement of this problem, $b=2$, and the final variant from last week asked the question for $b=5$.  However, we can tackle all of these variants at once by solving the general case.

The key to the solution is to turn the problem around, so to speak, and solve for $f$ instead of $d$.  That is, given a maximum number of drops $d$, and a supply of $b$ light bulbs, what is the tallest building that we can handle?  More precisely, what is the maximum number of floors $f(d,b)$ for which we can guarantee to find the “critical” floor in at most $d$ drops?

Consider the first drop from the as-yet-unknown optimal floor $k$.  If the bulb breaks, then by Property 1 (and 3) above, there must be at most $f(d-1,b-1)$ floors below floor $k$.  If the bulb does not break, then by Property 2 (and 3), there must be at most $f(d-1,b)$ floors above floor $k$.  Thus, $f(d,b)$ satisfies the following recurrence relation:

$f(d,b) = f(d-1,b-1) + 1 + f(d-1,b)$

$f(d,0) = f(0,b) = 0$

Using the identity

${d \choose b} = {d-1 \choose b} + {d-1 \choose b-1}$

it is not difficult to show that

$f(d,b) = \sum_{k=1}^b {d \choose k}$

This gives us a solution to all three original problems.  For any given number of floors $f^*$ and number of light bulbs $b$, we simply find the smallest number of drops $d$ for which $f(d,b) \geq f^*$.  To answer Problem 2, for example, for a 100-floor building with 2 light bulbs, we need 14 drops in the worst case.

Problem 3: Similarly, with 5 or more light bulbs we can do it in 7 drops… but we must be careful, since a binary search will only work with 7 or more light bulbs.  If we only have 5 (or 6) bulbs, the optimal strategy is slightly different.  Fortunately, the counting argument above gives a recipe for determining from which floor to drop the next light bulb in any situation: assuming that we have calculated the optimal number of drops $d$ remaining, the next drop should be from floor $f(d-1,b-1) + 1$, counting from the lowest remaining “candidate” floor.  For example, beginning with 5 light bulbs, the first bulb should be dropped from floor 57.  If it breaks, the second bulb is dropped from floor 26.  If it also breaks, the third bulb is dropped from floor 11.  If it breaks, the fourth bulb is dropped from floor 4.  If it breaks, the fifth and final bulb must be dropped from floors 1, 2, and 3 in the worst case, for a total of 7 drops.

Finally, using the identity

$\sum_{k=0}^d {d \choose k} = 2^d$

we can see how the binary search arises in the case where we have “more than enough” light bulbs.

# Dropping Light Bulbs (or Eggs): An Interview Puzzle Twist

I had planned to at least take a few holiday weeks off from this blog, and maybe back off from writing much more at all, putting a bow on this interesting and fun “experiment” over the last year and a half.

But subject matter seems to keep dropping in my lap.  In just the last two weeks I learned about some cool new science, a brilliant and elegant algorithm I had not heard of, and a nice twist on an “old” mathematical puzzle.

That is plenty to choose from; but since I love puzzles, and since I am still technically trying to be on vacation, this week I will just briefly present the puzzle, and we’ll see how it goes from there.

A variant of the problem appeared in a year-end compilation of “Top 25 Oddball Interview Questions” (the entire list is at glassdoor.com):

Problem 1: “Given 20 ‘destructible’ light bulbs (which breaks at certain height), and a building with 100 floors, how do you determine the height that the light bulb breaks?” – Asked at QUALCOMM

Before continuing, although I like this problem as a mathematical puzzle, I tend to dismiss this (or similar puzzles) as a useful interview question, for reasons I have discussed before.  But whether asked in an interview or not, note that this is not the possibly-vague “lateral thinking” type of problem as suggested here.  For those who have not heard this one before, we can make the problem precise as follows:

All light bulbs are identical in that they all have the following properties:

1. If a light bulb is dropped from a given floor and breaks, then any other light bulb will also break if dropped from that or any higher floor.
2. If a light bulb is dropped from a given floor and does not break, then neither it nor any other light bulb will break if subsequently dropped from that or any lower floor.
3. A light bulb may be dropped any number of times until it breaks, after which it is unusable and cannot be dropped again.

A “drop” consists of taking a single light bulb in the elevator up to a particular floor, dropping the light bulb from that floor, taking the elevator back down, and checking whether the dropped light bulb broke.  Your objective is to determine the highest floor from which a light bulb may be dropped without breaking, using as few drops (i.e., making as few elevator trips) as possible.  What should your strategy be to minimize the worst case number of drops required?

Problem 2: This problem caught my eye because I suspect that it actually contains a typo– but an interesting typo.  In the usual statement of the problem, instead of having 20 light bulbs at your disposal, you have only 2, and if/once they are both broken, you must have enough information to determine the highest floor from which a light bulb may be safely dropped.  Now what should your strategy be?

Problem 3: The above two variants of the problem are actually somewhat special cases, “endpoints” of a more general problem that still has a very elegant solution.  In this third “twist” variant, suppose that you have 5 light bulbs; now what should your strategy be to minimize the maximum number of drops required?  As usual, can you generalize as a function of the number of floors and light bulbs?