Putnam 1996, Problem A-4

Let \( S \) be the set of ordered triples \( (a,b,c) \) of distinct elements of a finite set \( A \). Suppose that  
1. \( (a,b,c) \in S \) if and only if \( (b,c,a) \in S \);  
2. \( (a,b,c) \in S \) if and only if \( (c,b,a) \notin S \);  
3. \( (a,b,c) \) and \( (c,d,a) \) are both in \( S \) if and only if \( (b,c,d) \) and \( (d,a,b) \) are both in \( S \).  

Prove that there exists a one-to-one function \( g \) from \( A \) to \( R \) such that \( g(a) < g(b) < g(c) \) implies \( (a,b,c) \in S \). Note: \( R \) is the set of real numbers.

Solution:
In fact, we will show that such a function \(g\) exists with the property that \((a, b, c) \in S\) if and only if \(g(d) < g(e) < g(f)\) for some cyclic permutation \((d, e, f)\) of \((a, b, c)\). We proceed by induction on the number of elements in \(A\). If \(A = \{a, b, c\}\) and \((a, b, c) \in S\), then choose \(g\) with \(g(a) < g(b) < g(c)\), otherwise choose \(g\) with \(g(a) > g(b) > g(c)\).  

Now let \(z\) be an element of \(A\) and \(B = A - \{z\}\). Let \(a_1, \ldots, a_n\) be the elements of \(B\) labeled such that \(g(a_1) < g(a_2) < \cdots < g(a_n)\). We claim that there exists a unique \(i \in \{1, \ldots, n\}\) such that \((a_i, z, a_{i+1}) \in S\), where hereafter \(a_{n+k} = a_k\).  

We show existence first. Suppose no such \(i\) exists; then for all \(i, k \in \{1, \ldots, n\}\), we have \((a_{i+k}, z, a_i) \notin S\). This holds by property 1 for \(k = 1\) and by induction on \(k\) in general, noting that  
\[
(a_{i+k+1}, z, a_{i+k}), (a_{i+k}, z, a_i) \in S \implies (a_{i+k}, a_{i+k+1}, z), (z, a_i, a_{i+k}) \in S \implies (a_{i+k+1}, z, a_i) \in S.
\]  

Applying this when \(k = n\), we get \((a_{i-1}, z, a_i) \in S\), contradicting the fact that \((a_i, z, a_{i-1}) \in S\). Hence existence follows.  

Now we show uniqueness. Suppose \((a_i, z, a_{i+1}) \in S\); then for any \(j \neq i - 1, i, i + 1\), we have \((a_j, a_{i+1}, a_j), (a_j, a_{j+1}, a_i) \in S\) by the assumption on \(G\).  

Therefore  
\[
(a_i, z, a_{i+1}), (a_{i+1}, a_j, a_i) \in S \implies (a_j, a_i, z) \in S, \quad (a_i, z, a_j), (a_j, a_{j+1}, a_i) \in S \implies (z, a_j, a_{j+1}) \in S,
\]  
so \((a_j, z, a_{j+1}) \notin S\). The case \(j = i + 1\) is ruled out by  
\[
(a_i, z, a_{i+1}), (a_{i+1}, a_{i+2}, a_i) \in S \implies (z, a_{i+1}, a_{i+2}) \in S
\]  
and the case \(j = i - 1\) is similar.  

Finally, we put \(g(z)\) in \((g(a_n), +\infty)\) if \(i = n\), and \((g(a_i), g(a_{i+1}))\) otherwise; an analysis similar to that above shows that \(g\) has the desired property.