Putnam 1996/A4 solution

Putnam 1996

Problem A4

A is a finite set. S is a set of ordered triples (a, b, c) of distinct elements of A, such that:
(a, b, c) ∈ S iff (b, c, a) ∈ S;
(a, b, c) ∈ S iff (c, b, a) ∉ S;
(a, b, c) and (c, d, a) ∈ S iff (b, c, d) and (d, a, b) ∈ S.
Prove that there exists an injection g from A to the reals, such that g(a) < g(b) < g(c) implies (a, b, c) ∈ S.

Solution

Easy.

Fix any element a in A. Now define < on the other elements of A by b < c iff (a, b, c) is in S. We check that < is a total order on the other elements. If b < c and c < d, then (a, b, c) and (a, c, d) are in S, so (a, b, d) is in S and hence b < d, so the relation is transitive. Also for distinct b, c just one of (a, b, c) and (a, c, b) is in S, so just one of b < c, c < b is true.

Now extend this ordering to A, by taking a < b for all b ≠ a. Finally, arrange the elements of A in order a₁ < a₂ < a₃ < ... < a_n and define g(a_i) = i. Then g has the required property.

Putnam 1996