Frank Morgan

April 5, 2002

OLD CHALLENGE. Prove the Marriage Theorem, which says that if equal-sized groups of men and women each have a preference order for members of the other group, it is possible to pair them off in a stable way (meaning there is no alternate potential couple who prefer each other to their own mates).

ANSWER (Joe Shipman). The following iterative matchmaking procedure achieves a stable pairing of any equal-sized sets of men and women.

1) Each man who hasn’t yet been paired proposes to the most desirable woman he hasn’t previously proposed to.

2) Each propositioned woman compares her most desirable proposer with her current partner. If she likes the proposer better or has no partner she accepts the proposal (dumping her partner); otherwise she rejects the proposal.

Repeat steps 1-2 until there are no proposals in step 1.

This procedure must come to an end because no man proposes to any woman twice. At the end everyone will be paired (an unpaired man would propose to an unpaired woman, since she couldn’t have previously rejected him or she’d be paired).

Proof that the final pairing is stable: if a man prefers a woman to his current partner, he must have already proposed to and been rejected by that woman, who therefore cannot prefer him to her current partner because she can have only improved her lot since rejecting him.

Incidentally, without a good procedure, an endless cycle of formations of new couples is possible with three couples: AP BP BQ CQ CR AR (keeps repeating). Here P prefers B to A, etc.

QUESTIONABLE MATHEMATICS. Joe Shipman notes a Washington Post Online report about how the results of polls of Islamic countries were simply averaged together without regard for the size of the country. A population-weighted average would have been appropriate.

Readers are invited to submit more examples of questionable mathematics.

It’s a miracle the way the world fits together, lot against lot, road meeting road, one jagged property line meshing perfectly with the neighbor’s. The whole land with its homes and factories and streets continues thousands of miles right up to the edge of the ocean, and stops right there. At hole in the ocean off the coast is filled perfectly by a small island. Under our feet the earth descends thousands of miles and stops precisely at the other side. The seas rise to where the atmosphere begins, itself then rising seamlessly, except for a few gaps perfectly filled by clouds and airplanes, to the very edge of outer space.

In like manner the moments of our lives continue seamlessly from birth to death. We sleep until the moment we wake. Our morning preparations, measured and totaled, add up precisely to our moment of departure. Our commute lasts precisely to the moment we arrive at work. Each project, conversation, break, or moment’s rest, summed and totaled, tallies precisely with the extent of our working day. Every second of our free time is used for some task, recreation, or rest, and not a second more. The events of a lifetime, down to the smallest thought or chuckle, added up moment by moment, tally perfectly with its whole span. It’s a miracle how it all fits.

NEW CHALLENGE. If you had to disappear, so that no one could find you, where would you go to live?

Copyright 2002, Frank Morgan.

Send answers, comments, and new questions by email to [email protected] to be eligible for Flatland and other book awards. Winning answers will appear in the next Math Chat. Math Chat appears on the first and third Thursdays of each month. Prof. Morgan’s homepage is at www.williams.edu/Mathematics/fmorgan.

THE MATH CHAT BOOK, including a $1000 Math Chat Book QUEST, questions and answers, and a list of past challenge winners, is now available from the MAA (800-331-1622).