Problem: Given a set $S$ of $n$ variables, a binary operation $\times$ on $S$ is called
\textit{simple} if it satisfies $(x \times y) \times z = x \times (y \times z)$
for all $x,y,z \in S$ and $x \times y \in \{x,y\}$ for all $x,y \in S$.
Given a simple operation $\times$ on $S$, any string of elements in $S$
can be reduced to a single element, such as $xyz \to x \times (y \times z)$.
A string of variables in $S$ is called \textit{full}
if it contains each variable in $S$ at least once,
and two strings are \textit{equivalent} if they evaluate to the
same variable regardless of which simple $\times$ is chosen.
For example $xxx$, $xx$, and $x$ are equivalent, but these are only full if $n=1$.
Suppose $T$ is a set of full strings such that any full string is
equivalent to exactly one element of $T$. Determine the number of elements of $T$.

\end{enumerate}

Solution: The answer is $(n!)^2$.
In fact it is possible to essentially find all $\times$:
one assigns a real number to each variable in $S$.
Then $x \times y$ takes the larger of $\{x,y\}$,
and in the event of a tie picks either ``left'' or ``right'',
where the choice of side is fixed among elements of each size.

\paragraph{First solution (Steven Hao).}
The main trick is the two lemmas, which are not hard to show
(and are motivated by our conjecture).
\begin{align*}
  xx &= x \\
  xyxzx &= xyzx.
\end{align*}

Consequently, define a \textbf{double rainbow}
to be the concatenation of two full strings of length $n$,
of which there are $(n!)^2$.
We claim that these form equivalence classes for $T$.

To see that any string $s$ is equivalent to a double rainbow,
note that $s = ss$, and hence using the second identity above
repeatedly lets us reduce $ss$ to a double rainbow.

To see two distinct double rainbows $R_1$ and $R_2$ aren't equivalent,
one can use the construction mentioned in the beginning.
Specifically, take two variables $a$ and $b$ which do not
appear in the same order in $R_1$ and $R_2$.
Then it's not hard to see that $abab$, $abba$, $baab$, $baba$
are pairwise non-equivalent by choosing ``left'' or ``right'' appropriately.
Now construct $\times$ on the whole set
by having $a$ and $b$ be the largest variables,
so the rest of the variables don't matter in the evaluation of the string.

\paragraph{Second solution outline (Ankan Bhattacharya).}
We outline a proof of the characterization claimed earlier,
which will also give the answer $(n!)^2$.
We say $a \sim b$ if $ab \neq ba$.
Also, say $a > b$ if $ab = ba = a$.
The following are proved by finite casework,
using the fact that $\{ab, bc, ca\}$ always has exactly
two distinct elements for any different $a$, $b$, $c$.
\begin{itemize}
  \ii If $a > b$ and $b > c$ then $a > c$.
  \ii If $a \sim b$ and $b \sim c$
  then $ab = a$ if and only if $bc = b$.
  \ii If $a \sim b$ and $b \sim c$ then $a \sim c$.
  \ii If $a \sim b$ and $a > c$ then $b > c$.
  \ii If $a \sim b$ and $c > a$ then $c > b$.
\end{itemize}
This gives us the total ordering on the elements
and the equivalence classes by $\sim$.
In this we way can check the claimed operations are the only ones.

We can then (as in the first solution) verify that every full string
is equivalent to a unique double rainbow --- but this
time we prove it by simply considering all possible $\times$,
because we have classified them all.