The Fifth Card

http://www.publicdomainpictures.net/view-image.php?image=65774&picture=playing-card

I hand you an ordinary deck of 52 cards. You inspect and shuffle it, then choose five cards from the deck and hand them to my assistant. She looks at them and passes four of them to me. I name the fifth card.

At first this appears impossible. The hidden card is one of 48 possibilities, and by passing me four cards in some order my assistant can have sent me only 1 of 4! = 24 messages. How am I able to name the card?

Part of the secret is that my assistant gets to choose which card to withhold. The group of five cards that you’ve chosen must contain two cards of the same suit. My assistant chooses one of these to be the hidden card and passes me the other one. Now I know the suit of the hidden card, and there are 12 possibilities as to its rank. But my assistant can pass me only three more cards, with 3! = 6 possible messages, so the task still appears impossible.

The rest of the secret lies in my assistant’s choice as to which of the two same-suit cards to give me. Think of the 13 card ranks arranged in a circle (with A=1, J=11, Q=12, and K=13). Given two ranks, it’s always possible to get from one to the other in at most 6 steps by traveling “the short way” around the circle. So we agree on a convention beforehand: We’ll imagine that the ranks increase in value A-K, and the suits as in bridge (or alphabetical) order, clubs-diamonds-hearts-spades. This puts the whole deck into a specified order, and my assistant can pass me the three remaining cards in one of six ways:

{low, middle, high} = 1
{low, high, middle} = 2
{middle, low, high} = 3
{middle, high, low} = 4
{high, low, middle} = 5
{high, middle, low} = 6

So if my assistant knows that I’ll always travel clockwise around the imaginary circle, she can choose the first card to establish the suit of the hidden card and to specify one point on the circle, and then order the remaining three cards to tell me how many clockwise steps to take from that point to reach the hidden rank.

“If you haven’t seen this trick before, the effect really is remarkable; reading it in print does not do it justice,” writes mathematician Michael Kleber. “I am forever indebted to a graduate student in one audience who blurted out ‘No way!’ just before I named the hidden card.”

It first appeared in print in Wallace Lee’s 1950 book Math Miracles. Lee attributes it to William Fitch Cheney, a San Francisco magician and the holder of the first math Ph.D. ever awarded by MIT.

(Michael Kleber, “The Best Card Trick,” Mathematical Intelligencer 24:1 [December 2002], 9-11.)

Self-Effacing

In introducing the puzzle-loving logician Raymond Smullyan, the chairman of a meeting praised him as unique.

“I’m sorry to interrupt you, sir,” said Smullyan, “but I happen to be the only one in the entire universe who is not unique.”

Risky Business

https://commons.wikimedia.org/wiki/File:Antipasto_all%27italiana.jpg
Image: Wikimedia Commons

In 1982, MIT physicist A.P. French received this letter from a writer in New Rochelle, N.Y.:

Being a safety minded individual I thought I would write you before experimenting on my own. Is it safe to mix Antipasto and Pasta together and could this be a future energy supply?

He responded:

I believe that your thoughtful and interesting suggestion about the mixing of pasta and antipasto deserves some acknowledgment. This process might well be a significant energy source — but only, I think, intragastrically. I estimate that the digestion of 1 lb of the mixture would release energy equivalent to about 0.001 megawatt hours or 0.000001 kilotons of TNT. I would not foresee any unusual hazards.

(From Robert L. Weber, ed., Science With a Smile, 1992.)

Fellow Travelers

https://commons.wikimedia.org/wiki/File:Soybean_cyst_nematode_and_egg_SEM.jpg

In short, if all the matter in the universe except the nematodes were swept away, our world would still be dimly recognizable, and if, as disembodied spirits, we could then investigate it, we should find its mountains, hills, vales, rivers, lakes, and oceans represented by a film of nematodes. The location of towns would be decipherable, since for every massing of human beings there would be a corresponding massing of certain nematodes. Trees would still stand in ghostly rows representing our streets and highways. The location of the various plants and animals would still be decipherable, and, had we sufficient knowledge, in many cases even their species could be determined by an examination of their erstwhile nematode parasites.

— Nathan Cobb, “Nematodes and Their Relationships,” Yearbook United States Department of Agriculture, 1914

(Thanks, Mick.)

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

https://commons.wikimedia.org/wiki/File:Diamond_ring_by_Jennifer_Dickert.jpg
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

https://pixabay.com/en/woman-artificial-intelligence-506322/

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

https://commons.wikimedia.org/wiki/File:Descartes_Circles.svg
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.

https://commons.wikimedia.org/wiki/File:ApollonianGasket-10_18_23_27-Labels.png
Image: Wikimedia Commons

Self Study

https://commons.wikimedia.org/wiki/File:Elements_of_Euclid_page_004_figure_01.svg

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