Match everyone up so no one wants to swap partners
Ten men and ten women each privately rank everyone of the opposite sex from most to least preferred. You have to pair all twenty of them off into couples. Is it always possible to do this so that no man and woman who aren't paired together would both rather leave their current partners and be with each other instead?
Reveal the answer
Yes — always, no matter what the preference lists look like. Economists David Gale and Lloyd Shapley proved it in 1962 and gave a simple algorithm (rounds of proposing and provisionally rejecting) that finds such a 'stable matching' in at most a few hundred steps for twenty people. The same algorithm, refined by Alvin Roth, now matches real medical residents to hospitals and students to schools worldwide; Shapley and Roth shared the 2012 Nobel Memorial Prize in Economic Sciences for the work.