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