Prologue

In the court of King Arthur 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 even 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 find the reason why such a pairing could not exist. He 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 these knights?”, and when all said “No!”, Merlin said: “O King, how can you command me to find a husband for each of these 56 ladies among the remaining 55 knights?” So the king, whose courtly education did include the pigeonhole principle, saw that in this case Merlin had spoken the truth and he graciously dismissed him.