Suppose we have a group of n men and n women. Each of the women can find some subset of the men whom she would be happy to marry. And each of the men would be happy with any woman who will have him. Is it always possible to pair everyone off into happy marriages?

Clearly this won’t work if, for example, two of the women have their hearts set on the same man and won’t be happy with anyone else. In general, for any subset of the women, we need to be sure that they can reconcile their preferences so that each of them finds a mate.

Surprisingly, though, that’s all that’s required. So long as every subset of women can collectively express interest in a group of men at least as numerous as their own, it will always be possible to marry off the whole group into happy couples.

The theorem was proved by English mathematician Philip Hall in 1935. Another application of the same principle: Shuffle an ordinary deck of 52 playing cards and deal it into 13 piles of 4 cards each. Now it’s always possible to assemble a run of 13 cards, ace through king, by drawing one card from each pile.