The Reminiscence Bump

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

If you seem to recall your adolescence and early adulthood years more clearly than your later life, that’s normal. Most of us can recall a disproportionate number of autobiographical memories made between ages 10 and 30, perhaps because of the important changes in identity, goals, attitudes, and beliefs that most of us went through in those years. (Also, that’s the span in which many of us have novel experiences such as graduation, marriage, and the birth of a child.)

Interestingly, this phenomenon extends to favorite books, movies, and records. In a 2007 study, psychologist Steve M.J. Janssen and his colleagues at the University of Amsterdam found that subjects best recorded memories of these things between 11 and 25. This is particularly true of music: Items that aren’t revisited frequently, such as books, are more likely to be forgotten, but records have a strong “reminiscence bump.”

“Books are read two or three times, movies are watched more frequently, whereas records are listened to numerous times. The results suggest that differential encoding initially causes the reminiscence bump and that re-sampling increases the bump further.” See the appendices for lists of favorite books, movies, and records and the average ages at which subjects first encountered them.

(Steve M.J. Janssen, Antonio G. Chessa, and Jaap M.J. Murre, “Temporal Distribution of Favourite Books, Movies, and Records: Differential Encoding and Re-Sampling,” Memory 15:7 [2007], 755-767.)

The Dining Cryptographers Problem

https://commons.wikimedia.org/wiki/File:Dining_Cryptographers.svg
Image: Wikimedia Commons

Three cryptographers are having dinner at their favorite restaurant. The waiter informs them that arrangements have been made for their bill to be paid anonymously. It may be that the National Security Agency has picked up the tab, or it may be that one of the cryptographers himself has done so. The cryptographers respect each other’s right to pay the bill anonymously, but they want to know whether the NSA is paying. Happily, there is a way to determine this without forcing a generous cryptographer to reveal himself.

Each cryptographer flips a fair coin behind a menu between himself and his right-hand neighbor, so that only the two of them can see the outcome. Then each cryptographer announces aloud whether the two coins he can see — one to his right and one to his left — had the same outcome or different outcomes. If one of the cryptographers is the payer, he states the opposite of what he sees. If an even number of cryptographers say that they saw different outcomes, then the NSA paid; if an odd number say so, then one of the cryptographers paid the bill, but his anonymity is protected.

Computer scientist David Chaum offered this example in 1988 as the basis for an anonymous communication network; these networks are often referred to as DC-nets (for “dining cryptographers”).

(David Chaum, “The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability,” Journal of Cryptology 1:1 [1988], 65-75.)

Bases Into Gold

You have 12 coins that appear identical. Eleven have the same weight, but one is either heavier or lighter than the others. How can you identify it, and determine whether it’s heavy or light, in just three weighings in a balance scale?

This is a classic puzzle, but in 1992 Washington State University mathematician Calvin T. Long found a solution “that appears little short of magic.” Number the coins 1 to 12 and make three weighings:

First weighing: 1 3 5 7 vs. 2 4 6 8
Second weighing: 1 6 8 11 vs. 2 7 9 10
Third weighing: 2 3 8 12 vs. 5 6 9 11

To solve the problem, note the result of each weighing and assemble a three-digit numeral in base 3 as follows:

Left pan sinks: 2
Right pan sinks: 0
Balance: 1

For example, if coin 7 is light, that produces the number 021 in base 3. Now converting that to base 10 gives 7, the number of the odd coin, and an examination of the weighings shows that it must be light. Another example: If coin 2 is heavy, then we get 002 in base 3, which is 2 in base 10. Note that it’s possible to get an answer that’s higher than 12, e.g. when coin 7 is heavy — in that case subtract the base-10 answer you get from 26.

Another curious method to solve the classic puzzle, this one involving verbal mnemonics, appeared in Eureka in 1950.

(Calvin T. Long, “Magic in Base 3,” Mathematical Gazette 76:477 [November 1992], 371-376.)

09/30/2018 UPDATE: Due to an error in the original paper, the weighings I originally specified don’t work in every case — in the third weighing, the left pan should contain 2 3 8 12, not 1 2 8 12. I’ve amended this in the post above; everything should work now. Sorry for the error; thanks to everyone who wrote in.

Maekawa’s Theorem

https://commons.wikimedia.org/wiki/File:Kawasaki%27s_theorem.jpg
Image: Wikimedia Commons

A neat observation by Japanese mathematician Jun Maekawa: If an origami model can be flattened without damage, then at any vertex (meeting of edges) in its crease pattern the number of “valley” folds and “mountain” folds always differ by two.

The single-vertex crease pattern above has five mountain folds (folds whose outer surface is colored) and three valley folds (folds whose inner surface is colored). (The fifth mountain fold is a bit hard to notice in this example — it’s folded flat at bottom right.)

One consequence of this is that every vertex has an even number of creases, and therefore that the regions between the creases can be colored with two colors.

Paper folder Toshikazu Kawasaki found a related theorem: At any vertex, the sum of all the odd angles is 180 degrees (and likewise the even).

“A Geological Parable”

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

It was at the place afterwards called Solenhofen. The weather was miserable, as Jurassic weather usually was. The rain beat steadily down, and carbon dioxide was still upon the earth.

The Archaeopteryx was feeling pretty gloomy, for at that morning’s meeting of the Amalgamated Association of Enaliosaurians he had been blackballed. He was looked down upon by the Pterodactyl and the Ichthyosaurus deigned not to notice him. Cast out by the Reptilia, and Aves not being thought of, he became a wanderer upon the face of the earth. ‘Alas!’ sighed the poor Archaeopteryx, ‘this world is no place for me.’ And he laid him down and died; and became imbedded in the rock.

And ages afterward a featherless biped, called man, dug him up, and marvelled at him, crying, ‘Lo, the original Avis and fountain-head of all our feathered flocks!’ And they placed him with great reverence in a case, and his name became a by-word in the land. But the Archaeopteryx knew it not. And the descendant for whom he had suffered and died strutted proudly about the barn-yard, crowing lustily cock-a-doodle-do!

— Samuel P. Carrick Jr., in The Fly Leaf, January 1896

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.

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

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:

https://commons.wikimedia.org/wiki/File:Instant_insanity_Cube.png
Image: Wikimedia Commons

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:

https://commons.wikimedia.org/wiki/File:Instant_sanity_graph.png
Image: Wikimedia Commons

Then, using certain criteria (explained here), we can derive two directed subgraphs that describe the solution:

https://commons.wikimedia.org/wiki/File:Instant_insanity_final.png
Image: Wikimedia Commons

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.