I have tried this problem and I got some ways to understand it, not unique. For example, if I consider $\times$ as the operation $\max$, then the "simple" operation in this case also satifies two given conditions and $|T| = 1$. (the same to $\min$) But if I consider $\times$ as: $x \times y = x$ (chose the left one) and $|T| = n$. (the same to chose the right one) In total, I can't make sure about the definition of $\times$. Hope someone can make it clearly!

$\times$ is defined as a simple operation. $|T|$ is constant. Two strings are equivalent if they evaluate to the same string (Edit: oops I meant variable) regardless of what $\times$ is chosen to be.

AceOfDiamonds wrote: $\times$ is defined as a simple operation. $|T|$ is constant. Two strings are equivalent if they evaluate to the same string (Edit: oops I meant variable) regardless of what $\times$ is chosen to be. If you say $|T|$ is constant, how about my two examples?

Your interpretation seems to be Pick a simple $\times$. Define two strings to be equivalent if they evaluate to the same variable under this specific $\times$. Compute $|T|$, the number of equivalence classes, for this $\times$. The problem statement is asking this: Define two strings to be equivalent if they evaluate to the same variable for every simple $\times$. Compute $|T|$, the number of equivalence classes.

Here is my solution.

Hmmm

Probably not as good as the above one, but oh well.

For some reason my solution looks a lot shorter than either of these, and it didn't seem that hard to find... maybe I got lucky

Very nice problem

First, construct a partially directed graph on the alphabet. For two letters $x$ and $y$, we draw a directed edge $x\rightarrow y$ if $x\times y=y\times x=y$, draw a simple edge $x-y$ if $x\times y=x$ and $y\times x=y$, and draw no edge if $x\times y=y$ and $y\times x=x$. In other words, a directed edge signifies evaluate to where the edge is directed, a simple edge signifies evaluate left, and no edge signifies evaluate right. Now, we classify all such graphs for which $\times$ is associative, or simple. The first claim is that there are no directed cycles. Indeed, if $a\rightarrow b\rightarrow c\rightarrow a$, then we have at the same time $abc=bc=c$ and $abc=ac=a$, a contradiction. Next, we show that if $a$ is simply connected to both $b$ and $c$, then $b$ and $c$ are also simply connected. Indeed, if $b$ and $c$ are disconnected or $b\rightarrow c$ then we have at the same time $bac=bc=c$ and $bac=ba=b$, a contradiction. Note that we may analogously show that if $a$ is disconnected from $b$ and $c$, then $b$ and $c$ are also disconnected. Then, we show that we cannot have a triangle consisting of a simple edge, a directed edge, and a disconnection. Indeed, note that if $a-b\rightarrow c$ and $a$ and $c$ are not connected then we have at the same time $cba=ca=a$ and $cba=cb=c$, a contradiction. Analogously, if $a-b\leftarrow c$ and $a$ and $c$ are not connected then we have at the same time $abc=ac=c$ and $abc=ab=a$. Finally, we show that the directed edges from a poset, i.e. transitivity holds or $a\rightarrow b\rightarrow c$ means that $a\rightarrow c$. Indeed, we cannot have $a\leftarrow c$ as there are no cycles. Otherwise, if $a-c$ then we have at the same time $bac=bc=c$ and $bac=ba=b$ and if $a$ and $c$ are disconnected then we have at the same time $bca=ca=a$ and $bca=ba=b$, a contradiction. Now, the structure of the graph is clear. No vertex can be part of both a simple edge and a disconnection and simple edges and disconnections form cliques, so the vertices may be partitioned into equivalence classes of either simple edges or disconnections. The rest of the edges must form a transitive multipartite digraph among the equivalence classes. We impose a poset on the alphabet with its directed edges and note that any two elements from different anti chains are comparable. Thus, any full string evaluates to either the leftmost maximal element or the rightmost maximal element of the poset, depending on if the anti chain of maximum elements form a clique or the compliment of a clique. It is clear that any such $\times$ works. Now, for each full string define its left permutation as the permutation of the alphabet obtained by erasing every occurrence of each letter that is not the first occurrence and its right permutation as the permutation of the alphabet obtained by erasing every occurrence of each letter that is not the last occurrence. It is clear by the poset evaluation method that any full string is equivalent to its double permutation, the concatenation of its left and right permutation. Furthermore, no two double permutations are equivalent, as we can easily construct a poset that evaluates the two double permutations differently. Hence, we have $n!^2$ equivalence classes, and we are done.

The answer is $(n!)^2$. We split the solution into three parts. Part I : Description of Equivalence Classes Given a string $s$, we define the left permutation $\sigma_L(s)$ as the order of the first occurrence of each letter when reading from left to right and define the right permutation $\sigma_R(s)$ similarly but we read from right to left instead. For example if $n=4$, $$s = acadcbdab \implies \begin{cases}\sigma_L(s) &= (a,c,d,b) \\ \sigma_R(s) &= (b,a,d,c) \end{cases}$$Define the signature of $s$ as $(\sigma_L(s), \sigma_R(s))$. The main claim is this signature describes each equivalence class. Part II : Any string with the same signature are equivalent Fix any simple operation. As usual, abbreviate $x\times y$ as $xy$. We claim that Claim: $xaxbx = xabx$ for any $x,a,b\in S$. Proof: Straightforward casework. If $ax=a$, then $x(ax)bx = xabx$, done. If $xb=b$, then $xa(xb)x = xabx$, done. Otherwise, assume that $ax = x$ and $xb=x$. Then $x(ax)bx = xxbx = xxx = x$. Therefore it suffices to show that $xabx = x$. If $ab = a $, then $xabx = x(ax) = xx = x$, done. If $ab = b$, then $xabx = (xb)x = xx = x$, done. $\blacksquare$ For each letter $x\in S$, perform the following algorithm to reduce the string preserving equivalency and signature. If $x$ appear exactly once, we replace $x$ with $xx$. If $x$ appear more than twice, by the claim, we can remove one in the middle remaining equivalency. At this point, each letter appear exactly twice. We label each letter with subscript $L$ if it's the left one and with subscript $R$ if it's the right one. We give another reduction algorithm. Claim: $axabyb = axbayb$ Proof: Use the first claim twice. \begin{align*} (axba)yb &= (axaba)yb \\ &= axa(bayb) \\ &= axa(babyb) \\ &= ax(abab)yb \\ &= axabyb & \blacksquare \end{align*} This claim means given $a_Rb_L$ appeared somewhere for some $a,b\in S$, we can replace with the following $$\hdots a_L\hdots a_Rb_L\hdots b_R \hdots= \hdots a_L\hdots b_La_R\hdots b_R \hdots$$while retaining equivalency. That means eventually, we can move all the $L$-letters to the left side and the $R$-letters to the right side. The resulting string must bijectively correspond to the signature so we are done. Part III : Any two strings with different signatures are not equivalent We give a family of simple operations. Partition $S = A\cup B$ arbitrarily. We define the operation by the following rules. $ab = ba = a$ for each $a\in A$, $b\in B$. $a_1a_2 = a_1$ for each $a_1,a_2\in A$. $b_1b_2 = b_1$ for each $b_1,b_2\in B$. One can check easily that this operation is indeed simple. Observe that a full string $s$ will evaluate into the leftmost letter which is in $A$. Now, consider two string $s,t$. WLOG $\sigma_1=\sigma_L(s)$ and $\sigma_2= \sigma_L(t)$ are different (otherwise reverse everything) and let $k$ be the smallest index which $\sigma_1(k), \sigma_2(k)$ differs. Pick $$B = \{\sigma_1(1), \sigma_1(2),\hdots,\sigma_1(k-1)\}$$so that $s,t$ will be evaluated to $\sigma_1(k)$ and $\sigma_2(k)$ respectively. This gives a contradiction.

The answer is $\boxed{(n!)^2}$. We take a moment to characterize all simple functions. Claim 1. All simple functions can be characterized in the following fashion. Group the elements of $S$ into $k$ levels, numbered from $1$ to $k$. For each level with $\geq 2$ elements, assign a direction left or right. Then $x \times y$ is $x$, if it is on a lower level than $y$. $y$, if it is on a lower level than $x$. $x$, if both are on the same level, and it is oriented left. $y$, if both are on the same level, and it is oriented right. Proof. All such functions are simple, so it remains to show all simple functions take on this form. To do this, we use induction, with the base case $n=1$ being trivial. Say $S$ is equipped with a simple $\times$ following the above. Then the semigroup $\{S\backslash \{z\}, \times\}$ can be ordered into levels by induction. Let $\ell$ be the least-leveled element such that $\ell \times z \neq z \times \ell$. If $\ell$ was on its own level we can assume $\ell \times z = \ell$. If not, without loss of generality it is on a left level. Then FTSoC say $\ell \times z = z$. Then for another element $\ell'$ on the same level as $\ell$, we have $$\ell' = \ell' \times \ell = \ell' \times (z \times \ell) = (\ell' \times z) \times \ell \implies \ell' \times z = \ell'.$$But then $\ell = \ell \times \ell' = \ell \times (\ell' \times z) = (\ell \times \ell') \times z = \ell \times z = z$, contradiction. Moreover, for all $L$ on a lower level than $\ell$, we have $$L \times z = (L \times \ell) \times z = L \times (\ell \times z) = L \times \ell = L,$$and similarly $z \times L = L$. In addition, for all $l$ on a higher level than $\ell$, we have $$z \times l = (z \times \ell) \times l = z \times (\ell \times l) = z \times \ell = z.$$Similarly, $l \times z = z$. So we have that $z$ is on the same level as $\ell$, as desired. $\square$ We now turn back to the problem. Note that, with the above theorem, the result of any full string is simply the leftmost or rightmost level 1 element (depending on whether level 1 is left-oriented or right-oriented). Thus, the output of a string under different level 1s is uniquely determined from the appearance of its characters left-to-right and right-to-left. There are $(n!)^2$ such orders, as desired. Remark. Simple functions are actually known as quasitrivial semigroups and can be found at https://arxiv.org/abs/1811.11113.

Probably same as the above post, but I think this is a very natural way of thinking about this problem:

Interpret a simple operation as a directed graph. The vertices are the $n$ values, and place an edge $x\to y$ to represent the value of $x\times y$ for each pair $(x,y)$ (there are $n^2$ edges). Color an edge blue if the corresponding operation returns the first element, and red otherwise. Notice that the associativity of the operation actually means that the blue and red subgraphs are transitive (you can check this trivially). We will now divide the graph into maximal monochromatic "complete subgraphs" meaning every edge (both directions) in such sets of vertices is the same color, and call such subgraphs $\textit{cores}$. From transitivity we get that all vertices inside a core have the same edges with the ones outside (the whole core acts as one vertex). We now conclude from transitivity and the maximality of cores that, for any two cores $\mathcal{A}$ and $\mathcal{B}$, all the edges from $\mathcal{A}$ to $\mathcal{B}$ are blue and the reverse edges are red, or vice versa. Now from transitivity we get that the cores are sorted in such a way where if one core is above another it will point to it in blue. This fully characterizes the simple operations. Returning to the language of the problem, an operation always prioritizes the characters which are in a "higher" core, and in a core it prioritizes either the first or last appearing character, meaning every full string evaluates to the first or last character from the highest core. Since we can find operations with arbitrary highest core, what we care about is the ordering in which every character appears for the first and last time, thus every full string is equivalent to exactly one string of length $2n$ where the first and last $n$ characters are all different (the first $n$ are the order in which they first appear in that string while the last $n$ are for the last appearance). This gives the answer of $(n!)^2$.

We will show that the set of strings $T$ containing all strings of the form $P_1P_2$ works, where $P_1,P_2$ are permutations of the $n$ variables $a_1,a_2,\dots,a_n.$ First, we prove the following lemma: If a string contains some variable $x$ three times, then the middle $x$ can be removed to produce an equivalent string. Proof: These three $x$ split our string into four sections that reduce to $a,b,c,d,$ such that our string is equivalent to $axbxcxd.$ Because of associativity, it suffices to show that $xbxcx$ is equivalent to $xbcx.$ We may assume that $b,c \ne x$ as otherwise it is trivial. Suppose that there is some operation $\times$ where these two strings evaluate differently. We can see that we must have $x \times b = b$ and $b \times x = x.$ Similarly, we can get that $c \times x = c$ and $x \times c = x.$ However, now if we have $b \times c = b,$ then we have $x = b \times x = (b \times c) \times x = b \times (c \times x) = b \times c = b,$ which is a contradiction. Similarly, if $b \times c = c,$ we have $c = b \times c = (x \times b) \times c = x \times (b \times c) = x \times c = x,$ which is another contradiction. Therefore, our assumption must have been false, and so the proof is complete. Now, we will prove that any full string is equivalent to one of these strings in our $T.$ Consider any full string $S.$ We will consider the string $SS$ which is formed by two copies of $S.$ Clearly this string is equivalent to $S.$ However, now consider any variable $x.$ We may remove all copies of $x$ from $SS$ except for the first and last. Notice that if $x$ appears $n$ times in $S,$ then $n-1$ copies of $x$ will be removed from each $S.$ Additionally, notice that the first $x$ must come from the first $S$ and the last $x$ must come from the last $S.$ Thus, we may repeat this for all variables. At the end, each variable will appear exactly twice, once from the first $S$ and once from the second. However, notice that all elements from the first $S$ always appear before all elements from the second $S,$ so both the first $n$ elements and the last $n$ elements will be permutations of the $n$ variables $a_1,a_2,\dots,a_n.$, corresponding to an element of $T.$ Now, we will show that no two elements of $T$ are equivalent. This is enough to show that any full string is equivalent to exactly one element of $T,$ since if any string is equivalent to two strings, then those two strings clearly must also be equivalent. To show this, first notice that this is trivial for $n=1,$ Now, when $n>1,$ suppose that there exist two equivalent strings $A,B$ in $T.$ First, assume that their $P_1$ permutations are distinct. Then, there must exist two variables $x,y$ such that $x$ precedes $y$ in $A$ but not $B.$ Consider the operation $\times$ defined as $x \times y = x, y \times x = y, x \times a = a \times x = x, y \times a = a \times y = y$ for any $a \notin \{x,y\},$ and $a \times b = a$ for any $a,b \notin \{x,y\}.$ An easy casework check shows that this is a simple operation, and we can see that under this operation, $A$ evaluates to $x$ but $B$ evaluates to $y,$ which is a contradiction. We can use similar reasoning to show that their $P_2$ permutations must also be the same, so the two strings $A,B$ must be identical, so no two distinct elements of $T$ are equivalent. We have shown that this set $T$ works, and we can easily count that $T$ has $(n!)^2$ elements, so we are done.

The answer is all strings that are two consecutive permutations of the $n$ characters, giving $\boxed{(n!)^2}$ total is necessary and sufficient. Its easy to see consecutive identical blocks of letters can be replaced by a single identical block. Claim 1: $abaca \equiv abca$. Moreover any string is equivalent to a string with at most $2$ of every character. Proof. Note that if $ba = b$, we are done, so assume $ba = a$. Then $abaca \equiv aca$. If $ac$ or $ca$ is $a$, $aca \equiv a$ and $abca \equiv aba \equiv a$. If they are both $c$, then $abca \equiv abc$ and $abaca \equiv abc$. Claim 2: $xayxby \equiv xaxyby$. Proof. Using claim 1, we cam write $$xayxby \equiv xaxyxyby \equiv xaxyby$$as desired. Now we consider all strings containing at most 2 of each character. If the string is not two consecutive permutations, we consider the $x$ such its second occurrence is the farthest right possible such that there exists a $y$ such that its first occurrence as as far left as possible and is after $x$. that has not been included in the string at all yet. Then if the second $x$ is not adjacent to the first appearance of $y$, there exists some $z$ between the second $x$ and the first $y$ which either has already appeared once contradicting $x$'s maximality or it has never appeared contradicting the minimality of $y$. Thus our configuration for our string now must look like $$AxBxyCyD$$for blocks of letters $A, B, C, D$. By claim 2, this is equivalent to $S' = AxByxCyD$. If we continuously repeat this process of choosing such $x$ and $y$'s, we will terminate only when we have reached two consecutive permutations as only then will such and $x$ and $y$ not exist. Thus any string is equivalent to a string that is two consecutive permutations. To finish, we show that no two consecutive permutation strings are equivalent. Say two elements in the same half of the string $x,y $ in $BxAyC$ are swapped to $ByAxC$(Repeating this describes all permutations) Then consider simple operation such that $xA = x$, $xy = x$,$yA=y$, and $yx = y$. We can then similarly make the operator work to make sure $BxC \neq ByC$. Thus no two are equivalent.

Nice problem, though it was super bashy and sunk like 4.5 hours or so into it. MOHS estimates, anyone? my first approach was as follows: ``It's easy to derive (ab=a, bc=b then ac=(ab)c=ab=a true, ab=a, bc=c ac= anything always true) in any set $\{ab,bc,ac\}$ (and similar permutations) that there are exactly two distinct values (1). Define an element a to \emph{override} another element b if ab=ba=a. The key step is the following: \begin{lemma} \textit{We can uniquely separate the elements into sets }$S_1,...,S_k$,\textit{ where elements a,b are in a set iff one does not override the other, and smaller numbered sets override larger. In fact, we characterize this for each i, }$\forall a,b\in S_i,$\textit{ ab is uniquely determined by if a is to the left of b or not; call this property left or right oriented}. \end{lemma} \begin{proof} Possibility and uniqueness of grouping: If ab=a,ba=b (these two WLOG),ac=a,ca=c, then obviously cb=(ca)b=c(ab)=c and bc=(ba)c=b(ac)=b so you can place a,b,c in the same set; the other case ab=a,ba=b,ac=c,ca=a follows by bc=c by (1), if (ac)b=cb=a=ab so ac=a contradiction, if c(ba)=cb=a=ca so ba=a contradiction, hence cb=b so you can place a,b,c in the same set." wasn't sure how to continue. here is the complete solution:

Should've just asked to find all $\times$ imo. Say that $x$ dominates $y$ or $x \succ y$ if $x \times y = y \times x$. Else, say that $x, y$ are first positional with respect to each other if $i \times j = i$ for $i, j \in \{x, y\}$ and second positional elsewise. Claim: If $x$ dominates $y$ and $y$ dominates $z$ then $x$ dominates $z$. Proof: Note that $xz = xyz = xy = x$ and similar by symmetry $\blacksquare$. Claim: It is impossible that $x, y$ are first positional and $x, z$ are second positional. Proof: Note that $zyx = zy$ and $xzy = zy$ so $zy$ dominates $x$, contradiction. $\blacksquare$. Claim: If $x, y$ are first (or second) positional and $x, z$ are first (or second) positional then the same holds for $x$ and $z$. Proof: Note that $xz = xyz = xy = x$, and the result follows by symmetry. $\blacksquare$. Now consider the graph $G = K_n$ on letters, and color edges between first positional letters red and second positional letters green. Then the red edges and green edges form disjoint cliques. If $A, B$ are cliques and some element $a \in A$ dominates $b \in B$, then by considering $a, a_1, b$ we get that $a_1$ must dominate $b$ as well, so there exists a total ordering on the cliques for domination. As such, if $\sum$ is our alphabet, all $\times$ can be classified as taking a partition $\sum = S_1 \sqcup S_2 \dots \sqcup S_k$ such that for two elements in different $S_i$, the smaller $i$ dominates, and for those in the same $S_i$, a fixed choice of first positional and second positional wins. Let $s_1, s_2$ be two full strings and let $f_1, f_2$ be the results when removing the non first occurences of each letter. If $f_1 \ne f_2$ then there exists some $a \dots b$ in $f_1$ and $b \dots a$ in $f_2$, so taking $S_1 = \{a, b\}, S_2 = \sum \setminus \{a, b\}$ and first positional on $S_1$ means $s_1$ and $s_2$ aren't equivalent. Defining $l_1, l_2$ for the last occurences, we get that $s_1$ and $s_2$ aren't equivalent if $f_1 \ne f_2$ or $l_1 \ne l_2$. However, if $f_1 = f_2$ and $l_1 = l_2$, then regardless of the positional ordering on $S_1$, the first/last element in $s_1$ and $s_2$ is the same, so the two letters are equivalent. As such, there are $(n!)^2$ tuples depending on $f_i, l_i$.

I will first prove that any such binary operation $\times$ has the property that we can break the $n$ variables into $k$ sets $A_1$, $A_2$, \dots, $A_k$, such that for any $i\in A_r$ and $j\in A_v$ such that $r>v$ $i\times j= i$ and $j\times i$. As well as that for any elements $i, j\in A_r$ that $i\times j =i$ and $j\times i = j$ for all $i, j$ or that $i\times j=j$ and $j\times i=i$ for all $i, j$. To see this is true first I will prove that if $i, j, k$ are $3$ of the $n$ variables, and $j\times k=j$ and $k\times j=j$ that if $i$ wins against $j$ for any ordering that $i\times k=i$ and $k\times i= i$. To do this WLOG $i\times j=i$ and consider the strings $ikj$ and $kij$ clearly $i$ wins the first string in one case so $i\times k=i$, in the second string if $i$ wins the result is clear however if $i$ does not win we can get both $j$ and $k$ to win which is a contradiciton. Now I will show the second condition. Suppose for three variables $i, j, k$ that $i\times j=i$ and $j\times i=j$ and that $k\times i=i$ and $i\times k=k$ and that $k\times j=k$ and $j\times k=j$. We can use the string $ijk$ which can equal both $i$ and $k$ which is a contradiciton. Now suppose that for three variables $i, j, k$ that $i\times j=i$ and $j\times i=j$ and that $k\times i=i$ and $i\times k=k$ and that $k\times j=j$ and $j\times k=k$. We use the string $ikj$ which can equal both $i$ and $j$ which is a contradiction. Thus our characterization is correct. Now consider concantating two permutations of the $n$ variables. Clearly as we can find a direction for any of these two such that two of the terms the same distance away from the end are different we can but both those terms in the set $A_1$ and put no other terms and we get they are not equivalent. Now for any other full sequence note that if we take the first $n$ distinct terms from either side we get something equivalent to one of the sequences. Terrible question not worth doing at all, way too shallow