15 A Glimpse of Complexity and Cryptography
15.1 A Connecticut Class in King Arthur’s Court.........
In the court of King Arthur^1 there dwelt 150 knights and 150 ladies-in-
waiting. The king decided to marry them off, but the trouble was that
some pairs hated each other so much that they would not get married, let
alone speak! King Arthur tried several times to pair them off but each time
he ran into conflicts. So he summoned Merlin the Wizard and ordered him
to find a pairing in which every pair was willing to marry. Now, Merlin had
supernatural powers, and he saw immediately that none of the 150! possible
pairings was feasible, and this he told the king. But Merlin was not only a
great wizard, but a suspicious character as well, and King Arthur did not
quite trust him. “Find a pairing or I shall sentence you to be imprisoned
in a cave forever!” said Arthur.
Fortunately for Merlin, he could use his supernatural powers to browse
forthcoming scientific literature, and he found several papers in the early
twentieth century that gave thereasonwhy such a pairing could not exist.
He went back to the king when all the knights and ladies were present, and
asked a certain 56 ladies to stand on one side of the king and 95 knights on
the other side, and asked, “Is any one of you ladies willing to marry any of
(^1) From L. Lov ́asz and M.D. Plummer:Matching Theory,Akad ́emiai Kiad ́o, North
Holland, Budapest, 1986 (with slight modifications), with the kind permission of Mike
Plummer. The material was developed as a handout at Yale University, New Haven,
Connecticut.