From Lee Sallows:
(Thanks, Lee!)
Science & Math
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:
In 1962, mathematicians David Gale and Lloyd Shapley showed that stable marriages can always be found for any equal number of men and women.
For What It’s Worth
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
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.)
Math Notes
286 = 77371252455336267181195264
That’s the largest known power of 2 with no zeros in its decimal representation.
Are there higher such powers? No one knows.
Cube Route
Created by Franz Armbruster in 1967, “Instant Insanity” was the Rubik’s Cube of its day, a simple configuration task with a dismaying number of combinations. You’re given four cubes whose faces are colored red, blue, green, and yellow:
The task is to arrange them into a stack so that each of the four colors appears on each side of the stack. This is difficult to achieve by trial and error, as the cubes can be arranged in 41,472 ways, and only 8 of these give a valid solution.
One approach is to use graph theory — draw points of the four face colors and connect them to show which pairs of colors fall on opposite faces of each cube:
Then, using certain criteria (explained here), we can derive two directed subgraphs that describe the solution:
The first graph shows which colors appear on the front and back of each cube, the second which colors appear on the left and right. Each arrow represents one of the four cubes and the position of each of the two colors it indicates. So, for example, the black arrow at the top of the first graph indicates that the first cube will have yellow on the front face and blue on the rear.
This solution isn’t unique, of course — once you’ve compiled a winning stack you can rotate it or rearrange the order of the cubes without affecting its validity. B.L. Schwartz gives an alternative method, through inspection of a table, as well as tips for solving by trial and error using physical cubes, in “An Improved Solution to ‘Instant Insanity,'” Mathematics Magazine 43:1 (January 1970), 20-23.
Podcast Episode 217: The Bone Wars
The end of the Civil War opened a new era of fossil hunting in the American West — and a bitter feud between two rival paleontologists, who spent 20 years sabotaging one another in a constant struggle for supremacy. In this week’s episode of the Futility Closet podcast we’ll tell the story of the Bone Wars, the greatest scientific feud of the 19th century.
We’ll also sympathize with Scunthorpe and puzzle over why a driver can’t drive.
Turn, Turn, Turn
I just ran across this, offered by Morton C. Schwartz in an old issue of Pi Mu Episilon Journal:
Take any number of zeros and any number of ones and place them in a circle, in any order. Reproduce the circle a second time, concentrically with the first. Rotate either circle, and any number of places. The number of zeros opposite ones will always be even.
(Morton C. Schwartz, “An Amazing Parity Theorem,” Pi Mu Episilon Journal 5:7 [Fall 1972], 338.)
Room for More
When logician John Venn introduced the famous diagrams that bear his name, he expressed an interest in “symmetrical figures … elegant in themselves.” He thought the “simplest and neatest figure” that showed all possible logical relations among four sets was four equal ellipses arranged like this:
“It is obvious that we thus get the sixteen compartments that we want, counting, as usual, the outside of them all as one compartment. … The desired condition that these sixteen alternatives shall be mutually exclusive and collectively exhaustive, so as to represent all the component elements yielded by the four terms taken positively and negatively, is of course secured.”
Interestingly, he added that “with five terms combined together ellipses fail us”: Venn believed that it was impossible to create a Venn diagram with five ellipses. Amazingly, that assertion went unchallenged for nearly a century — it was only in 1975 that Branko Grünbaum found a diagram with five ellipses:
It’s not possible to form a Venn diagram with six or more ellipses. Do we even need one with five? According to Reddit, yes, we do:
(Peter Hamburger and Raymond E. Pippert, “Venn Said It Couldn’t Be Done,” Mathematics Magazine 73:2 [April 2000], 105-110.)
Magic
A ring that encircles a length of chain will be caught in a loop if it tumbles during its fall. By Newton’s Third Law, when the turning ring strikes the chain it transfers momentum to the loop at the end — which causes it to rise and swallow the ring.
Neat
I just ran across this in an old Mathematical Gazette: R.H. Macmillan of Buckinghamshire shared a tidy expression for the area of a triangle whose vertices have coordinates (x1, y1), (x2, y2), and (x3, y3):
The sign is positive if the numbering is counterclockwise and negative if it’s clockwise.
“The expression is readily derived geometrically (using only the fact that the sum of the areas on each side of the diagonal of a rectangle must be equal) and so provides an interesting elementary exercise.”
(R.H. Macmillan, “Area of a Triangle,” Mathematical Gazette 77:478 (March 1993), 88.)