S and T and finite sets. U is a collection of ordered pairs (s, t) with s ∈ S and t ∈ T. There is no element s ∈ S such that all possible pairs (s, t) ∈ U. Every element t ∈ T appears in at least one element of U. Prove that we can find distinct s1, s2 ∈ S and distinct t1, t2 ∈ T such that (s1, t1), (s2, t2) ∈ U, but (s1, t2), (s2, t1) ∉ U.
Suppose that we cannot find such si, ti. We will establish a contradiction.
Take t in T. Suppose that there are n distinct s in S such that (s, t) is in U. Suppose n > 0. Then take a specific s' such that (s', t) is in U. There must be some t' such that (s', t') is not in U. Now consider whether we have (s, t') in U. If (s, t) is not in U, then (s, t') cannot be in U (or we would have found si, ti). But there are at most n-1 distinct s such that (s, t') is in U (the only candidates are the cases for which (s, t) is in U, and one of those, namely s', does not work).
Iterating, we must eventually get some x in T for which there is no s in S with (s, x) in U. Contradiction.
26th Putnam 1965
© John Scholes
25 Jan 2002