The Stable Marriage Problem

Given a group of 10 men and 10 women, all straight, is it always possible to pair them off in stable marriages, that is, to pair them so that there exist no man and woman who would prefer each other to the partners they have? Yes:

  • In the first round, each man who’s not yet engaged proposes to the woman he most prefers. Then each woman says “maybe” to the suitor she most prefers and rejects all the others. Now she and the suitor she hasn’t rejected are provisionally engaged.
  • In each following round, each man who’s not yet engaged proposes to the woman he most prefers and hasn’t yet approached. He does this even if she’s already engaged. Then each woman says “maybe” to her most preferred suitor, even if that means jilting her current provisional fiancé.

This process continues until everyone is engaged (as they must be, since every man must eventually propose to every woman and every woman must accept someone). All the marriages are stable because no man can end up pining for a woman who would prefer him to her own partner — that woman must already have rejected or jilted him at some point during the courting:

https://commons.wikimedia.org/wiki/File:Gale-Shapley.gif
Animation: Wikimedia Commons

In 1962, mathematicians David Gale and Lloyd Shapley showed that stable marriages can always be found for any equal number of men and women.

| Science & Math

Tact

https://commons.wikimedia.org/wiki/File:Richard_Porson_-_Imagines_philologorum.jpg

When Robert Southey boasted to Richard Porson of the greatness of his poem Madoc, Porson answered:

“Madoc will be read when Homer and Virgil are forgotten.”

| Literature

Podcast Episode 218: Lost in the Amazon

https://pixabay.com/en/jungle-ecuador-nature-green-beauty-240498/

In 1769, a Peruvian noblewoman set out with 41 companions to join her husband in French Guiana. But a series of terrible misfortunes left her alone in the Amazon jungle. In this week’s episode of the Futility Closet podcast we’ll follow Isabel Godin des Odonais on her harrowing adventure in the rain forest.

We’ll also learn where in the world “prices slippery traps” is and puzzle over an airport’s ingenuity.

See full show notes …

| History · Podcast

Line Limit

https://commons.wikimedia.org/wiki/File:Goat_(PSF).png

You own a goat and a meadow. The meadow is in the shape of an equilateral triangle each side of which is 100 meters long. The goat is tied to a post at one corner of the meadow. How long should you make the tether in order to give the goat access to exactly half the meadow?

Click for Answer
| Puzzles

An Actor’s Notes

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

Ellen Terry played Juliet at London’s Lyceum Theatre in 1882. The following was later found on the flyleaf of her copy of the text:

Get the words into your remembrance first of all. Then, (as you have to convey the meaning of the words to some who have ears, but don’t hear, and eyes, but don’t see) put the words into the simplest vernacular. Then exercise your judgment about their sound.

So many different ways of speaking words! Beware of sound and fury signifying nothing. Voice unaccompanied by imagination, dreadful. Pomposity, rotundity.

Imagination and intelligence absolutely necessary to realize and portray high and low imaginings. Voice, yes, but not mere voice production. You must have a sensitive ear, and a sensitive judgment of the effect on your audience. But all the time you must be trying to please yourself.

Get yourself into tune. Then you can let fly your imagination, and the words will seem to be supplied by yourself. Shakespeare supplied by oneself! Oh!

Realism? Yes, if we mean by that real feeling, real sympathy. But people seem to mean by it only the realism of low-down things.

To act, you must make the thing written your own. You must steal the words, steal the thought, and convey the stolen treasure to others with great art.

(From Donald Sinden, ed., The Everyman Book of Theatrical Anecdotes, 1987.)

| Art

Time Saver

Ogden Nash invented a streamlined limerick he called the “limick”:

An old person of Troy
In the bath is so coy
That it doesn’t know yet
If it’s a girl or a boy.

Two nudists of Dover,
When purple all over,
Were munched by a cow,
When mistaken for clover.

A cook called McMurray
Got a raise in a hurry
From his Hindu employer,
By flavouring curry.

A young flirt of Ceylon,
Who led the boys on,
Playing “Follow the Leda,”
Succumbed to a swan.

| Poems

For What It’s Worth

https://en.wikipedia.org/wiki/File:Cnl03.jpg

Based on an ancient Hindu game, Snakes and Ladders (Chutes and Ladders in ophidiophobic America) is at heart a morality lesson: As you progress by die roll from square 1 to square 100 and spiritual enlightenment, your way is complicated by virtues and vices. Landing on a snake (or chute) will send you back to an earlier square, and landing on a ladder will send you ahead to a later one. Each of these shortcuts is associated with a precept — “Carelessness” leads to “Injury,” “Study” leads to “Knowledge,” and so on.

In 1993 University of Michigan mathematician S.C. Althoen and his colleagues considered the game as a 101-state absorbing Markov chain. The shortest possible game lasts seven moves, the longest is infinite, and according to their calculations the expected number of moves in the Milton Bradley version of Chutes and Ladders is

\displaystyle \frac{225837582538403273407117496273279920181931269186581786048583}{5757472998140039232950575874628786131130999406013041613400},

which is about 39.2.

Troublingly, the average length of a game without snakes or ladders (just the 100-square board) is almost exactly 33 moves: “Apparently the snakes lengthen the game more than the ladders shorten it.” And, while adding a ladder will generally shorten the game and adding a snake will lengthen it, this isn’t always the case: In the original game, adding a ladder from square 79 to square 81 lengthens the expected playing time by more than two moves (to about 41.9), since it increases the chance of missing the important ladder leading from square 80 to square 100. And adding a snake from square 29 to square 27 shortens the game by more than a move (to about 38.0), since it offers a second chance at the long ladder from 28 to 84.

So, arguably, we might advance more quickly through life with more vice and less virtue.

(S.C. Althoen, L. King, and K. Schilling, “How Long Is a Game of Snakes and Ladders?”, Mathematical Gazette 77:478 [March 1993], 71-76.)

| Entertainment · Science & Math

Black and White

https://books.google.com/books?id=JTEVAAAAYAAJ&pg=PA96

I just ran across this in Benjamin Glover Laws’ The Two-Move Chess Problem, from 1890. It’s by G. Chocholous. White is to mate in two moves.

Click for Answer
| Puzzles

La

https://en.wikipedia.org/wiki/File:THXDeepNoteScore35thAnniversary.jpg

On its 35th anniversary, THX, the sound quality assurance company founded by George Lucas, released the original score of “Deep Note,” its audio trademark, which debuted at the premiere of Return of the Jedi in 1983 and is now familiar from countless films. Essentially it’s a stupendous D chord; the U.S. trademark registration reads:

The THX logo theme consists of 30 voices over seven measures, starting in a narrow range, 200 to 400 Hz, and slowly diverting to preselected pitches encompassing three octaves. The 30 voices begin at pitches between 200 Hz and 400 Hz and arrive at pre-selected pitches spanning three octaves by the fourth measure. The highest pitch is slightly detuned while there are double the number of voices of the lowest two pitches.

“I like to say that the THX sound is the most widely-recognized piece of computer-generated music in the world,” says James A. Moorer, who wrote it. “This may or may not be true, but it sounds cool.” And now that we have the score you can do this:

| Entertainment · Technology