The Four Travelers Problem

four travelers problem

Four straight roads cross a plain. No two are parallel, and no three meet in a point. On each road is a traveler who moves at some constant speed. If Blue and Red meet each other at their crossroad, and each of them meets Yellow and Green at their respective crossroads, will Yellow and Green necessarily meet at their own crossroad?

Suprisingly, the answer is yes. Rob Fatland offers a beautiful solution at the CTK Exchange:

Imagine the whole scenario unfolding from Blue’s rest frame; that is, regard Blue as unmoving and consider the movements of the other travelers relative to him. What does he see? Objectively we know that each traveler moves along a straight line at a constant speed, eventually encounters Blue, and moves on, so from Blue’s perspective each of them moves directly toward him on a straight line, passes through his position, and continues.

Very well, let Red do that. But we know that Red also encounters Yellow and Green without deviating from his own path. And we know that (from Blue’s perspective) Yellow and Green are also traveling straight lines that intersect Blue’s position. This can only mean that Red, Yellow, and Green are all traveling along the same straight line from Blue’s point of view. And this means that Yellow and Green must meet one another.

(It might be objected that two points traveling the same line needn’t meet if they’re going in the same direction at the same speed. But here this would mean that two of the roads are parallel, and that possibility is excluded by the conditions of the problem.)

05/27/2016 UPDATE: Reader Derek Christie recalls a three-dimensional solution: “Make a time axis perpendicular to the plane. Then each traveller moves in a straight line trajectory through this 3D space. Blue and Red meet at a particular place and time, so their two trajectories must meet at a point, and these two trajectories define a plane. Both Yellow and Green trajectories meet the Blue and Red trajectories and so also lie in this same plane. So Yellow and Green must also meet somewhere in that plane.”

Present Company
Image: Wikimedia Commons

Why do we give gifts during courtship, and what makes a good gift? In 2005, University College London mathematicians Peter D. Sozou and Robert M. Seymour modeled the question with a game. The male begins by offering one of three gifts — valuable, extravagant, or cheap — depending on how attractive he finds the female. After he offers the gift, she decides whether to accept it and mate with him. Afterward, he decides whether to stay with her or seek another partner.

Each is trying to judge the intentions of the other. She must decide whether he wants a serious relationship or only a brief encounter, and he must decide whether she’s really attracted to him or only wants the gift.

According to the courtship game, the most successful strategy for the male is to offer an “extravagant” gift that’s costly to him but intrinsically worthless to the female. This tells the female that he has resources and values her highly, but it protects him from coy fortune-hunters.

“By being costly to the male, the gift acts as a credible signal of his intentions or quality,” write Sozou and Seymour. “At the same time, its lack of intrinsic value to the female serves to deter a ‘gold-digger’, who has no intention of mating with the male, from accepting the gift. In this way, an economically inefficient gift enables mutually suitable partners to be matched.”

(Peter D. Sozou and Robert M. Seymour, “Costly But Worthless Gifts Facilitate Courtship,” Proceedings of the Royal Society B 272, 1877–1884, July 26, 2005.)

Language Arts

A replacement for the Turing test has been proposed. The original test, in which a computer program tries to fool a human judge into thinking it’s human during a five-minute text-only conversation, has been criticized because the central task of devising a false identity is not part of intelligence, and because some conversations may require relatively little intelligent reasoning.

The new test would be based on so-called Winograd schemas, devised by Stanford computer scientist Terry Winograd in 1972. Here’s the classic example:

The city councilmen refused the demonstrators a permit because they [feared/advocated] violence.

If the word feared is used, to whom does they refer, the councilmen or the demonstrators? What if we change feared to advocated? You know the answers to these questions because you have a practical understanding of anxious councilmen. Computers find the task more difficult because it requires not only natural language processing and commonsense reasoning but a working knowledge of the real world.

“Our WS [Winograd schemas] challenge does not allow a subject to hide behind a smokescreen of verbal tricks, playfulness, or canned responses,” wrote University of Toronto computer scientist Hector Levesque in proposing the contest in 2014. “Assuming a subject is willing to take a WS test at all, much will be learned quite unambiguously about the subject in a few minutes.”

In July 2014 Nuance Communications announced that it will sponsor an annual Winograd Schema Challenge, with a prize of $25,000 for the computer that best matches human performance. The first competition will be held at the 2016 International Joint Conference on Artificial Intelligence, July 9-15 in New York City.

Here’s another possibility: Two Dartmouth professors have proposed a Turing Test in Creative Arts, in which “we ask if machines are capable of generating sonnets, short stories, or dance music that is indistinguishable from human-generated works, though perhaps not yet so advanced as Shakespeare, O. Henry or Daft Punk.” The results of that competition will be announced May 18 at Dartmouth’s Digital Arts Exposition.

(Thanks, Kristján and Sharon.)

Apollonian Circle Packings
Image: Wikimedia Commons

In 2014 I described Descartes’ theorem, which shows how to find a fourth circle that’s tangent to three “kissing circles.”

Descartes’ equation refers to the “curvature” of each circle: this is just the reciprocal of the radius, so a circle with radius 1/3 would have a curvature of 3. (This makes sense intuitively — a circle with a small radius “curves more” than a larger one.)

Remarkably, if the four starting circles all have integer curvature, then so will every circle we pack into the figure, each kissing the three around it. In the limit the figure becomes a fractal containing an infinite number of circles. It’s called an Apollonian gasket.
Image: Wikimedia Commons

07/29/2016 UPDATE: By coincidence, the U.S. quarter, nickel, and dime make three of the four generating circles in an integral packing — see the caption accompanying the first figure on this page. (Thanks, Trevor.)

Self Study

Here’s an isosceles triangle. Sides AB and AC are equal, and this means that the angles opposite those sides are equal as well.

That’s intuitively reasonable, but proving it is tricky. Teachers of Euclid’s Elements came to call it the pons asinorum, or bridge of donkeys, because it was the first challenge that separated quick students from slow.

The simplest proof, attributed to Pappus of Alexandria, requires no additional construction at all. We know that two triangles are congruent if two sides and the included angle of one triangle are congruent to their corresponding parts in the other (the “side-angle-side” postulate). So Pappus suggested simply picking up the triangle above, flipping it over, and putting it down again, to produce a second triangle ACB. Now if we compare the respective parts of the two triangles, we find that angle A is equal to itself, AB = AC, and AC = AB. Thus the “left-hand” angles of the two triangles are congruent, and it follows that the base angles of the original triangle above are equal.

In his 1879 book Euclid and his Modern Rivals, Lewis Carroll accepts the proof but remarks that it “reminds one a little too vividly of the man who walked down his own throat.”

Podcast Episode 105: Surviving on Seawater

alain bombard

In 1952, French physician Alain Bombard set out to cross the Atlantic on an inflatable raft to prove his theory that a shipwreck victim can stay alive on a diet of seawater, fish, and plankton. In this week’s episode of the Futility Closet podcast we’ll set out with Bombard on his perilous attempt to test his theory.

We’ll also admire some wobbly pedestrians and puzzle over a luckless burglar.

See full show notes …

Travel Delays
Image: Wikimedia Commons

What’s the most effective strategy for loading an airplane? Most airlines tend to work from the back to the front, accepting first the passengers who will sit in high-numbered rows (say, rows 25-30), waiting for them to find their seats, and then accepting the next five rows, and so on. Both the airline and the passengers would be glad to know that this is the most effective strategy. Is it?

In 2005, computer scientist Eitan Bachmat of Ben-Gurion University decided to find out. He devised a model that considers parameters of the aircraft cabin, the boarding method, the passengers, and their behavior, and found that the most important variable is a combination of three parameters: the length of the aisle blocked by a standing passenger, multiplied by the number of seats in a row, divided by the distance between rows. If rows are 80 centimeters apart, there are six seats in a row, and a standing passenger and his hand luggage take up 40 centimeters of the aisle, then the passengers headed for a single row will block the aisle space of three rows while they’re waiting to reach their seats.

This quickly backs things up. Even if the airline admits only passengers with row numbers 25-30, half the aisle will be completely blocked and most passengers will have to wait until everyone in front of them has sat down before they reach their seats. The time it takes to fill the cabin grows in proportion to the number of passengers.

A better policy would be to call up the passengers in rows 30, 27, and 24; then those in 29, 26, and 23; and so on (perhaps using color-coded boarding passes). These combinations of passengers would not block one another in the aisles.

An even better policy, Bachmat found, would be to dispense with seat assignments altogether and let passengers board the plane and pick their seats as they please. “With this method, or lack of a method,” writes George Szpiro, “the time required to get people on board and into their seats would only be proportional to the square root of the number of passengers.”

(Eitan Bachmat et al., “Analysis of Airplane Boarding Times,” Operations Research 57:2 [2009]: 499-513 and George S. Szpiro, A Mathematical Medley, 2010. See All Aboard.)

Podcast Episode 103: Legislating Pi

In 1897, confused physician Edward J. Goodwin submitted a bill to the Indiana General Assembly declaring that he’d squared the circle — a mathematical feat that was known to be impossible. In today’s show we’ll examine the Indiana pi bill, its colorful and eccentric sponsor, and its celebrated course through a bewildered legislature and into mathematical history.

We’ll also marvel at the confusion wrought by turkeys and puzzle over a perplexing baseball game.

See full show notes …

“Sweet-Seasoned Showers”

craig knecht -- shakespeare water-retention square

Today marks the 400th anniversary of William Shakespeare’s death. To commemorate it, Craig Knecht has devised a 44 × 44 magic square (click to enlarge). Like the squares we featured in 2013, this one is topographical — if the number in each cell is taken to represent its altitude, and if water runs “downhill,” then a fall of rain will produce the pools shown in blue, recalling the words of Griffith in Henry VIII:

Noble madam,
Men’s evil manners live in brass; their virtues
We write in water.

The square includes cells (in light blue) that reflect the number of Shakespeare’s plays (38) and sonnets (154) and the year of his death (1616).

(Thanks, Craig.)