13

An old sailor, by the name of John, was in his attic with his bright young great-nephew Stewart, showing him all the old tools they used to use while at sea.

Stewart was fascinated by all the trinkets. One item caught his eye, which was a giant compass like one would find on a table inside the ship. It was beautifully constructed, with hand-printed markings for north, east, south and west. Halfway between those markings were four more markings for the 45° (1/8) bearings of north-east, south-east, south-west, and north-west. Halfway again between those markings were eight markings for the 22.5° (1/16) bearings corresponding to north-north-east, east-north-east, and so on.

But what was special about this giant compass is that the markings went further down. There were sixteen markings for each of the 1/32 bearings, starting from north-north-north-east. And between those were thirty-two markings for the 1/64 bearings, starting from north-north-north-north-east. And it also had the 1/128 bearings and the 1/256 bearings, and so on down until they were so small that Stewart couldn't see them anymore.

Stewart asked his great-uncle, "Uncle John, how did you keep track of all these directions? Didn't you use degrees like we do today?"

The uncle laughed. "Of course we used degrees. These directions are just for decoration on the compass. But we did learn how to interpret them. Each direction is named the combination of the two directions it's between. Just like north-east is between north and east, and east-north-east is between east and north-east."

Stewart decided to challenge the old sailor on this. "So what would north-east-east-north-east be?"

John immediately said, "5/32 from north. Check for yourself." Stewart located the arrow pointing 5/32 of the way around the circle, and sure enough, it read north-east-east-north-east.

Stewart then decided to ask, "What about east-east-east-north-north-east-north?"

John said, "That's 9/64 from north. You can name any number of 'north's and 'east's as you like, and I can tell you what fraction it is."

"And north-north-north-east-east-east-east?"

"That's the same as the last one, 9/64 from north," explained Stewart. "Only the number of norths and easts matters, not their orders."

"How about south-east-east-south?" asked Stewart.

"That's just south-east. You can't use a number of 'south's and 'east's with a common factor," explained John. "They'd all be the same."

"Okay then," said Stewart, frowning in thought. He then blurted out, "How about west-west-south-south-south-west-west-south-west-west-west-west-south-south-west-west-west?"

John had his fingers out counting how many 'south's and 'west's his young pupil had uttered out (six and eleven, respectively). "That would be 351/512 from north."

"What about north-west-south-east?" asked Stewart smartly.

"It'll take more than that to outfox me," laughed John. "You can only name directions with two of the four cardinal directions that are next to each other. But I assure you, I can tell you the direction of any combination of two adjacent cardinal directions you like."

"That's cool," said Stewart, now turning his attention to a wind-up clock.

Is the old sailor's claim true? Can you come up with some combination of "north"s and "east"s (or some other combination of two adjacent cardinal points) that doesn't correspond to a point on the infinite compass rose?

Community
  • 1
  • Also, I looked it up while writing this problem that they used "North by east" and such notation past the 1/16 markings. But for the purposes of this problem, I made up an alternate arrangement. –  Oct 26 '14 at 14:52
  • Just to be clear, is EEN equivalent to ENE and NEE in this puzzle? – Jason Patterson Oct 27 '14 at 02:19
  • Yes. The positions of the symbols don't matter; only their number. –  Oct 27 '14 at 02:21
  • 1
    However, if you want another interesting challenge, try proving that the order doesn't matter, i.e. that no two symbols on the compass rose will have the same ratio of N's to E's (or other symbols as required). –  Oct 27 '14 at 02:22
  • I'm having a hard enough time getting 351/512, to be honest. I can see how the first few work, but that one is getting the best of me. – Jason Patterson Oct 27 '14 at 02:36
  • 351/512 around the circle is 95/128 from south to west. Try doing 95/128 from north to east instead and see what you get. –  Oct 27 '14 at 02:42
  • It doesn't seem like all of your claims can be correct. Consider NNNEE. We know that 'NN' and 'NNN' and 'NNEE' are illegal (because they simplify to N, N, and NE), so the only interpretation is as halfway between NNNE and E. But then NNNEE is clearly not the same as NENNE (halfway between NE and NNE), so order does matter. – ruakh Oct 27 '14 at 02:56
  • NNNE and E are not adjacent powers of two, though. A compass point's label is the combination of the two points it lies between in the compass rose directly "above" it (containing one power of two less than that point). For example, the 9/16 point is between 1/2 (4/8) and 5/8, not between 3/8 and 3/4 (6/8). –  Oct 27 '14 at 03:08
  • Basically, you can't make a point between NNNE and E because they never appear next to each other at any level on the compass rose. –  Oct 27 '14 at 03:11
  • @JoeZ.: Ah, O.K.; I had considered that possibility, but it still seems to violate your statement that order doesn't matter. Either way -- I guess that's the answer, then. NNNEE doesn't correspond to any point on the infinite compass rose. – ruakh Oct 27 '14 at 03:14
  • By "order doesn't matter", I mean that only the numbers of symbols are actually taken into consideration, and any rearrangements of the symbols represent exactly the same angle. –  Oct 27 '14 at 05:51
  • I was able to follow the logic of this question until the eighth paragraph, at which point I became confused. You claim that east-east-east-north-north-east-north equals 17/128. But by my reckoning, 4 Es and 3 Ns should be 9/64, because it lies halfway between 4/32 (NE) and 5/32 (NNEEE). What am I missing? – Kevin Oct 27 '14 at 13:49
  • You have possibly just caught another error. I did the first two in my head, and it was hard to keep track of what power of two I was at. –  Oct 27 '14 at 14:11
  • For those of you that don't want to write it out yourself, I've calculated the values in the northeast quadrant of the compass, down to 1/128: http://pastebin.com/uMHAJShE. Hope that's not too spoilery. – Kevin Oct 27 '14 at 14:27

2 Answers2

2

Leo had almost the right idea in his solution, but didn't quite get his explanation right.

The problem boils down to proving that every dyadic multiple of $90^\circ$ (i.e. every angle in the form $90^\circ \times \frac{a}{2^n}$) can be represented by a unique ratio of N's and E's. The solution for the rest of the compass follows by symmetry.

First, let's take a look at the chart that Leo put up, representing the number of N's and E's of a compass point in an ordered pair $(N, E)$:

Level 1: (1,0)                                           (0,1)
Level 2: (1,0)                   (1,1)                   (0,1)
Level 3: (1,0)       (2,1)       (1,1)       (1,2)       (0,1)
Level 4: (1,0) (3,1) (2,1) (3,2) (1,1) (2,3) (1,2) (1,3) (0,1)

This configuration of numbers is known as the Stern-Brocot tree, a way to generate a mapping between the rational numbers and the binary fractions from 0 to 1.

This proof that this tree is such a mapping has three steps, as shown below:

1. Proof of uniqueness

"And north-north-north-east-east-east-east?"

"That's the same as the last one, 9/64 from north," explained Stewart. "Only the number of norths and easts matters, not their orders."

Some people expressed doubts about this claim, and the fact that it could be proven.

Let $(a, b)$ and $(c, d)$ be any two points on the same level. Then, the point between them is $(a+c, b+d)$.

Now, notice that the points $(a, b)$ on any level are ordered by the ratio $\frac ba$. We can prove that this ordering is preserved every time you go down a level by proving that if $\frac ab < \frac cd$, then $\frac ab < \frac{a+c}{b+d} < \frac cd$.

Proof: Cross-multiply the demoninators so that you get $ad < bc$. Then, if you add $ab$ to both sides of the equation, you get $a(b+d) < b(a+c)$, and then divide by $b(b+d)$ on both sides to get $\frac ab < \frac{a+c}{b+d}$. If you add $cd$ to both sides of the equation instead, you get $(a+c)d < (b+d)c$, and divide by $d(b+d)$ on both sides to get $\frac{a+c}{b+d} < \frac cd$.

2. Proof of relative primality

"How about south-east-east-south?" asked Stewart.

"That's just south-east. You can't use a number of 'south's and 'east's with a common factor," explained John. "They'd all be the same."

The second claim that people had doubts about was this one. What if one of the in-betweens really did have an NEEN or NENNEE or similar, with the same ratio of N's to E's as NE? Then the whole question would be bunk.

So here's a proof that the number of N's and E's at any point on the compass are always relatively prime to each other.

Lemma: Any two consecutive points on the compass $(a, b)$ and $(c, d)$ will always satisfy $ad - bc = 1$.

Proof: By induction. At level 1, $(1, 0)$ and $(0, 1)$ satisfies $1 \times 1 - 0 \times 0 = 1$.

Then, suppose two consecutive points satisfy $ad - bc = 1$, and the point between them is $(a+c, b+d)$. Then, we take $a(b+d) - b(a+c)$ $= ab + ad - ab - bc$ $= ad - bc$ $= 1$, as required.

Now, suppose there is some point $(nx, ny)$ on the compass rose, where $x$ and $y$ are relatively prime so that $n$ is the greatest common factor. Then, its ancestor points are $(a, b)$ and $(c, d)$, and so the point satisfies $nbx - nay = 1$, or $n(bx-ay) = 1$. Therefore, $n$ must equal $1$, and $x$ and $y$ are relatively prime, as required.

3. Proof of surjection

"I assure you, I can tell you the direction of any combination of two adjacent cardinal directions you like."

Finally, the actual problem. Predictably, this is the hardest step. There are various proofs out there, some of them involving the Euclidean algorithm, some involving weird cross-multiplications, and others that I don't understand, but this is the most elegant one in my opinion.

Suppose that some combination of relatively prime $(a, b)$ didn't appear on the compass. Then, because it's between $(0, 1)$ and $(1, 0)$, it must be strictly between two points that do appear on the tree.

So consider $\frac pq$ and $\frac rs$ to be two consecutive points on some level of the Stern-Brocot tree, such that $\frac pq < \frac ab < \frac rs$. Then we can iterate as follows:

Let $\frac mn$ = $\frac{p+r}{q+s}$, i.e. the term in between those two terms on the next level. If $\frac ab < \frac mn$, then set $\frac mn$ to be the new $\frac rs$. If $\frac ab > \frac mn$, then set $\frac mn$ to be the new $\frac pq$. Then, repeat this procedure form the beginning. (If $\frac ab = \frac mn$, then $\frac ab$ is on the Stern-Brocot tree, which we assumed was not the case.)

If $\frac ab$ is not in the Stern-Brocot tree, this procedure will continue forever. But then all the $\frac mn$ values we get at each iteration form a Cauchy sequence of rational numbers with ever larger irreducible denominators, which cannot possibly converge to any rational number with a fixed denominator $b$. So this is impossible, and $\frac ab$ must appear somewhere on the tree.

I first encountered the Stern-Brocot tree in the 2006 paper of the Canadian Open Mathematics Challenge, which is (not entirely) coincidentally where I got the three steps of this proof from.

Community
  • 1
  • I think this is right in spirit, but the question makes it clear that all of the angles are dyadic fractions, which rules out Stern-Brocot as being the 'pure' explanation (since the Stern-Brocot tree covers all rational numbers in (0,1), not just the dyadics). – Steven Stadnicki Apr 17 '15 at 03:05
  • @StecenStadnicki The Stern-Brocot tree provides a mapping from the dyadic fractions to the rational numbers. The dyadic fractions are each compass point's position relative to 90 degrees, while the rational numbers are the E-to-N ratio. –  Apr 17 '15 at 03:44
2

The old sailor is correct! According to our notation, that ONLY depends on the number of N's, E's, S's or W's, we can ALWAYS create another "finer" degree of precision. I will illustrate why...

First, we have to think about the problem in a slightly different way. Consider that instead of drawing a circular compass rose we are drawing points on a graph. The coordinates of the points correspond to the number of instances of the particular direction. Also, for the purposes of this illustration, we assume that South is just negative North and West is negative East. So for example, (1,0) corresponds to E, (1,2) corresponds to NNE.

Now we can continue to create more points by simply going through our list and adding the coordinates of two existing adjacent points. Here are a few sample iterations...

Set1: (1,0)                                           (0,1)
Set2: (1,0)                   (1,1)                   (0,1)
Set3: (1,0)       (2,1)       (1,1)       (1,2)       (0,1)
Set4: (1,0) (3,1) (2,1) (3,2) (1,1) (2,3) (1,2) (1,3) (0,1)

Notice anything? The sets we create are every unique combination of integers that isn't perfectly divisible by a lower combination of integers (i.e. no common factors). Furthermore, since there are an infinite set of prime numbers, there must be an infinite number of combinations and an infinite number of markings on the infinite compass rose :)

Also, if we take the ratios of these integers (i.e. the slopes of the lines created by (0,0) and the respective point), we get the direction of the arrows on the compass rose. Since the ratio directly corresponds to slope which directly corresponds to the direction on the compass rose, no two combinations are allowed to have the same mix of N's or E's. Therefore, every combination corresponds to one and only one direction and order does NOT matter.

Leo
  • 525
  • 4
  • 8
  • I'll make the point that the directions on the compass don't actually correspond to the slopes of the fractions they represent. But you're on the right track. –  Oct 27 '14 at 16:14
  • 1
    Also, as I told d'alar'cop, you've only proven that there are an infinite number of possible combinations that are possible, not that all combinations are possible. Between infinite sets, injection does not imply bijection. –  Oct 27 '14 at 16:21
  • @JoeZ the directions DO correspond. However, they do NOT equal (which I think is what you meant). And you are correct about injection not implying bijection. So while I can come up with an infinite number of directions, I can also come up with directions that are impossible to perfectly match using a compass rose. For example, using the slopes I was talking about, I can say the slope of pi exists between 0 and infinity but I cannot map it perfectly using the ratio of any two integers. – Leo Oct 27 '14 at 17:09
  • If by "they correspond", you mean there's a monotone bijection between the two sets, then yes, they're right. And the problem is asking for you to prove that every rational slope "corresponds" to a direction on the compass rose, not just infinitely many of them. –  Oct 27 '14 at 18:44
  • I think I have a better understanding of what you are looking for now. I'll work on a way to show that this evening :) – Leo Oct 27 '14 at 19:22
  • After about 5 months, I've finally gotten around to posting the correct answer. –  Apr 17 '15 at 02:37