Tuesday, April 25, 2017

An Efficient Connector: Solution For the L Shape

In this post I'll provide the solution to the problem I posed recently:



For the L-shaped set shown here (1 unit tall and 2 units wide), find two points of the L such that, if the two points are joined by a straight line segment, then the average distance between points in the set decreases by the greatest possible amount.

(Measure point-to-point distances along the segments; that is, all "travel" remains within the L and/or the connector.)

Note, in the problem as phrased here, when you calculate the average distance between points in the "after" picture, you must consider not only distances between points in the L, but also distances between points in the L and points in the connector, and between points in the connector and other points in the connector. Call this the homogeneous form of the problem (the connector becomes part of the network being analyzed, as opposed to its being thought of as made of different stuff or serving a different purpose). One could also consider the inhomogeneous form of the problem, in which the points of the connector aren't considered when calculating the average for the "after" picture. ...

Here's my result for the homogeneous problem, which I haven't checked thoroughly (details here):


The optimal connector attaches to the vertical about 63% of the way up, and it attaches to the horizontal about 36% of the way over. Adding this connector lowers the average distance between points by 12.8%.

To solve the problem, I generalized the dimensions of the L and derived a general expression D(abcde) for the average distance between points in the network.


(See the PDF for the actual expression.) Next I specialized to the problem at hand by expressing a, d, and e in terms of b and c. (For example, d = 2 − c.) The result was a messy function of two variables, D(b, c).

Complexity of the expression aside, the nature of the problem guarantees that the behavior of this function will be pretty simple, with just one basin to find. Here's a contour plot of D(b, c):


The minimum value D0 = 0.8719… occurs at (b0 = 0.3725…, c0 = 0.7186…).

Mathematica can express D0, b0, and c0 in exact form, but the expressions are lengthy; for example, D0 is the fifth real root of a certain 18th-degree polynomial whose constant term is

63,935,354,309,637,222,973,365,921,189,789,696.


That's it for the homogenous problem, although the foregoing should be thought of as provisional given my lack of stress-testing. 

By the way, having a general expression for D also makes it easy to solve cases where the L has a width:height ratio different from 2:1. For example, to analyze a square L, we can put d = 1 − c instead of d = 2 − c. Then the optimal connector looks like this:


The triangle in the upper-left corner has horizontal and vertical legs of equal lengths, about 0.364. The optimal connector for the square L decreases the average distance between points by about 15%.

Now if one wished to add another segment to decrease the average distance further….

Monday, April 24, 2017

Packing Books Into Boxes

As frequently as I've moved apartments in my life, I ought to be better than I am at packing up books. Taping down the flaps on a box, I'm apt to think: Might I have gotten more books in here if I'd done it differently? After so many years, why don't I have a system for this?

Apparently I'm not the only person who feels this way. Here's a moving company that offers advice for packing books—from the comments online, you can tell that book-packing vexes people.


"A constant puzzle with every box": that actually describes pretty well the abstract version of this problem, known as the three-dimensional bin-packing problem. A research article on the problem says that "The problem is strongly NP-hard and extremely difficult to solve in practice." Even the one-dimensional version of the problem is NP-hard.

To give a flavor of the subject, here's a snippet from the research article giving an approximate algorithm:


Right—why didn't I think of that?

For a much friendlier tour of the problem, click here.

I wonder if researchers have ever studied the book packing problem—that is, bin packing in the case where the bins are all 'book-shaped.' Conversely, perhaps the mathematicians who study bin packing might be able to learn something by talking to people who pack books for a living! Anyway here are a couple of videos for packing books. In common with some of the mathematical approaches I saw, both videos use strategies of pre-sorting the books and recursively creating layers. Check back the next time you need to pack up a library.





Saturday, April 22, 2017

An Efficient Connector: A Warmup Problem

(Updated below.) I haven't had much time to dig into the problem posed in my last post, that of adding an efficient connector to this L shape:



As a warmup however, I did calculate the average distance between points on the boundary of an equilateral triangle with unit side lengths (measuring distances along the boundary, as if the sides of the triangle were roads).



The average point-to-point distance is ¾, which is less than the length of a side. For details, see this two-pager.

***

Waking up fresh this morning, I think the mean distance is easy to calculate as follows. Once the first point is chosen, the second point is equally likely to be closer when measured clockwise or closer when measured counter-clockwise. If closer measured clockwise, all distances up to 3/2 are equally likely; if closer measured counter-clockwise, all distances up to 3/2 are equally likely. Therefore once the first point is chosen, all distances up to 3/2 are equally likely, and the mean distance is
\[\int_0^{\frac{3}{2}}{v\cdot\left(\frac{2}{3}\,dv\right)} = \frac{3}{4}\,.\]
This reasoning generalizes to any triangle if we replace 3/2 by the semiperimeter s:
\[{\rm mean\ distance} = \int_0^s{v\cdot\left(\frac{1}{s}\,dv\right)} = \frac{1}{2}s = \frac{1}{4}p\]
where p is the perimeter of the triangle.

Friday, April 14, 2017

An Efficient Connector: The Solution And Some Additional Questions


Problem from the previous post:

Airport authorities would like to build a connector road (dashed line) so that maintenance vehicles can drive from one runway to the other without having to go all the way back to the airport terminal.

Given that the connector will be vertical, how far from the terminal should it be?

In my approach to the problem, I neglect the startup cost of building the connector road. My goal instead is to minimize the average distance that a maintenance vehicle would have to travel in order to get from the top runway to the bottom runway.



With the coordinates shown, the problem is to minimize, with respect to s, the value of the definite integral
\[ \frac{1}{c^2}\int_0^c{\int_0^c{\left(h + 2(b/c)s+ |x-s|+|y-s|\right)\,dxdy}}\,. \]
Before giving the result, let's make a couple of intuitive observations. First, if the two runways were parallel, then the optimal location for the connector would pretty clearly be at the midpoint. Second, since the runways aren't parallel, putting the connector at the far right looks worse than putting it at the far left…in both cases, the vehicles have to trundle the entire length of the runway to connect, but when the connector is at the far right, the vehicles also have to cover a long distance to get from one runway to the other. From these observations alone, we might expect the optimal location of the runway to lie to the left of the midpoint.

Evaluating the integral and minimizing the resulting function of s, we obtain

sbest = ½(cb).

This result shows how the parameter b pulls the optimal location leftward.

***

We could generalize this problem very far by asking something like the following: Given a closed, bounded, non-convex set L in a Euclidean space, find two points of L such that, if the two points are joined by a straight line segment, then the average distance between points in the set decreases by the greatest possible amount. In this form (if it is well posed), the problem might be difficult; even without the complication of identifying an optimal pair of points, just calculating the average distance between points in a convex set is apparently not easy. (This 2009 paper has some promising references if you're interested. Another relevant paper is this one from 2012.)

For the sake of having something to chew on, let's ask the following:



For the L-shaped set shown here (1 unit tall and 2 units wide), find two points of the L such that, if the two points are joined by a straight line segment, then the average distance between points in the set decreases by the greatest possible amount.

(Measure point-to-point distances along the segments; that is, all "travel" remains within the L and/or the connector.)

Note, in the problem as phrased here, when you calculate the average distance between points in the "after" picture, you must consider not only distances between points in the L, but also distances between points in the L and points in the connector, and between points in the connector and other points in the connector. Call this the homogeneous form of the problem (the connector becomes part of the network being analyzed, as opposed to its being thought of as made of different stuff or serving a different purpose). One could also consider the inhomogeneous form of the problem, in which the points of the connector aren't considered when calculating the average for the "after" picture. That's more like the runway problem.

I haven't done the problem in either the homogeneous or inhomogenous form; feel free to beat me to it!

I chose the L because it seemed like the easiest possible asymmetrical case. (Update 4/14: maybe an easier case would be a pair of parallel line segments of different lengths…but let's stick with the L.) One could try the problem for other non-convex sets, such as a polygon boundary, a circle, or some other plane curve. Two-dimensional sets could also be considered, such as two square regions given in position with respect to one another (a situation considered in this paper, though not with the goal of finding an efficient connector).

***

After you add a segment to a given set, you could repeat the problem with the resulting set, and so on. (If there were ever a choice between several equally good pairs of points, that would have to be handled somehow, either by choosing one of the pairs randomly or by choosing all of them at once.) I wonder what the limiting set looks like! Some kind of lacy fractal? And how well can one do, in the end? That is, given an initial network, does there exist an infimum value for the average distance between points attainable by adding connectors ad infinitum?

Monday, March 27, 2017

An Efficient Connector



Airport authorities would like to build a connector road (dashed line) so that maintenance vehicles can drive from one runway to the other without having to go all the way back to the airport terminal.

Given that the connector will be vertical, how far from the terminal should it be?

In my approach to the problem, I neglect the startup cost of building the connector road. My goal instead is to minimize the average distance that a maintenance vehicle would have to travel in order to get from the top runway to the bottom runway.

For example, with reference to the next figure, suppose that the vehicle is initially on the top runway, at the point indicated by the gray circle. To get to the indicated point on the bottom runway, the vehicle must drive along the magenta path to the other gray circle.


One way to begin the problem is to create a formula for the distance between a given initial location and a given final location. Then, one can use integration to average the distances over all initial and final locations. Because the average will depend on the location of the connector, the possibility arises of choosing the location of the connector that minimizes the average.

I did the problem for the dimensions shown:


In case anyone wants to solve it for themselves, I'll post my answer at a later time.

If you don't know calculus, you can try using your intuition to place the connector in an efficient location. Do you think that the most efficient connector will be halfway across, or less than halfway, or more than halfway?

Follow-up questions: Was it safe to assume that the most efficient connector is vertical? What if the runways are asymmetrical, as in this configuration?


Sunday, March 26, 2017

On Having A Favorite

To enroll in a frequent-flyer program online, I had to answer half a dozen security questions, including "What is your favorite kind of vacation?" and "What is your favorite cold-weather activity?" Who has ready answers to these kinds of questions?

"I like red the best!" says the toddler, as if his outfit didn't already make that clear. For grownups as well, having a favorite is for people who are at the toddler stage in their appreciation of something. I have a favorite bourbon, and that should tell you that I don't know much about bourbon. A good way to know that somebody isn't much of a reader is if they have a favorite book.

Now it is true that when I eat in a familiar restaurant, I almost always order the same thing. Always the pork curry at the Thai place in my neighborhood, always the chicken tikka at the Indian place. There's more to Indian food than chicken tikka, of course, but that's why God created other Indian restaurants. And if I didn't want a Shackburger and a strawberry shake, then I wouldn't be at Shake Shack, now would I?

This is not to say that Shake Shack hamburgers are the only hamburgers I like. I also like an occasional double quarter-pounder, or a "Mexican style" hamburger with Jack cheese, salsa, and avocado. Can't go wrong with a barbecue burger either—that bacon and zippy sauce!

Also, crumbled blue cheese is excellent on a thick hamburger.

Yet there are people out there who say things like, "My favorite hamburger is In-n-Out." Hearing this always makes me sad, not because I object to In-n-Out burgers in themselves, but because having a favorite hamburger just seems like a sad way to live.

To have a favorite X is to care too little about X's to arrange your life in such a way as to be surrounded only by wonderful X's. As few ties as I own, I can't say I have a favorite one. I like them all, or else why would I have them? Do you really want to put on a tie and think, "Eh, not my favorite"?

On the other hand, there are costs to not having a favorite. I can spend a long time in the morning choosing a tie to wear. A trip to the bookstore can take me hours and lead to no firm decisions; likewise for a trip to my Netflix queue. If nothing else, having favorites is efficient: a fact well known to parents of toddlers.

Saturday, March 25, 2017

Piece Out

Back for a few more notes on grammar and spelling:


1. Please know that the past tense of lead is led.

Wrong:
LeBron James lead the Cavaliers through a relatively stress-free fourth quarter on the way to the win. (Sports Daily, December 2016)
Fixed:
LeBron James led the Cavaliers through a relatively stress-free fourth quarter on the way to the win.


2. The preferred past tense of plead is pleaded.

Bad:
When arraigned Friday morning Goff plead not guilty and was assigned a public defender. Shortly before 1:30, through a second public defender, he plead guilty and was sentenced to 12 months in the Arkansas Department of Correction. (Booneville Democrat, March 2017)
Best:
When arraigned Friday morning Goff pleaded not guilty and was assigned a public defender. Shortly before 1:30, through a second public defender, he pleaded guilty and was sentenced to 12 months in the Arkansas Department of Correction.
My American Heritage Fourth Edition (2000) also lists pled as an acceptable spelling of the past tense.

Unfortunately, I see from the online version that the Fifth Edition now lists plead is an acceptable spelling of the past tense. My advice though is not to use that spelling. For one thing, it's inconsiderate writing—you'll trip up some fraction of your readers when they mistakenly read plead as present-tense the first time through.

I do think pled is fine, though according to the American Heritage entry linked above, the usage panel for the Fifth Edition prefers pleaded to pled by a wide margin.

And I see that the usage note doesn't even address plead as a past-tense spelling. I suspect that's because zero percent of the panel would find this spelling acceptable.

Although plead as a past-tense spelling is apparently widespread enough to be listed in the dictionary, I don't think it is used very often in high-status writing. Anecdotally, I find several thousand hits for a google search of "He pleaded guilty" on nytimes.com, but only about a hundred hits for "He pled guilty" or "He plead guilty." A quick scan suggests that the instances of "He plead guilty" tend to come from complicated constructions ("...it was required that he plead guilty...."), or from direct quotes of speech, or from internet comments.

Bottom line: use pleaded, or use pled if you prefer, but don't use plead because you might trip up your readers and/or come across like an internet commenter.


3. Don't hand-wave with around.

Lazy:
The committee developed a set of guidelines around ethics.
Better:
The committee developed a set of ethics guidelines for members.

The use of around, in the sense of the first sentence, is almost always a sign of vagueness. In the second sentence, we better serve the reader by stating more clearly what is going on—the guidelines are for members. Even if we don't give any additional information beyond the first sentence, we can cut out flab by writing
The committee developed a set of ethics guidelines.

Around, in the sense of the first sentence, is gaining currency. In addition to saving the writer the effort of being clear or concise, it appeals to those writers who worry that more common prepositions just don't sound smart enough.


4. Know your own verbal tics. Is piece one of them?

With the tic:
We haven't figured out the professional development piece.
Without:
We haven't figured out professional development.

Normally I don't comment on speech, just writing, but piece is a prominent verbal tic among knowledge workers. Their jobs require them to analyze systems into parts; it's natural to think of the parts as "pieces," and to speak accordingly. But I have yet to hear a sentence that wouldn't be improved by just not doing that.

Because it's unpretentious, I would even prefer
We haven't figured out the professional development thing.


Sunday, March 19, 2017

The Sliding Ladder Problem

Yesterday a colleague mentioned a problem that professors often assign in their Calculus courses. The problem went something like this:
A 5m ladder is leaning against a wall. If the bottom of the ladder is pulled along the ground away from the wall at a constant rate of 0.40m/s, how fast will the top of the ladder be moving down the wall when its bottom is 3m away from the wall?
(This is a version of the problem I found today at math.stackexchange.)

The problem is straightforward as stated (the answer is 0.3 m/s), but my colleague wanted to know what I thought, as a physicist, about the fact that the speed of the top point of the ladder exceeds any finite value as this point nears the ground. I can see from a different math.stackexchange page that this is a frequently asked question, so I thought I'd post some thoughts about it here.

Before I get to that, however, I ought to substantiate the point my colleague was making about the ladder's speed. The following animation helps to visualize the motion:


I added a reversed phase of the motion just because I think it aids the eye to see the "bounce."

The equations I used to generate this figure were

x(t) = t
y(t) = (1 − t2)½
0 ≤ t ≤ 1

where point F = (x(t), 0) is the location of the ladder's point of attachment to the floor at time t, and point W = (0, y(t)) is the location of the ladder's point of attachment to the wall at time t. At time t = 0, the ladder is vertical; at time t = 1, the ladder is horizontal.

These equations are the non-dimensionalized versions of

X(T) = vT
Y(T) = (L2 - v2T2)½
0 ≤ TL/v

where v is the constant speed of the ladder's foot, and L is the length of the ladder. (That is, x = X/L, y = Y/L, and t = vT/L.)

The functions x(t) and y(t) are differentiable on the interval (0, 1), which means that points F and W both have well-defined speeds during this interval. However, y(t) has no derivative at t = 1, not even a left-sided one; this means that the speed of point W doesn't exist at the moment of time when the ladder is horizontal.

People usually say that the speed of point W "becomes infinite" at t = 1…but if "the speed of point W" means |dy/dt|, then saying that the speed is infinite is saying that dy/dt = ∞, and I used to discourage my beginning Calculus students from writing such things, because I wanted them to appreciate that dy/dt is defined by a limit, and limits are numbers that either exist or don't.

(It's certainly true that the speed of point W exceeds any finite value as t approaches 1, and that's enough to justify asking for a physicist's take.)


To think about the ladder's motion physically, concentrate on the motion of the ladder's center of mass point. (The motion of the center of mass point tells you about the net force acting on the ladder.) Here's an animation showing the motion of the center-of-mass point.


The coordinates of the CM point are ½(x(t), y(t)). As the ladder moves, the CM point traces a circle of radius ½. This isn't uniform circular motion, however, because the CM point isn't moving at constant speed.

The next animation shows the horizontal and vertical locations of the CM point.


The CM point has zero horizontal acceleration during the motion. But the CM point has a downward vertical acceleration that increases without bound throughout the motion.

From the Second Law, Fnet, cm = Mtotacm, we conclude that during the time when the ladder is dropping, there is zero net horizontal force on the ladder, while the net vertical force on the ladder is downward, increasing without bound as the ladder reaches the ground.

So I think the main takeaway from physics is that no finite force is capable of making a ladder move this way.

To analyze the problem any further, I would want to specify the coupling between the ladder and the wall and floor. For instance, on the wall there could be a freely sliding ring, allowing point W to move vertically without resistance, but constraining point W so that it can't move horizontally. That version of the problem is considered in this article, again leading to the conclusion that the constraint forces cannot be finite. This had to happen, given the motion of the CM point during the stipulated motion.

***

The ladder problem reminds me of a class of problems treated by philosophers of science, called supertasks. A supertask is an infinite sequence of operations conducted in a finite amount of time. One question is whether supertasks ever happen, or are ever possible. Zeno's Paradox could be thought of as a question about whether motion itself is a supertask. You can read about supertasks on Wikipedia.

After Zeno, the most famous of a supertask is the example of Thomson's lamp; here is a paper about that paradox by John Earman and John D. Norton. I learned about some of Norton's work while writing my paper on the Law of Inertia and determinism in Newton's Laws.

Sunday, March 5, 2017

Points In A Circle Problem: Solution for N = 3

Let's take another look at the second-to-last figure from the previous post.


Given minimal obstacles X, Y and Z, we rotated and reflected the disk as necessary so that segment XY is horizontal and located in the upper half-disk. Then:

  • Obstacle Z can be located no higher than the lowest point of the small circle, otherwise there would exist a large feasible triangle in the part of the disk below Z.
  • Z cannot be located below the long chord ending at L, otherwise we could draw a large feasible triangle by sliding L downward.
  • Similarly, Z cannot be located below the long chord ending at M.

Altogether then, Z belongs to the (closed) grey triangular region, the bottom point of which is (0, −r0).

An interesting thing about this situation is that the location, shape, and size of the grey triangle is independent of the precise location of points X and Y—these points aren't even shown on the diagram. One could translate segment XY arbitrarily within the upper part of the disk, or lengthen or shorten segment XY, and it would remain the case that Z would have to belong to the grey triangle—because the grey triangle was defined by considerations about the lower half-disk. Of course, we almost certainly had to rotate and reflect the disk to make segment XY horizontal and up-top in the first place. So if you imagine not doing that reflection and rotation step, then when you construct the grey triangle based on the location of X and Y, it will end up being rotated or reflected from what is shown above.


Here's an animation showing all of the possible locations of the shaded triangle. (I'm shading the triangle green from here on out. Also, note that the dashed circle has radius r0.)


No matter how we orient the green triangle (i.e., no matter where X and Y are located), the green triangle can't escape the grey annulus, ½r0 ≤ r ≤ q, where q = 0.36606…. Therefore, no matter where X and Y are located, obstacle Z belongs to the grey annulus. 

But "Z" could be any of the three obstacles, so actually,

All three obstacles in a minimal triple must belong to the annulus ½r0rq.

This is a pretty severe constraint, especially when combined with the result of from the previous post (any two obstacles in a minimal triple must be at least r0Sqrt[3] apart).

***

Let's start again. Suppose {X, Y, Z} is a minimal set of obstacles, and rotate the disk if necessary so that segment XY is horizontal. Reflect if necessary so that segment XY is in the lower half-disk. (The switch from upper to lower is just so that I can use my existing codebase for generating diagrams.) And finally, for definiteness, reflect once more if necessary so that X is to the left of Y. Then with reference to the figure below, Z belongs to the green triangular region, and horizontal segment XY belongs to the part of the grey annulus located below chord DE.


Segment XY has to be at least r0Sqrt[3] long, which constrains its position in the annulus in several ways:

  • The segment can't be too close to the bottom of the annulus, because the width of the annulus decreases as you move towards the bottom.
  • The leftmost point can't be located very far to the right—there has to be a distance at least r0Sqrt[3] to the right-hand boundary of the annulus.
  • The rightmost point can't be located very far to the left—there has to be a distance at least r0Sqrt[3] to the left-hand boundary of the annulus.

Here's the real estate available for X and Y once we take into account these implications of the minimum separation requirement. Point X must belong to the blue region, and Point Y must belong to the red region.


On the same figure, lay down Segment PQ as shown:


Segment PQ represents an extreme case in the following sense:

(*) If a segment has one endpoint in the green triangle to the right of PQ, and passes tangent to the circle, then its other endpoint cannot be located in the blue region.

To see this, imagine choosing any point in the green triangle to the right of PQ, and from this point project a ray tangent to the circle: pretty clearly, this ray "flies too high" and misses the blue region entirely. This is because of the way the tangent to the circle "rocks" against the circle like a rocker-arm.


Thus, if a segment has one endpoint in the green region to the right of PQ, and another endpoint anywhere in the blue region, then the segment can't be tangent to the circle. Indeed such a segment enters the circle, i.e., it passes closer than ½r0 to the center of the disk.


This has implications for the location of point Z. If Z were located to the right of segment PQ, then segment ZX would necessarily pass closer than ½r0 to the center of the disk, and there would exist a large feasible edge-type triangle on the chord through ZX. (Feasible, because obstacle Y is safely away from this action.)

Conclusion: Z can't be located to the right of segment PQ. And by considering the red region analogously, Z can't be located to the left of segment RS either.


The allowable regions for X (blue), Y (red), and Z (green) are therefore as shown here:



***

Let's forget about the red and blue regions now. I was really only using them to help me clip off the annoying "wide lapels" of our initial green triangle. Having done that, we can now re-run the same annular arguments that we used for the initial green triangle.


Since the outermost point of the clipped green region is a distance r0 from the disk center, we can replace q by r0 in the reasoning and conclude this time that

All three obstacles in a minimal triple must belong to the annulus ½r0 ≤ r ≤ r0.

And with that, we're in the home stretch. In an annulus ½r0 ≤ r ≤ r0, the longest possible segment that doesn't pass closer than ½r0 to the center is a segment of length r0Sqrt[3] tangent to the inner circle.


This fact is probably standard, but at any rate I think it's not hard to see that the longest segment has to be a chord on the outer circle. (If either endpoint were in the interior, the segment could be lengthened; and if an endpoint were on the small circle, rotating the segment a bit about the other endpoint would free up some space to lengthen it again). And given that it's a chord, it's not hard to see that its length is maximized by pushing the chord toward the center until it's tangent to the inner circle.

What this means is that if all three pairs of obstacles must be at least r0Sqrt[3] apart, then all three pairs of obstacles must be exactly r0Sqrt[3] apart, i.e., triangle XYZ is isosceles, with its sides tangent to the circle of radius ½r0.

That is, {X, Y, Z} = {O1, O2, O3}.

***

Readers, please let me know if you see mistakes or lapses in the above! But assuming for now that it is basically right, we can add to our results in the Points In A Circle Problem.

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*. 

Known results so far:
  • 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* = 0.8286369… and a3(X1, X2, X3) = 0.8286369… if and only if {X1, X2, X3} = {O1, O2, O3} in some orientation.
Here, the points Oi are equally spaced around a circle of radius r0 = 0.320963…. As noted in an earlier post, the value of r0 is given exactly by the real root of the cubic polynomial 5x3 − 4x2 + 7x − 2, namely


and the value of a3* is given exactly by positive root of the polynomial 160000x6 − 265824x4 +  412857x2 − 209952, namely



***

Not all of the partial results from the past few months figured in the eventual solution to N = 3. Mostly, the argument relies on the tension between edge triangles and spotlight triangles. Calculating a3(O1, O2, O3) to begin with was actually harder, I thought, than showing a3(X, Y, Z) ≥ a3(O1, O2, O3) for all X, Y, Z. Needless to say, there could be much easier ways of solving the problem than the ways I developed, and perhaps there are theorems known to experts that would make quick work of the problem.

Part of me is disappointed that a careful investigation of N = 3 failed to turn up any better obstacles, or even any additional minimizers beyond the Oi originally conjectured. But I guess I'm even more surprised that an initial, intuitive choice of obstacles eventually held up to scrutiny.

Speaking of scrutiny, I have listed our "known results"—but in mathematics, nothing is really known until it's proved to professional standards of rigor. I'm not under the illusion that this series of blog posts meets that standard. I've been approaching the Points In A Circle problem recreationally, not professionally. Some of the arguments I've made are solid, but many others are just sketches that would need filling in. Journal peer review would certainly reveal gaps, if not errors, along the way. Nevertheless, I don't have any plans right now to clean up the analysis or organize it more linearly.

Also, I plan to keep my promise and leave the N = 4 problem to others!

Saturday, February 25, 2017

Points In A Circle Problem: Obstacles In A Minimal Set Can't Be Arbitrarily Close

A session last week on an elliptical machine gave an idea about minimal obstacles, and a red-eye flight last night gave me time to make some diagrams. So in this post, we'll show that the obstacles in a minimal set can't be too close to one another.

To that end suppose {X, Y, Z} is a minimal set of obstacles. For convenience, rotate the disk if necessary so that segment XY is horizontal (see the figure). Also, reflect if necessary so that segment XY lies in the upper half-disk. Then by previous work, obstacle Z must be located in the lower half-disk, at least a distance ½r0 from the disk center; and segment XY must be raised at least a distance ½r0 above the horizontal diameter of the disk.


(For reference, the diagram shows a circle of radius ½r0 centered at the disk center O. The diagram also shows a dashed triangle, the vertices of which are O1, O2, O3.)

If necessary, slide X toward Y reaching point X’ such that ZX’ is tangent to the circle. (X can't be to the Y side of X', because then segment ZX would approach closer than ½r0 to the center.) Likewise, if necessary slide Y toward X reaching point Y’ such that ZY’ is tangent to the circle. If segment X’Y’ is located above the circle, then draw segment X"Y" parallel to X’Y’ and tangent to the circle. Then segment X"Y" is no greater in length than segment XY (having been produced by two operations that either reduce length or leave it unchanged).

Now if point Z has coordinates (a, b), then the length of segment X"Y" can be found as  \[\frac{2r\sqrt{a^2+b^2-r^2}}{|b|-r} \equiv f(a, b)\,.\] To derive this, I required the system yb = m(xa), x2 + y2 = r2 to have a double root; this condition yields two slope values corresponding to the two tangents from Z. Using these slopes in yb = m(xa) with y = r then gives the x-coordinates of X" and Y". Subtracting the x-coordinates gives the expression shown above for f(a, b). (Some careful simplification is required along the way, but I felt like going this route instead of doing trigonometry.)

Knowing f(a, b) can help us to constrain the distance between obstacles in a minimal triple. Suppose we can specify a region of the disk that necessarily contains point Z. And suppose we can identify a number f* so that f(a, b) ≥ f* for all (a, b) in this region. Then we’ll have

Length of XY ≥ Length of X"Y" = f(a, b) ≥ f*

or in other words, the two obstacles X and Y must be at least f* apart. And since X and Y were chosen arbitrarily from the triple, the argument shows that in a minimal triple of obstacles, any two of the obstacles must be at least f* apart.

Let’s apply this argument to the next figure, which shows the entire unit disk, and which also shows two spotlight triangles on the same horizontal base. Observe that obstacle Z must belong to the (closed) shaded region—otherwise, by sliding point L or point M downward, we could create a feasible triangle with area greater than 0.828…. (Feasible because X and Y are located on or above the spotlight triangle's base.)


[[Note 2/27/17: I could have drawn the grey region smaller than I did, because point Z also has to be at least ½r0 below the horizontal diameter—otherwise we could draw a large feasible triangle below point Z. This doesn't change the conclusions below, but here is an improved figure.]]


The bottom corner of the shaded region has coordinates (0, −r0). It isn’t hard to show that f takes its minimum value there, f(0, −r0) = r0Sqrt[3] = 0.5559….  This configuration is shown in the next figure (improved analogously to the previous).


This gives our conclusion for today:

Any two obstacles in a minimal triple must be at least r0Sqrt[3] apart (0.5559…).

Note that the conjectured minimal obstacles {O1, O2, O3} do satisfy this condition—they form an equilateral triangle of side r0Sqrt[3].

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.