Given a set $S$ of $n$ variables, a binary operation $\times$ on $S$ is called 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 $x y z \rightarrow x \times(y \times z)$. A string of variables in $S$ is called full if it contains each variable in $S$ at least once, and two strings are equivalent if they evaluate to the same variable regardless of which simple $\times$ is chosen. For example $x x x, x x$, 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$.
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.

First solution (Steven Hao). The main trick is the two lemmas, which are not hard to show (and are motivated by our conjecture).
$$
\begin{aligned}
x x & =x \\
x y x z x & =x y z x .
\end{aligned}
$$

Consequently, define a 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=s s$, 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 $a b a b, a b b a$, $b a a b, b a b a$ 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.

ब 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 $a b \neq b a$. Also, say $a>b$ if $a b=b a=a$. The following are proved by finite casework, using the fact that $\{a b, b c, c a\}$ always has exactly two distinct elements for any different $a, b, c$.
- If $a>b$ and $b>c$ then $a>c$.
- If $a \sim b$ and $b \sim c$ then $a b=a$ if and only if $b c=b$.
- If $a \sim b$ and $b \sim c$ then $a \sim c$.
- If $a \sim b$ and $a>c$ then $b>c$.
- If $a \sim b$ and $c>a$ then $c>b$.

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.