Tuesday, January 3, 2017

2016 Holiday Challenge: Results for Challenge 3, Lewis Carroll's Two Walkers Problem

Holiday Challenges typically can't be solved by googling or opening a reference book. With Lewis Carroll's problem of the two walkers, I made an exception. This is just a math problem, and if you have Carroll's book Pillow Problems, you can look up the answer. You could even google the words in the puzzle and find Lewis Carroll's solution online. But I like the problem, and it's not so easy to get it right, either. Several readers submitted partial solutions, but nobody solved the problem fully. Even Carroll's answer was incomplete, as I'll discuss at the end.
A and B begin, at 6 a.m. on the same day, to walk along a road in the same direction, B having a start of 14 miles, and each walking from 6 a.m. to 6 p.m. daily. A walks 10 miles, at a uniform pace, the first day, 9 the second, 8 the third, and so on: B walks 2 miles, at a uniform pace, the first day, 4 the second, 6 the third, and so on. When and where are they together?
If you know how to make a distance-time graph, that's probably the easiest way to solve the problem. It's basically just transferring the narrative to paper. Here's what my graph looked like:

The two walkers are together for a single instant of time at noon on the third day, when they are both momentarily 23 miles from A's starting point, and later they are together for a period of time lasting from 6 p.m. on the fourth day until 6 a.m. the following morning, when they are both 34 miles from A's starting point. These are all the times and places where the two curves coincide.

Here are two distance-time graphs that I made on a computer. In the second one, I've excised the periods of night when the walkers are stationary.

In my first attempt at the problem, I didn't make a graph; I just scribbled down numbers for how far the two walkers were at the end of each day. Eyeballing the numbers, you can see that they pass each other on Day 3 and come together again at the end of Day 4. Figuring out the exact time of the meeting on Day 3 then takes a little more number-crunching.

Two readers found the solution at noon on Day 3. To see why this isn't the only solution, visualize the motion carefully. When A passes B at noon on Day 3, A is (of course) going faster. But A is slowing down, and B is speeding up, so it is inevitable that B will catch up to A sooner or later. (There's a problem like this in my physics book.)

Looking back at the original question with the answer in hand, one sees that Carroll chose his words carefully. Had he asked, "When and where do they meet?" the first crossing of the curves alone might be considered a sufficient answer. After all, A and B do meet there. (And in English, the word "meet" tends to suggest a first meeting.) Instead Carroll asks, "When and where are they together?" This elegant phrasing calls for a complete account of all the coincidences of the curves without telegraphing how many there will be.

Here's an animation I made to illustrate the problem. Walker A is the little blue line, and walker B is the larger green line. The pauses correspond to periods of night (6 p.m. to 6 a.m.) when the walkers are stationary.

Here's the same animation excluding periods of night:

Lewis Carroll's solution was more technical than just scribbling down numbers, or drawing a graph; it involved setting up a quadratic equation. Here's that approach in my own words.

Let An be the location of walker A at the completion of the nth day. Then, for example, A4 = 10 + 9 + 8 + 7. We could write this as A4 = 10 + 10 − 1 + 10 − 2 + 10 − 3, or 4 × 10 − (1 + 2 + 3). More generally, An = 10n − (1 + 2 + 3 + … + n − 1). Knowing that 1 + 2 + 3 + … + k = k(k+1)/2, we therefore have
An = 10nn(n − 1)/2.
Similarly if Bn is the location of walker B at the completion of the nth day, then by a similar process we find
Bn = 14 + n(n + 1).
The condition that A and B occupy the same location at the end of the nth day is AnBn = 0, or
10nn(n − 1)/2 − 14 − n(n + 1) = 0.
There are two real solutions, n = 4 and n = 7/3 = 2.333…. The solution n = 4 is easy to interpret: it means that at the end of the 4th day, the two walkers are at the same location. The second solution is, technically speaking, extraneous, because our variable n is supposed to be a whole number. But the fact that AnBn equals zero for n = 2.333… clues us that the quantities A2B2 and A3B3 have different signs, meaning that the walkers pass each other sometime during the third day. We can analyze the third day separately to find out when that happens, which is what Carroll proceeded to do.

In Pillow Problems, Carroll's final answer to this problem reads, "They meet at end of 2d. 6h., and at end of 4d. : and the distances are 23 miles, and 34 miles." That's a true statement. However as noted above, the question wasn't asking about when they meet; it was asking about when they are together. A complete statement of when the two walkers are together has to mention all of the times when they are together during the course of the situation described. That includes times such as 4d., 1h. So I consider a complete answer to the stated problem to be,
They are together at noon on the third day, 23 miles from A's starting point, and from 6 p.m. on the fourth day until 6 a.m. the following morning, 34 miles from A's starting point.

These are called "pillow problems" because Carroll solved almost all of them mentally while lying awake in bed—only writing down the solution after he had it, and only writing down the problem statement after that. Some of these feats of solving are tremendously impressive, notwithstanding Carroll's statement, in the self-effacing introduction to the first edition, that at first he himself could make little progress, only discovering with practice that he had become better at holding diagrams or equations in the mind long enough to work with them.

Carroll also writes about the errors that inevitably creep into such a process. In the case of the two walkers, I had to wonder if Carroll allowed himself just a little imprecision because he found the idea of A and B spending the night together a little too awkward to mention. Or maybe it was just an oversight. Carroll humorously anticipates such things in his introduction's final paragraph:

Other mistakes may perchance … await the penetrating glance of some critical reader, to whom the joy of discovery, and the intellectual superiority which he will thus discern, in himself, to the author of this little book, will, I hope, repay to some extent the time and trouble its perusal may have cost him!
May, 1893

This coda is yet another example of Lewis Carroll's habit of speaking with tongue in cheek.

That's it for Challenge 3; tomorrow we'll wrap up the Holiday Challenge with some impressive book titles supplied by readers!

No comments: