ben weiss

Anna loves multiples of 11. Bibi is not quite so keen. One day Anna is flipping idly through the yellow pages (full of 10-digit numbers including area codes), and notices that every number seems to have the interesting property that it is either a multiple of 11, or convertible to a multiple of 11 by altering a single digit. For instance, 999-867-5309 can be changed (by altering the first digit) to 5998675309, which is a multiple of 11.

 Anna challenges Bibi: “Pick any 10-digit number in the phone book. I’ll bet I can change it to become a multiple of 11 by altering at most one digit.”

Is Anna right?

Follow-up: Anna confidently states “Now pick a number with any number of digits. I’ll bet I can still do the same thing.” Now is Anna right? Can you find a number Bibi can pick that could foil Anna? If so, what is the smallest number (positive integer) Bibi could pick that would foil Anna? Can you find and characterize the entire sequence of numbers with this property?

—

Solution

Rephrased, the question asks whether every positive integer has a decimal Hamming distance <= 1 to a multiple of 11. And if not, what are the counterexamples?

Divisibility by 11 can be tested by summing even-place and odd-place digits, and seeing if the two sums differ by a multiple of 11. For instance, the number 123456789 can be separated into 1 + 3 + 5 + 7 + 9 = 25, and 2 + 4 + 6 + 8 = 20. These two numbers differ by 5, which is not a factor of 11, therefore 123456789 is not a multiple of 11. Change the leading ‘1’ to a ‘7’, however, and now we have 7 + 3 + 5 + 7 + 9 = 31, which differs from 20 by a multiple of 11. So 723456789 is divisible by 11.

Consider an arbitrary integer of the form 11n + k, where k is in [1 .. 10], thus not divisible by 11. In order to convert this number to a multiple of 11 by changing one digit, then there are four potential operations that could work: we can subtract k from an odd-position digit, add (11 – k) to an odd-position digit, add k to an even-position digit, or subtract (11 – k) from an even-position digit. The catch is that this operation must not carry; e.g. adding ‘3’ to 8′ would carry and affect the next digit over. E.g. if an odd-position digit is k – 1, then either subtracting k or adding (11 – k) will carry. Similarly, if an even-position digit is 10 – k, then either adding k or subtracting (11 – k) will carry.

So for a number Q to satisfy these constraints, we have the following conditions:

Q = 11n + k, for some k in [1 .. 10]

Every odd-position digit is k – 1

Every even-position digit is 10 – k

It’s efficient enough to simply examine every number with a pattern that satisfies the last two constraints (e.g. 5454545), and check its remainder mod 11. It turns out that the first few numbers that satisfy all the constraints, and thus have a decimal Hamming distance of >1 from any multiple of 11 are:

545
27272
1818181
636363636
90909090909
181818181818
272727272727
363636363636
454545454545
545454545454
636363636363
727272727272
818181818181
909090909090
363636363636363
81818181818181818
7272727272727272727
454545454545454545454

And then the sequence repeats, with the pattern extended in increments of 22 digits for each term. Interestingly, if leading 0’s are allowed, the above list can be neatly divided into ten odd-length terms:

545
27272
1818181
636363636
90909090909
0909090909090
363636363636363
81818181818181818
7272727272727272727
454545454545454545454

and ten even-length terms:

090909090909
181818181818
272727272727
363636363636
454545454545
545454545454
636363636363
727272727272
818181818181
909090909090

The leading zeroes result in two of the terms being duplicated, yielding 18 unique terms. And then the pattern repeats, with the recurrence:

a(n) = a(n – 18) * 10^22 + (a(n – 18) % 100) * 101010101010101010101.

Or put another way, for each term, the last two digits can be appended an additional 11 times, yielding a new term; e.g., 545 -> 5454545454545454545454545.

Finally, an open question: the ordering of the odd-length terms, the leading-digit sequence { 5, 2, 1, 6, 9, 0, 3, 8, 7, 4 } appears fairly random. Is there a simple expression that can generate this pattern? (One clue is that the first five digits (52169) plus the last five reversed (47830) equals 99999.)

From this week’s FiveThirtyEight.com Riddler column, slightly reworded for clarity:

“During their descent, three paratroopers were blown off course and crash-landed in the desert — an infinite, uniform, two-dimensional plane. They come to at a random time after the crash and must find a way to meet up. The only tool they each have is a device that displays a snapshot of the positions (but not the velocities) of all three of them in the desert. They can each use this tool only once. To make things more annoying, they’ve all been nearly blinded by sandstorms and won’t be able to physically see the others until they’ve all arrived at the same point. (Two out of three is not good enough; all three must be at the same point in order to see each other.)

Can you devise a strategy that they can agree upon beforehand and that will guarantee they will meet up? (Note that the snapshot does not indicate the specific identities of any of the paratroopers, so a strategy like “let’s agree that A stands still and B and C walk to him” will not work. The paratroopers do not know which of the three points corresponds to their own location.)

Extra credit: Is there a strategy that would work for any number of paratroopers?”

—

Additional assumptions:

1. The paratroopers have perfect dead-reckoning ability to know where they are at any time (relative to their initial position) and to navigate to any point.
2. They have some sort of watch/stopwatch that tells accurate relative time.

Solution:

Each paratrooper is preassigned a distinct prime number. (E.g. { 2, 3, 5 } for the three paratroopers.) They each use their tool as soon as they wake up, which shows each of them three points, though it may not be the same set of three points for each paratrooper.

Define the starting point of the last paratrooper to wake up as point Z. Note that this point will be shown by the tools of all three paratroopers.

So each paratrooper can independently perform the following steps:

1. Upon waking, immediately use the tool to obtain points A, B, C, one of which is this paratrooper’s initial location P, and one of which (possibly also P) is point Z.
2. Compute seven candidate locations for Point Z relative to Point P: { P, P + (A – B), P + (B – A), P + (A – C), P + (C – A), P + (B – C), P + (C – B) }.
3. Compute a Traveling Salesman path that cycles between these seven points. (It doesn’t have to be optimal.)
4. Walk along this path, stopping for exactly one hour at each candidate point, and eventually returning and waiting an hour at Point P.
5. Wait additional time at point P until the total elapsed time for the cycle is of the form [assigned prime]^k hours for some integer k. For instance, the paratrooper assigned the prime 5 might wait til their total cycle time is 25, 125, or 625 hours.
6. Start the cycle again, and keep repeating steps 4 and 5.

Using this scheme, each paratrooper is guaranteed to visit Point Z for at least one hour, on a regular interval of [assigned prime]^k hours. Since the cycle times for the three paratroopers are relatively prime, eventually all three cycles will coincide and the paratroopers will find themselves at Point Z at the same time.

Note that this solution generalizes trivially to N paratroopers, where each computes (1 + N(N-1)) candidate points for Z, and walks their corresponding TS cycles, each with relatively prime periods. Eventually they will all coincide at point Z simultaneously.

---

An alternate interpretation of the puzzle is that the paratroopers DO know which dot represents themselves, but do NOT have timepieces, and also do NOT have a common idea of true North. (In other words, the tool shows the direction and distance of the other paratroopers, but there is no sense of absolute north-south.) With these assumptions, the trivial solution of e.g. “head to the northwest corner of the axis-aligned bounding box” doesn’t work, and neither does the timed-cycle approach (because if the three cycle periods are not relatively prime, they could perpetually miss each other. Mathematically, for any finite amount of time, there is a nonzero probability that they won’t find each other in that time.)

For three paratroopers, the solution then becomes to find the “Fermat Point” of the three dots, and head there. (The Fermat Point is the single point at which lines drawn to the three dots are mutually off by exactly 60°/120° from each other, and is invariant to the distances of the three dots from the Fermat Point.)

For more than three paratroopers, it gets more complicated. My intuition is that the case of N paratroopers can be approached as follows:

1: Compute the Fermat Point of every triple of dots.

2: If no two Fermat Points coincide (100% probability for the initial random arrangement), choose the most compact one; i.e. the one with the smallest sum of distances from the point to its three dots. If two or more Fermat Points do coincide, choose the ones that coincide. (The chance that multiple Fermat Points coincide at distinct locations, e.g. two at point A and two at point B, is probabilistically zero.) Walk to one of the lines corresponding to the chosen Fermat Point, being careful to stay further away than its corresponding dot (and also being sure not to incidentally create a second smaller Fermat Point with two other paratroopers along the way*) then follow the line inward to the center.

*Herein lies the tricky part. I’m not sure exactly how to ensure this in the general case. For four paratroopers it’s straightforward: the “odd man out” just walks directly away from the center target far enough that he can’t create a more compact target at that radius, then walks circumferentially until reaching one of the Fermat lines, then walks inward to the target. I believe this exact approach also works in the case of five paratroopers, but can fail for six or more.