Tuesday, February 7, 2017

Points In A Circle Problem: Ruling Out Some Configurations

To date we've been using the term "edge triangle" to refer to a triangle of area 0.8286... that rests against two of the conjectured best obstacles O1, O2, and O3, as in this figure.


To generalize the term where helpful, let's say that given two distinct points P and Q, their edge triangle is the triangle whose base is the chord through P and Q, and whose third vertex lies on the disk boundary, maximally distant from the base.


(We won't apply the term when the chord is a diameter, in which case there are two points maximally distant from the base. We already know that in a minimal triple of obstacles, a diameter contains at most one obstacle; see item 6 here.)

The area of an edge triangle decreases as its base moves away from the disk center. This is clear from the figure: triangle E' is less wide and less tall than triangle E.


This could be restated as a constraint on minimal obstacles:

(*) Given three obstacle points X, Y, Z, if the chord through X and Y passes closer than a0/2 to the disk center—and if the edge triangle on that base doesn't strictly contain Z—then {X, Y, Z} is not a minimal set of obstacles.

This is because, under the stated conditions, a feasible triangle will exist with area greater than 0.8286..., making {X, Y, Z} worse than {O1, O2, O3}.

As an application, suppose three obstacle points X, Y, and Z all lie on a circle of radius a0, centered on the disk (as in the case of O1, O2, and O3) except that X, Y, and Z aren't equally spaced by 120° angles. Then it follows easily from (*) that the obstacles aren't minimal.


Proof: Because angles α, β, and γ aren't equal, at least one of the angles (say γ) exceeds 120°. Therefore the dashed distance in the diagram, a0 cos γ/2, is less than a0 cos 60° = a0/2. So if we draw the edge triangle whose base is the chord through X and Y, and whose third vertex is the projection from the center along the dashed line to the disk boundary, then this triangle will be feasible and will have area greater than 0.8286.... (This conclusion follows as long as X, Y, and Z lie on a circle of radius a0 or smaller.)

Here is one last result: if you displace one of the Oi, then the resulting obstacles are no longer minimal. In other words—keying on O1 for definiteness—we show that if the obstacles {X, O2, O3} are minimal, then X = O1


Proof: Let {X, O2, O3} be a minimal set of obstacles. We eliminate possibilities for X using the above diagram. (The three black dots in the diagram are the points O1, located at noon; O2, located at four o'clock; and O3, located at eight o'clock.)

First, X cannot be located on or below the diameter through O2, or else there would be no obstacle point above the diameter.

Likewise, X cannot be located on or below the diameter through O3.

Next, X cannot be located above chord EM. If X were located above chord EM, then spotlight triangle DEM could be enlarged to create a feasible triangle of greater area by sliding M upward along the disk boundary.

Likewise, X cannot be located above chord DL.

This, I believe, narrows down the possibilities for X to the two grey triangular regions (including the top boundaries, but excluding the bottom boundaries).


Now if X were anywhere in the dark triangle other than O1, then the chord through O3X would pass closer to the disk center than AB does; hence by (*), the edge triangle defined by O3 and X would be feasible and would have area greater than that of edge triangle ABC. And if X were anywhere in the light triangle other than O1, then the chord through O2X would pass closer to the disk center than GH does; hence by (*), the edge triangle defined by O2 and X would be feasible and would have area greater than that of edge triangle GHI.

The only possible location remaining for X is the location of O1, as claimed.



Intuitively, edge triangles penalize you for shrinking the obstacle triangle, while spotlight triangles penalize you for expanding it. This tradeoff was the intuition that led me to produce the Oi candidate triple in the first place. In the above reasoning, spotlight triangles helped to confine X to the triangular regions, and then edge triangles helped to drive X outward to O1.

Conclusion: In this post, we considered some classes of configurations that are, in a sense, "close to, but not quite" {O1, O2, O3}; and we showed that these configurations are not minimal.

***

I'm not sure if I ever mentioned this in previous posts, but in case not, I should say that the "Points In A Circle Problem" doesn't appear to be one that you can simply punt over to Mathematica for a solution. I tried it early on and I didn't get very good results, even in special cases. Maybe this shouldn't have been surprising: even if you specify the positions of the obstacle points, I think that finding the greatest area of a feasible triangle still isn't trivial for a computer. I believe you would classify this as a quadratically constrained quadratic program with a non-convex objective function—a class of problems that is NP-hard in general.

When I cast the problem for given obstacles as a constrained optimization over real variables and called Mathematica's Maximize and NMaximize commands on the system, I found inconsistent results. Sometimes the execution failed to return a result even after many hours; other times it threw some scary messages that made you wonder about the solution it eventually returned. These commands have some very intricate algorithms packed into them, and it isn't easy for a non-expert to know what they are doing under the hood. So I eventually stopped trying, and wrote my own solver and wrote custom code to do such things as generate combinatorial lists. If I'm being too pessimistic about Maximize and NMaximize, I invite correction from better Mathematica jockeys than me—or people for whom quadratically constrained quadratic programs are routine!

Tuesday, January 31, 2017

Neil Gorsuch and the Shadow of the Merrick Garland Nomination

With Senate Democrats vowing to filibuster the Supreme Court nomination of Neil Gorsuch, there will be tons of commentary about how the shoe is now on the other foot. The political theater has already been comical. However, what I doubt most people will notice is that from a Constitutional standpoint, the case of Neil Gorsuch is importantly different from the case of Merrick Garland.

The case of Merrick Garland was a conflict between two different branches of government. The President nominated a Supreme Court justice, and the leadership of the Senate defied the President by refusing to vote on him—even to reject him. That was a conflict between the Executive and Legislative branches of government.

What's happening with Neil Gorsuch is that internal divisions within the Senate are preventing the majority party from working its will on the body as a whole. This is a Senate power struggle.

To underscore this difference, remember that all last year, John Yoo and others were stepping up to defend Mitch McConnell from charges that he was acting unconstitutionally. By contrast, I think nobody will be out there defending Chuck Schumer from such charges—because his actions don't raise the same constitutional questions.

It's true that filibustering a Supreme Court nominee is unprecedented. It's also true that the Republicans broke vastly more ground last year in the destruction of governing norms.

***

Some are arguing that Gorsuch will be confirmed sooner or later, and so the Democrats should make it happen the hard way by filibustering and forcing McConnell to end the filibuster for Supreme Court appointments. I don't know what the Senate Democrats ought to do here, strategically or on principle. In my previous post, I argued that Garland deserved a vote because he was qualified for the job. I still think that argument was right. Gorsuch, too, is plainly qualified. It sounds like a QED—give Gorsuch a vote—except I keep getting held up by one thing: the only reason Gorsuch was nominated at all is that the Senate Republicans had kept his seat open through an indefensible maneuver. This context might justify the Democrats working to keep the court at eight members, since to do otherwise would be to reward the bad-faith actions of the Senate during the Garland nomination.

It's like if a lunchroom bully steals my chocolate-chip cookie and shoves his own oatmeal cookie toward me. Should I say, "Well, I guess oatmeal is fine," and eat it, or should I say, "That was my goddamned chocolate-chip cookie, and you're going to pay for taking it"?

This is what it looks like when norms get broken.

***

On the substance of the pick, I would have preferred Hardiman, based only on what I know of his life trajectory. But I never thought Trump would appoint such an 'unreliable' character anyway, and considering that it could have been Pryor (background here), I'm glad to see that it was Gorsuch.

Here is a profile of Gorsuch from scotusblog. Here are four cases Gorsuch decided. And here are notes on Gorsuch's jurisprudence from the libertarian site Reason.com.

Given the concerns I expressed about Trump after his election—concerns that have only escalated since then—what I most want out of the next Supreme Court justice is a person with courage to beat back executive power and stand up for the liberties guaranteed to us by the Constitution. Gorsuch might or might not be that person. On the plus side, he has robustly defended Fourth Amendment freedoms, and he has argued that the judiciary currently defers too much to Executive Branch rule-making. On the other hand, he has a narrow view of the 14th Amendment, and due process has already been an issue in the Trump administration. Depending on how the political circus in the Senate plays out, I'll be looking to SCOTUSblog, as well as center/libertarian pundits like Conor Friedersdorf, for substance reporting and analysis on the nomination.

Sunday, January 15, 2017

Points In A Circle Problem: Various Notes On N = 3

I haven't had much time to think about the problem lately, what with all the Holiday Challenge action, but there are a few notes from my notebook that I thought I would record. I'll begin by stating the problem once again using our compact notation.

Given N obstacle points X1, …, XN in the closed unit disk, let

aN(X1, …, XN)

denote the greatest possible area of a triangle in the disk that doesn't strictly contain any of the Xi. Let

aN* = minimum possible value of aN(X1, …, XN).

Then for each given value of N, our problem is to calculate aN* and find a minimal set of obstacles—that is, N points Xi* for which aN(X1*, …, XN*) = aN*. 

So far, here is what we know:
  • a1* = 1 and a1(X) = 1 if and only if X = O, the center of the disk.
  • a2* = 1 and a2(X1, X2) = 1 if X1 = O or X2 = O.
  • a3* ≤ a3(O1, O2, O3) = 0.8286369…, a value we'll abbreviate by A0.
Here, the points Oi are equally spaced around a circle of radius r0 = 0.320963….

Now the notes (edited 1/16/2017 to correct the error noted below in the comments):

1) If all three obstacle points are located a distance at least 0.798677… from the disk center, then an equilateral triangle inscribed in a centered circle of radius 0.798677… is feasible and has area greater than A0. Such a set of obstacle points therefore can't be minimal. (We'll strengthen this statement at the end of the post.)

2)  Because the long side of an edge triangle passes the disk center at a distance ½r0 = 0.16048… from the origin, it follows that if any obstacle point were located less than a distance 0.16048… from the origin, then we could produce a feasible triangle of area greater than by A0 by first drawing a feasible edge triangle and then pushing its long side inward toward the center. (To see that a feasible edge triangle exists, first rotate and reflect the disk if necessary so that any obstacles with r ≥ 0.16048… are in the closed upper half-disk. Then the edge triangle to the bottom of the disk is feasible.) Thus, a set of minimal obstacles must be confined to the annulus 0.16048 ≤ r < 1.

Confining the minimal obstacles to an annulus or some other two-dimensional region probably doesn't help fundamentally with solving the problem, because it doesn't reduce the problem's dimensionality. However, confining the obstacles could conceivably help with ruling out various cases one might find oneself considering; and it does reduce the acreage of the problem, which could increase the power of some numerical experiments.

Continuing with items from the notebook:

3) A natural question to ask is whether the conjectured minimal set {O1, O2, O3} is stable. That is, could you perturb the Oi slightly and obtain a better set of obstacles?

I think not…when I wrote a quickie computer program to evaluate several million small perturbations of the triple, for every perturbation the computer was able to find a triangle of area greater than A0 (by checking the perturbed edge and spotlight triangles). This isn't a proof of stability, of course. (Nor would a stability proof be enough by itself to establish that the Oi are a minimal set: better obstacles might exist but not be obtainable by a small perturbation of the Oi.)

One easy result that at least relates to stability is the following: If {X, Y, Z} is a minimal set of obstacles and triangle XYZ is congruent to triangle O1O2O3 by a rigid motion with a sufficiently small translation, then {X, Y, Z} is a rotation of {O1, O2, O3}. In simpler terms: if you hold triangle O1O2O3 rigid and nudge it off the center of the disk, possibly with some rotation, then the resulting points are no longer a minimal set of obstacles.

To see this, let t be the nonero vector pointing from the center of the disk to the center of triangle XYZ. Translate triangle XYZ back to the center of the disk via −t to form triangle X'Y'Z'. Triangle X'Y'Z' is just a rotation of triangle O1O2O3, which means that the edge triangles through the sides of triangle X'Y'Z' all have area A0. Now define the unit vector u1 pointing directly away from Y'Z', unit vector u2 pointing directly away from Y'X', and unit vector u3 pointing directly away from X'Z'. Now, you can't run against all three of these directions at once: at least one of the inner products t·ui must be positive. This is easy to show by a sketch, or by choosing coordinates so that u1 = (0, 1), u2 = (Sqrt[3]/2, −½), u3 = (−Sqrt[3]/2, −½), and t = (tx, ty). So if, say, t·u1 is positive, then for sufficiently small ||t||, the area of the edge triangle through YZ exceeds the area of the edge triangle through Y'Z'. But the edge triangle through Y'Z' has area A0, so the area of the edge triangle through YZ exceeds A0, and the obstacles X, Y, Z are not a minimal set.

4) Because the problem of N + 1 obstacles includes the problem of N obstacles as a special case, we have aN* ≤ aM* whenever NM.

Proof (example): Suppose {P, Q, R, S} is a minimal set of obstacles for N = 4, and {X, Y, Z} is a minimal set obstacles for N = 3. Then we have

a4(P, Q, R, S) = a4* ≤ a4(X, Y, Z, Z) = a3(X, Y, Z) = a3*

so that a4* ≤ a3*.

Because of this, any bound we find for small N becomes a bound on all higher values of N also. (The N = 3 bound a3* ≤ A0 implies the bound aN* ≤ A0 for all N ≥ 3.)

5) A minimal set of 3 or more obstacles can't consist of collinear points. If the obstacles were collinear, there would exist a feasible triangle of area 1, which exceeds A0, so that the obstacles couldn't be minimal.

6) For any diameter of the disk, there must be at least one obstacle on either side of that diameter, otherwise again there would exist a feasible triangle of area 1. (From this it also follows that any diameter of the disk contains at most one obstacle.)

7) Let's draw the three edge triangles ABC, DEF, GHI passing through points O1, O2, and O3:


If all three obstacle points X, Y, Z were to be located outside of any single edge triangle, then that edge triangle could be perturbed to create a feasible triangle of greater area. So the apportionment of minimal obstacle points among the 22 regions shown is not arbitrary. For example, it is easy to check that every region in the diagram falls outside of some edge triangle, so that in a minimal set of obstacles, no single open region can contain all three obstacle points.

8) Let's go further and draw not only the three edge triangles ABC, DEF, GHI, but also the six spotlight triangles ABJ, ABK, DEL, DEM, GHN, GHP:


In this diagram, the regions are sub-regions of the regions in the previous diagram. Therefore all three obstacles in a minimal set can't be located in any single region of this diagram either. And similarly to before, if all three obstacles in a minimal set were to be located outside of any one of the nine triangles, then that triangle could be perturbed to create a feasible triangle of greater area. So again the apportionment of minimal obstacle points among the regions is not arbitrary.

There are 82 regions altogether, which results in 95,202 ways to place the obstacle points. Listing these ways with a computer is easy; in Mathematica we can do it like this:

Flatten[Map[Permutations, IntegerPartitions[3, {82}, {0, 1, 2}]],1]

It is also easy to tell the computer which regions belong to which triangles, enabling an automated check of whether any given apportionment of the three points results in a forbidden circumstance of all three obstacle points lying outside of any of the nine triangles that define the figure. The configurations falling afoul of this rule then get culled.

For example, one of the configurations that gets culled is this one, because putting an obstacle point in each of the shaded regions leaves all of the obstacle points outside of triangle ABJ. You could slide vertex J downward and it would increase the altitude on side AB, thus increasing the area beyond A0; this shows that the implied set of obstacles is not minimal.


One of the configurations that survives the culling is this one:



You can verify that placing an obstacle point in each of the shaded regions guarantees that all nine of the triangles contain at least one obstacle point. The bottom region guarantees triangles ABJ, ABK, DEF, GHN, and GHP; the region touching that one guarantees triangles ABC, DEL, DEM; and the region near the top guarantees triangle GHI.

A total of 411 configurations survive, and by telling the computer which regions map to which regions under symmetries of the figure, these can be reduced to 79 distinct configurations. Here is an animation showing all 79 of them:


Certain regions of the diagram are absent from all of the valid configurations; therefore in a minimal set of obstacles, no obstacle point can be located in these regions. The forbidden regions are shaded here:


Of course, we could have drawn the original nine triangles oriented at some other angle. If a region is excluded in one orientation, it is excluded in all orientations. This means that no obstacle point in a minimal set can be so far from the origin that it belongs to some forbidden region in any orientation. The innermost point of any forbidden region is located a distance 0.76664… from the center of the disk. This shrinks the annulus to which obstacle points in a minimal set must belong: the known bounds are now r ≥ 0.16048… and r ≤ 0.76664….

Wednesday, January 4, 2017

More Book Titles With Curious Properties

I couldn't help generalizing the 4th Holiday Challenge…so here are some more book titles with special properties.

If you know of better answers in the following categories (or additional categories altogether), put them in the comments and I'll update the list. Rules for subtitles etc. are the same as in the Holiday Challenge. (Also, I am not including juvenile books.)


Book Titles With Special Properties


Title at least three words long; all words have the same number of letters

Less Than Zero, by Bret Easton Ellis


Title at least four words long; words in alphabetical order

The Time Traveler's Wife, by Audrey Niffenegger


One-word fiction titles; most and fewest letters

Immortality, by Milan Kundera

Scaramouche, by Rafael Sabatini

It, by Stephen King


One-word nonfiction titles; most and fewest letters

Hydrofunctionalization, ed. V.P. Ananikov and M. Tanaka

FDR, by Jean Edward Smith


Most words in a fiction title with every word at least 6+ letters

Everything Ravaged, Everything Burned, by Wells Tower

Brideshead Revisited, by Evelyn Waugh


Most words in a fiction title with every word at most 3+ letters

How It Is, by Samuel Beckett

The Name of the Rose, by Umberto Eco

In the Café of Lost Youth, by Patrick Modiano


Most words in a nonfiction title with every word at least 8+ letters

Teachers' Pedagogical Thinking: Theoretical Landscapes, Practical Challenges, by Pertii Kansanen et al.

Imperialism: Theoretical Directions, ed. Ronald H. Childcote

Organometallic Photochemistry, by Gregory L. Geoffroy and Mark S. Wrighton

Honorable mention for literary nonfiction: Slouching Towards Bethlehem, by Joan Didion (every word at least 7 letters)


Most words in a nonfiction title with every word at most 3+ letters

How We Won the War, by Vo Nguyen Giap and Van Tien Dung

What We Eat When We Eat Alone, by Deborah Madison



2016 Holiday Challenge: Results for Challenge 4, Book Titles

The final challenge, and the most open-ended of the challenges this year, was Challenge 4:
Like You'd Understand, Anyway. That's the title of a 2007 book of short stories by Jim Shepard. It's an unusual title because its shortest word is four letters long. Can you think of any other published books (fiction or nonfiction) in which the shortest word in the title is at least four letters long? The more words in the title, the better.
I should say that when I published this puzzle, I didn't know of a better answer than Like You'd Understand, Anyway. But I was confident that my readers would do better, and they did! I'll list the best answers I received, but first let me settle some ambiguities that various readers asked me about via email.
  • What qualifies as "a book"? Higher-quality answers will appear in the Library of Congress. But at the very least, there has to be an ISBN assigned.  
  • In Fahrenheit 451, the numeral 451 counts as a single "word" of three "letters." Other non-letter characters like ampersands, asterisks, etc., are handled similarly.
  • Sometimes it's hard to decide what "the title" of a book is. For example, I have an edition of The Hobbit that shows the title on the cover as The Hobbit, but then the inside title page adds Or There and Back Again in smaller font underneath. In such cases, I decide what "the title" of a book is by relying on the Library of Congress. They use a markup scheme called MARC to log books in the collection. According to this scheme, "the title" consists of the contents of MARC data field 245, subfields (a) and (b). For the case of The Hobbitlooking at the MARC data tells us that the title is seven words long. For subtitled books that aren't in the Library of Congress, we'll include the subtitle because that's the pattern we tend to find in MARC.

Without further ado, here are the best titles I received for Challenge 4, listed alphabetically within word count. Some of these were submitted by more than one reader. My two favorites are in bold: these get the job done without using subtititles—and they're fiction, where we don't expect to see so many examples. 

Whose Science? Whose Knowledge? Thinking from Women's Lives, by Sandra Harding

Your Healthy Journey: Discovering Your Body's Full Potential, by Fred Bisci

California Dreaming: Reforming Mathematics Education, by Suzanne Wilson

Dirk Gently's Holistic Detective Agency, by Douglas Adams

Julius Knipl, Real Estate Photographer, by Ben Katchor

Last Stand: America's Virgin Lands, by Barbara Kingsolver

Let's Explore Diabetes with Owls, by David Sedaris [1/12/2017]

Everything Ravaged, Everything Burned, by Wells Tower

Jeremy Thatcher, Dragon Hatcher, by Bruce Coville

Letter from Birmingham Jail (rare book illustrated by Faith Ringgold)

Miss Julia Takes Over, by Ann Ross

These Happy Golden Years, by Laura Ingalls Wilder

Willie Masters' Lonesome Wife, by William H. Gass

Finding these examples isn't easy! Some of the submissions I received arose from clever strategies, such as looking at 19th century books, and noticing that self-help books tend to have long titles with phrases like "Finding Your Inner."

Reader Ronda was the first person to send a published book title of at least four words with each word at least four letters long. And reader Beth K. won this year's drawing. Congratulations, both—a copy of Word Games 5 is on its way to you!

That wraps up the 2016 Holiday Challenge! Thanks for participating this year. My best wishes to everyone for a happy and healthy 2017.

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!
C.L.D.
CH. CH., OXFORD
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!

Monday, January 2, 2017

2016 Holiday Challenge: Results for Challenge 2, Candy Cane Word-Find

My readers appear to have solved this puzzle much faster than I did. Congratulations to reader Sharmin, who solved it first—a copy of Word Games 5 is on its way!


By the way, the email edition of yesterday's post was missing an embedded video, so for the benefit of my email subscribers, here's a direct link to Lisa Simpson challenging Bart Simpson to a game of rock/paper/scissors. (The video underlines that you shouldn't necessarily attribute rationality to your opponents!)

Getting back to Challenge 2, I thought people might like to see the process I use to create these word-find puzzles, so here is some detail on that.

The first thing is to rank the letters of the alphabet according to their visual density. I'll skip the steps for this and give the result:

I, Z, L, T, Y, P, C, F, J, E, S, A, B, R, G, K, H, V, X, D, U, O, Q, M, W, N

Next, we rank the words in the dictionary according to their dynamic range. Ideally, we want words like NINJA, which include both low-density letters (I, J) and high-density letters (N). That allows us to "paint" with a broad palette. But I had a hard time coming up with a holiday puzzle about ninjas, so I downloaded a list of holiday theme words from a teacher website:

ANGEL, BELLS, BIRTH, BLIZZARD, BLUSTERY, BOOTS, BOUGH, BOW, BOX, CANDLE, CANDY, CANDYCANE, CAP, CARD, CAROLERS, CAROLING, CAROLS, CELEBRATE, CELEBRATION, CEREMONY, CHARITY, CHESTNUTS, CHILL, CHILLY, CHIMNEY, CHRISTMAS, CHRISTMASCARD, CHRISTMASCAROL, CHRISTMASEVE, CHRISTMASTIDE, CHRISTMASTREE, CHRISTMASTREESTAND, CIDER, COAL, COLD, COOKIE, CRECHE, DECEMBER, DECORATE, DECORATIONS, DISPLAY, EGGNOG, ELF, ELVES, EVE, EVERGREEN, EXCHANGE, FAMILY, FAMILYREUNION, FATHERCHRISTMAS, FEAST, FELIZNAVIDAD, FESTIVAL, FESTIVE, FIR, FIREPLACE, FIREWOOD, FRANKINCENSE, FROSTY, FROSTYTHESNOWMAN, FRUITCAKE, GARLAND, GIFT, GIFTGIVING, GINGERBREAD, GINGERBREADHOUSE, GINGERBREADMAN, GINGERBREADWOMAN, GIVE, GOLD, GOODWILL, GOOSE, GREEN, GREETINGS, GUEST, HAPPY, HOLIDAY, HOLLY, HOPE, HOTCHOCOLATE, HOTCIDER, HUG, ICESKATES, ICICLE, ICY, IVY, JACKFROST, JESUS, JINGLEBELLS, JOLLY, JOY, JOYFUL, JOYEUXNOEL, KINGS, KRAMPUS, KRISKRINGLE, LIGHTS, LIST, LOG, LOVE, MANGER, MERRY, MERRYCHRISTMAS, MINCEPIE, MISTLETOE, MITTENS, MYRRH, NATIVITY, NAUGHTY, NICE, NIPPY, NOEL, NORTHPOLE, NUTCRACKER, OCCASION, ORNAMENTS, PACKAGE, PAGEANT, PARADE, PARTRIDGE, PARTY, PIE, PINETREE, PINECONE, PLUMPUDDING, POINSETTIA, POPCORNSTRING, PRESENTS, RECEIVE, RED, REINDEER, REJOICE, REUNION, RIBBON, RITUAL, RUDOLPH, SAINTNICHOLAS, SALES, SANTACLAUS, SANTASELVES, SANTASHELPERS, SANTASLIST, SANTASWORKSHOP, SCARF, SCROOGE, SEASON, SEASONSGREETINGS, SHOPPING, SKATE, SLED, SLEIGH, SLEIGHBELLS, SNOW, SNOWBALL, SNOWBOUND, SNOWFALL, SNOWFLAKE, SNOWMAN, SNOWY, SOCKS, SPIRIT, STAR, STNICK, STOCKING, STOCKINGSTUFFER, SUGARPLUM, SWEATER, TIDINGS, TINSEL, TOBOGGAN, TOGETHERNESS, TOY, TRADITION, TREE, TRIMMING, TRIPS, TURKEY, UNWRAP, VACATION, VISIT, WASSAIL, WINTER, WINTERTIME, WINTRY, WISEMEN, WISH, WONDER, WORKSHOP, WRAP, WRAPPINGPAPER, WREATH, XMAS, YULE, YULELOG, YULETIDE

Sorting these according to their dynamic range yields

{{WINTRY}, {NICE}, {NOEL}, {TRIMMING}, {WINTER}, {TOY, WISH}, {GOODWILL}, {WINTERTIME}, {MITTENS}, {NIPPY}, {TIDINGS}, {PINECONE}, {WISEMEN}, {CHIMNEY}, {LOG}, {TRADITION}, {FAMILYREUNION}, {MINCEPIE}, {COLD}, {SNOWFALL}, {SNOWY}, {REUNION}, {TINSEL}, {SNOWBALL}, {STNICK}, {PLUMPUDDING}, {NATIVITY}, {KINGS}, {HOLLY, IVY, JOY}, {OCCASION}, {CANDY}, {SAINTNICHOLAS}, {VACATION}, {CAROLING}, {STOCKING}, {GIFTGIVING}, {RIBBON}, {SHOPPING}, {HOLIDAY}, {CANDLE}, {NORTHPOLE}, {POINSETTIA}, {GOLD}, {POPCORNSTRING}, {FELIZNAVIDAD}, {COOKIE}, {LOVE}, {ANGEL}, {FIREWOOD}, {FAMILY}, {MISTLETOE}, {COAL}, {YULELOG}, {FRANKINCENSE}, {JOYEUXNOEL}, {JOYFUL}, {CEREMONY}, {CANDYCANE}, {FROSTYTHESNOWMAN}, {DECORATIONS, ORNAMENTS}, {YULE}, {NAUGHTY}, {SNOWFLAKE}, {JOLLY}, {UNWRAP}, {WRAP}, {RITUAL}, {WASSAIL}, {BOOTS}, {CELEBRATION}, {YULETIDE}, {HOTCIDER}, {PINETREE}, {CHESTNUTS}, {KRISKRINGLE}, {RUDOLPH}, {REINDEER}, {HOTCHOCOLATE}, {GIVE}, {VISIT}, {WRAPPINGPAPER}, {BLIZZARD}, {SANTASLIST}, {JINGLEBELLS}, {PAGEANT}, {GREETINGS}, {CIDER}, {GARLAND}, {STOCKINGSTUFFER}, {HOPE}, {CHRISTMASTIDE}, {SANTACLAUS, WREATH}, {GINGERBREADWOMAN}, {SUGARPLUM}, {TOBOGGAN}, {MERRY}, {SLED}, {BIRTH}, {GINGERBREADMAN}, {CHRISTMAS}, {SNOW}, {SEASON}, {MYRRH}, {SEASONSGREETINGS}, {CHRISTMASTREESTAND}, {SANTASWORKSHOP}, {LIGHTS}, {MERRYCHRISTMAS}, {CHRISTMASCAROL}, {NUTCRACKER}, {FROSTY}, {PRESENTS}, {TURKEY}, {MANGER}, {GREEN}, {SNOWMAN}, {DISPLAY}, {TOGETHERNESS}, {FIR}, {CAROLS}, {REJOICE}, {CHILL}, {SWEATER}, {SLEIGH}, {WORKSHOP}, {WONDER}, {CHRISTMASCARD}, {GUEST}, {BOW}, {CHRISTMASEVE}, {GINGERBREAD, SANTASELVES}, {FRUITCAKE}, {DECORATE}, {XMAS}, {KRAMPUS}, {EXCHANGE}, {BLUSTERY}, {GIFT}, {CHRISTMASTREE}, {PARTRIDGE}, {GINGERBREADHOUSE}, {FATHERCHRISTMAS}, {CHARITY}, {SANTASHELPERS}, {SCROOGE}, {GOOSE}, {EGGNOG}, {SOCKS}, {CHILLY}, {DECEMBER}, {CAROLERS, FESTIVAL}, {SLEIGHBELLS}, {FESTIVE}, {JACKFROST}, {SNOWBOUND}, {CARD}, {SPIRIT}, {RECEIVE}, {ELVES}, {EVERGREEN}, {TRIPS}, {HAPPY}, {RED}, {JESUS}, {BELLS}, {PARADE}, {EVE}, {BOX}, {PIE}, {PARTY}, {ICESKATES}, {LIST, STAR}, {SKATE}, {FIREPLACE}, {TREE}, {CRECHE}, {BOUGH}, {CELEBRATE}, {PACKAGE}, {ICICLE}, {SALES}, {ELF}, {CAP}, {FEAST}, {HUG, ICY}, {SCARF}}

Some of these looked good (like TOY) but didn't quite work out. Eventually I tried CANDY, doing an image search online for a line drawing of a candy cane. I was looking for a blocky image that would remain recognizable when converted to a low-resolution letter grid. Here was the image I chose:


I resized the image to 72 pixels by 40 pixels, and then created a histogram of pixel saturation:


Eyeballing the peaks in the histogram, I assigned a letter to each pixel according to the following rule:
  • Pixel saturation 0.9 or less:  Replace pixel with C or Y (flip a coin)
  • Pixel saturation between 0.9 and 2:  Replace pixel with letter A
  • Pixel saturation between 2 and 3.5: Replace pixel with letter D
  • Pixel saturation greater than 3.5:  Replace pixel with letter N.
Now I had a grid of letters resembling a candy cane. I ran the grid through a word-search-solver that I wrote a long time ago, just to see what words were present in the grid. I found several instances of short words like AND, with maybe a CYCAD or two—but no CANDY.

Even after ten thousand attempts, I still didn't have a grid with CANDY. I diagnosed the problem as not enough Ds next to Ys (or something like that), so I added some blurring to the pixel rule for saturation above 3.5. Instead of replacing all of these pixels with Ns, I set it to be 93% likely to replace the pixel with an N, with 7% likelihood of C, D, or Y. With this rule, the image still looked like a candy cane, and it only took around 500 attempts to produce a grid with one instance of CANDY in it. (I had to solve the puzzle myself, because my word-search solver tells me which words are in a grid, but not where they are located!)

From there I adjusted the font size and spacing of the grid in Microsoft Word, and the puzzle was finished.


Most ASCII art looks a lot nicer than this, as you can see from a google search. In part, that's because of the crudeness of my algorithm; it's also because most ASCII art uses a much larger character set with much greater dynamic range. Some programs even help themselves to different font colors.


I'll leave you with the first known example of typewriter art, this butterfly created by Flora Stacey in 1898. Stacey created striking effects by the technique of rotating her paper in the typewriter.


Nowadays you can upload images to websites like this one and have them converted into ASCII instantaneously.

Results of Challenge 3, Lewis Carroll's problem of the two walkers, coming next!