How Can You Prove the Existence of a Function in POTW #223?

[Ackbach]

Here is this week's POTW:

-----

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) \not\in 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.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Re: Problem Of The Week # 223 - Jul 05, 2016

This was Problem A-4 in the 1996 William Lowell Putnam Mathematical Competition.

No one answered this week's POTW. The solution, attributed to Kiran Kedlaya and his associates, follows:

Spoiler

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}, \dots, 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, \dots, 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, \dots, 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
\begin{align*}
(a_{i+k+1}, z, a_{i+k}), &(a_{i+k}, z, a_{i}) \in S \\
&\Rightarrow (a_{i+k}, a_{i+k+1}, z), (z, a_{i}, a_{i+k}) \in S \\
&\Rightarrow (a_{i+k+1},z,a_{i}) \in S.
\end{align*}
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_{i}, a_{i+1}, a_{j}), (a_{j},
a_{j+1}, a_{i}) \in S$ by the
assumption on $G$. Therefore
\begin{align*}
(a_{i}, z, a_{i+1}), (a_{i+1}, a_{j}, a_{i}) \in S
&\Rightarrow (a_{j}, a_{i}, z) \in S \\
(a_{i}, z, a_{j}), (a_{j}, a_{j+1}, a_{i}) \in S
&\Rightarrow (z, a_{j}, a_{j+1}),
\end{align*}
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 \Rightarrow (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.