This problem was proposed by Alex Zhai (USA). The original proposal also asks to prove the converse: if $A^{*|B|} = B^{*|A|}$ then $A * B = B * A$.

Claim 1: $f_{X*Y}=f_X\circ f_Y$. Proof: Since both functions are strictly increasing, it is enough to prove that they have equal images, or formally $f_{X*Y}(\mathbb N)=f_X(f_Y(\mathbb N))$. It is true since: $$f_{X*Y}(\mathbb N)=\mathbb N\setminus (X*Y)=\mathbb N\setminus (X\cup f_X(Y))=(\mathbb N\setminus X)\setminus f_X(Y)=f_X(\mathbb N)\setminus f_X(Y)=f_X(\mathbb N\setminus Y)=f_X(f_Y(\mathbb N))$$ Claim 2: The operation $*$ is associative, i.e. for each three finite sets $X,Y,Z$ we have $X*(Y*Z)=(X*Y)*Z$. Proof: Note that $$f_{X*(Y*Z)}=f_X\circ f_{Y*Z}=f_X\circ (f_Y\circ f_Z)$$ $$f_{(X*Y)*Z}=f_{X*Y}\circ f_Z=(f_X\circ f_Y)\circ f_Z$$ Since composition is associative, we have $f_{X*(Y*Z)}=f_{(X*Y)*Z}$. Now $$X*(Y*Z)=\mathbb N\setminus f_{X*(Y*Z)}(\mathbb N)=\mathbb N\setminus f_{(X*Y)*Z}(\mathbb N)=(X*Y)*Z$$ as desired. Now we can write $$A^{*b}=\underbrace{A*(A*\cdots (A*(A*A))\cdots )}_{\text{ A appears $b$ times}}$$ Hence the condition rewrites as $A^{*b}=B^{*a}$. Note that $A^{*b},B^{*a}$ have they same cardinality and communte by associativity. Hence it suffices to prove a more general claim: Claim 3: Let $X,Y$ be finite sets such that $X*Y=Y*X$ and $|X|=|Y|$. Then $X=Y$. Proof: Let $n=|X|=|Y|$. We'll prove the claim by induction on $n$. The base case is when $X,Y$ are empty. Now suppose $X,Y$ are nonempty. We'll first prove that $X,Y$ have the same maximal element. Let $p=\max X$ and $q=\max Y$. Assume for contradiction and WLOG that $p<q$. Then $q+n=\max(X*Y)=\max(Y*X)\leq\max\{q,p+n\}<q+n$, contradiction. Now write $p=\max X=\max Y$. Let $X'=X\setminus\{p\}$ and $Y'=Y\setminus\{p\}$. We'll prove that $X',Y'$ commute, and we'll be done by induction hypothesis. Note that for each positive integer $m$, $$f_{X'}(m)=\begin{cases}f_X(m)\qquad\text{ if }f_X(m)<p\\f_X(m)-1\qquad\text{ if }f_X(m)>p\end{cases}$$ and similarly for $f_Y(m)$. Let $s=\max(X*Y)=\max(Y*X)$. Also write $-1+T=\{-1+t|s\in T\}$. Then: $$X'*Y'=((X*Y)\cap[1,p-1])\cup(-1+((X*Y)\cap[p+1,s-1]))$$ Similar result for $Y'*X'$. This clearly shows that $X'*Y'=Y'*X'$.

Hey this is not a combo problem Let $\mathbb{N} = \mathbb{Z}^+$. Note that $\mathbb{N} \setminus A = f_A(\mathbb{N})$. Furthermore, $f_A, f_B$ are strictly increasing functions from $\mathbb{N} \rightarrow \mathbb{N}$ that are eventually of the form $x \mapsto x+c$ for sufficiently large $x$. More precisely, there is a constant $C$ such that $f_A(x) = x+a$ and $f_B(x) = x+b$ for all $x > C$. Note that $f_A$ and $f_B$ are injective. Claim 1. $\mathbb{N} \setminus (A*B) = f_A(f_B(\mathbb{N}))$. Proof. Just write $$\mathbb{N} \setminus (A*B) = \mathbb{N} \setminus (A \cup f_A(B)) = f_A(\mathbb{N}) \setminus f_A(B) = f_A(f_B(\mathbb{N})).$$ $\blacksquare$ We are given that $$f_A(f_B(\mathbb{N})) = f_B(f_A(\mathbb{N}))$$ and we wish to show that $$f_A^b(\mathbb{N}) = f_B^a(\mathbb{N}).$$ For convenience let $f = f_A$ and $g = f_B$. Lemma 1. $f(g(x)) = g(f(x))$ for all $x$; i.e. $f$ and $g$ commute. Proof. We are given that $f(g(\mathbb{N})) = g(f(\mathbb{N}))$. Thus for each $x$, there exists $y$ which depends on $x$ satisfying $$f(g(x)) = g(f(y)).$$ For each $x$, there is exactly one corresponding $y$ (since $g \circ f$ is injective). Furthermore, each $y$ corresponds to some $x$. Define a function $h$ such that $y = h(x)$, so $$f(g(x)) = g(f(h(x))).$$ Clearly $h$ is injective. We also already know that $h$ is surjective. Thus $h$ is bijective. Note that $f(g(x))$ is strictly increasing in $x$, which means that $g(f(h(x)))$ is strictly increasing in $x$. Thus $h(x)$ is strictly increasing in $x$. It follows that $h$ is the identity function; i.e. $f(g(x)) = g(f(x))$. $\blacksquare$ Lemma 2. Suppose there is $x_0$ such that $f(x_0) = x_0$. Then $g(x_0) = x_0$. Proof. Suppose for the sake of contradiction that $g(x_0) > x_0$. We have the infinite chain $$x_0 < g(x_0) < g^2(x_0) < \cdots$$ By Lemma 1, $f(g^i(x_0)) = g^i(f(x_0)) = g^i(x_0)$. Thus $f$ has $x_0,g(x_0),g^2(x_0),\cdots$ as fixed points. Since $f$ has infinitely many fixed points, it follows that $a=0$, contradiction. $\blacksquare$ Corollary. The roles of $f$ and $g$ can be switched in the preceding Lemma, so in fact $f(x_0) = x_0$ if and only if $g(x_0) = x_0$. We can define a threshold $N$ such that $f(x) = x$ if and only if $x \le N$. Thus $g(x) = x$ if and only if $x \le N$. Lemma 3 (key Lemma). $f^b(x) = g^a(x)$ for all $x$ Proof. If $x \le N$ then this is obvious, so assume $x > N$. Note that $$x<g(x)<g^2(x)<\cdots$$ Thus we can find $i$ such that $g^i(x) > C$, and we compute $$f^b(g^i(x)) = g^i(x) + ab = g^a(g^i(x)).$$ From here we can take out $i$ copies of $g$ from both sides of the equation due to the fact that $g$ is injective. We are left with $$f^b(x) = g^a(x),$$ as desired. $\blacksquare$

The problem reduces to the following claims: 1. $*$ is associative 2. If $XY=YX$ and $|X|=|Y|$, then $X=Y$. Indeed, if claims 1 and 2 are true then $AB=BA$ implies $A^bB^a=B^aA^b$, and since $|A^b|=|B^a|=ab$, we get $A^b=B^a$. Define $S_X(Y)=\{f_X(y): y\in Y\}$. Note that $S_X(Y)$ and $X$ are always disjoint. Additionally, $S_X(Y\cup Z)=S_X(Y)\cup S_X(Z)$. Using this, we get $(X*Y)*Z=X\cup S_X(Y)\cup S_{X*Y}(Z)$ and $X*(Y*Z)=X\cup S_X(Y)\cup S_X(S_Y(Z))$. Thus, it remains to prove $S_{X*Y}(Z)=S_X(S_Y(Z))$. We prove the stronger claim that $f_{X*Y}(n)=f_X(f_Y(n))$ for any integer $n$. Since $f_T$ is strictly increasing for any set $T$, it remains to show that the range of $f_{X*Y}$ and the range of $f_X\circ f_Y$ are identical. Obviously, the range of $f_{X*Y}$ is every positive integer not in $X*Y$; i.e., any integer not in $X$ or $S_X(Y)$. Now, suppose $m$ is in the range of $f_X\circ f_Y$. Then $m$ cannot be in $X$, since $m$ is in the range of $f_X$. Moreover, $f_X^{-1}(m)$ cannot be in $Y$, since it is in the range of $f_Y$. This implies that $m$ cannot be in $S_X(Y)$. For all $m$ not in $X$ or $S_X(Y)$, we can check that $f^{-1}_Y(f^{-1}_X(m))$ is defined, and thus the range of $f_X\circ f_Y$ is every positive integer not in $X$ or $S_X(Y)$, i.e. the same range as $f_{X*Y}$. This proves associativity of $*$. Now we prove the second claim via induction. Because $*$ is associative, we simply denote $X*Y$ as $XY$. Obviously, the claim is true for $|X|=|Y|=1$. Now, suppose it is valid for $|X|=|Y|=s$. Let $\max(X)$ denote the maximum value in a set $X$. For the sake of contradiction, suppose $\max(X) < \max(Y)$. Then $\max(S_X(Y))=f_X(\max(Y))=\max(Y)+s$ since $\max(Y) > \max(X)$. On the other hand, $\max(S_Y(X))=f_Y(\max(X))\le \max(X)+s<\max(Y)+s$; note that it could not be greater than $\max(X)+s$ by definition. Thus, $\max(XY)=\max(\max(X), \max(S_X(Y))=\max(Y)+s$ and $\max(YX)=\max(\max(Y), \max(S_Y(X))<\max(Y)+s$, contradicting $XY=YX$! Thus, $\max(X)=\max(Y)$. Now, denote $M=\max(X)=\max(Y)$ and $X’=X-\{M\}$, and $Y’$ similarly. We claim that $XY=YX$ implies $X’Y’=Y’X’$, and then induction proves claim 2 since $|X’|=|Y’|=s-1$. Note that $f_{X’}(n)=f_X(n)$ if $f_X(n) <M$ and $f_{X’}(n)=f_X(n)-1$ if $f_X(n)\ge M$. Thus, $S_{X’}(Y’)$ is just the set $S_X(Y’)$ with all elements greater than or equal to $M$ decreased by one. Moreover, $S_X(Y)=S_X(Y’)\cup \{f_X(M)\}=S_X(Y’)\cup \{M+s\}$. Therefore, $S_{X’}(Y’)$ is equivalent to $S_X(Y)$ with the element $M+s$ removed and all elements at least $M$ decreased by one. Now, since all elements of $X’$ are less than $M$, it follows that to get from $XY=X\cup S_X(Y)$ to $X’Y’=X’\cup S_{X’}(Y’)$ one applies the following procedure: 1. Remove the elements $M$ and $M+s$. 2. Decrease all the remaining elements $\ge M$ by one. But by symmetry the same procedure is done to get from $YX$ to $Y’X’$. Since $XY=YX$, it follows $X’Y’=Y’X’$ and thus by induction, $X’=Y’\rightarrow X=Y$, proving claim 2. Thus, from the above two claims, we get $A^b=B^a$ as desired. $\square$

1. $*$ is associative. We want to prove $X*(Y*Z)=(X*Y)*Z$ First, just remove all of the members of $X$. Then, both sides of the upper equation are just $Y*Z$. The difference is just when we add back the elements of $X$. However, it's clear that at what step we add back the elements of $X$ does not affect any other elements, so both sides are the same. $\blacksquare$ 2. $X*Y=Y*X$ and $|X|=|Y|$ implies $X=Y$ Let $|X|=|Y|=k$, and let the maximum elements of $X$ and $Y$ be $x_1$ and $y_1$, respectively. Assume for sake of contradiction that $x_1\neq y_1$, so wlog, $x_1>y_1$ Then, the maximum element of $Y*X$ must be either $y_1$ or $x_1+k$. The former is if the maximum is from the original set, the latter is if the maximum is one of the added numbers. Clearly, the maximum cannot be $y_1$, since $y_1<x_1\in X*Y=Y*X$. Thus, we have the maximum element of $Y*X$ is $x_1+k$. Then, the maximum element of $X*Y$ must be $x_1$ or $y_1+k$ by the same logic. But since $k$ is nonzero and $y_1<x_1$, we have that both possibilities are less than $x_1+k$ We have a contradiction, so $x_1=y_1$. Let $x_1=y_1=z$ Now, we remove $z$ from $X$ to get $X_1$ and likewise for $Y$ to get $Y_1$. So let's consider what happens to $X*Y$ when we make this removal. So when we go from $X*Y$ to $X*Y_1$ we just remove the $z$th element in $X*Y$ not in $X$. Since the maximum element in $X$ is $z$, the $z$th element must be greater than $z$, so it has to be $z+k$. Now, to go from $X*Y_1$ to $X_1*Y_1$, we just remove $z$ from $x$ and shift everything above down by $1$. Note that going from $Y*X$ to $Y_1*X_1$ uses the exact same steps, so $X*Y=Y*X$ implies $X_1*Y*1=Y_1*X_1$ Thus, we can remove the maximum from both sets to get two equivalent sets. But then we can just repeat this process of proving the two maximum numbers of both sets are equal and removing them, to eventually get that both sets are equivalent. $\blacksquare$ Now, we clearly have that $A^bB^a=B^aA^B$ by associativity, so (2) gives $A^b=B^a$ $\square$

CantonMathGuy wrote: This problem was proposed by Alex Zhai (USA). The original proposal also asks to prove the converse: if $A^{*|B|} = B^{*|A|}$ then $A * B = B * A$. The converse, anyone? (Sorry if it's a dumb question, but I don't find it trivial)

Lemma 1: If $X*Y=Y*X$ and $|X|=|Y|$, then $X=Y$. Proof: We will use induction. The base case is trivial, so suppose we have $|X|=|Y|=n$, and $X*Y=Y*X$. Consider the largest number in each set, and call them $M_x$ and $M_y$. If $M_x\neq M_y$ (WLOG $M_x > M_y$), then consider $f_Y(M_x)$. Clearly, $f_Y(M_x)>M_x>M_y$, and it is the largest number in $X*Y$. On the other hand, if $f_X(M_y)<M_x$, then the largest number in $Y*X$ is $M_x$, which is a contradiction. So, we must have $f_X(M_y)>M_x$. However, it is obvious that $f_X(M_y)=M_y+n$, $f_Y(M_x)=M_x+n$, and they are both the largest numbers in $Y*X$, $X*Y$ respectively, so we must have $M_x=M_y$, which is a contradiction. Therefore, we always have that $M_x=M_y$, and it is not hard to see we can just remove both numbers from $X$, $Y$ respectively but keep $X*Y=Y*X$. We are now done by inductive hypothesis. Lemma 2: The operation $*$ is associative. Proof: We need to show that $A*(B*C)=(A*B)*C$. Considering the RHS, $A*B=A\cup\{f_A(b) : b\in B\}$, and when we star this with $C$, we will add on $f_{A*B}(c)$ for all $c\in C$. However, it is not hard to see that $f_{A*B}(c)=f_A(f_B(c))$, so $$(A*B)*C=A\cup\{f_A(b) : b\in B\}\cup\{f_A(f_B(c)) : c\in C\}=A\cup\{f_{A}(k) : k\in B*C\}=A*(B*C)$$ Looking at the question, we know that for any combination of $A$s and $B$s, we can star them in any way we like, as the operation is both associative and commutative. In particular, $$\underbrace{A*(A*\cdots (A*A)\cdots )}_{\text{ A appears $b$ times}}*\underbrace{B*(B*\cdots (B*B)\cdots )}_{\text{ B appears $a$ times}}=\underbrace{B*(B*\cdots (B*B)\cdots )}_{\text{ B appears $a$ times}}*\underbrace{A*(A*\cdots (A*A)\cdots )}_{\text{ A appears $b$ times}}.$$ As each big term has $ab$ elements, we have, by Lemma 1, $\underbrace{A*(A*\cdots (A*(A*A))\cdots )}_{\text{ A appears b times}}=\underbrace{B*(B*\cdots (B*(B*B))\cdots )}_{\text{ B appears a times}}$ as desired.

Lemma 1. Let $A,B\in \mathbb{N}$, then for all integers $n$, $$f_A(f_B(n)) = f_{A*B}(n)$$ Proof: Let $M=\{f_A(f_B(n)): n\ge 1\}$ and $N=\{f_{A*B}(n): n\ge 1$. It suffices to show $M=N$. Observe the range of $f_A(x)$ is simply $\mathbb{N}\backslash A$, so $N=\mathbb{N}\backslash (A*B)$ and $M=\mathbb{N}\backslash A \cup \{f_A(b): b\in B\}=\mathbb{N}\backslash A*B$, as desired. Lemma 2: $A*(B*C)=(A*B)*C$ Proof. Note $\{ f_A(f_{B*C}(n)): n\ge 1\} = \{f_A(f_B(f_C(n))): n\ge 1\} = \{f_{A*B}(f_C(n)): n\ge 1\}$, where the equalities hold by lemma 1. Now, we present two solutions similar in flavor, both involving convolutions of the same function. Solution 1: I claim the $A,B$ have the same smallest number. Proof: Let $b_1$ be the smallest number in $B$. Then $f_B(f_A(b_1-1))=f_A(b_1-1)$, which implies $f_A(b_1-1)=b_1-1$, which means the smallest number in $A$ is at least $b_1$. Repeating the same argument gives that their smallest elements are the same. Now, let $x_0$ be their smallest element. We wish to show $f_A^{|B|} (n) = f_B^{|A|}(n)$. If $n<x_0$ we're trivially done. If $n\ge x_0$, $f(n)-n\ge 1$, so we apply enough $f$'s such that $f^e(n) > \max\limits_{a\in A} a - |A|, \max\limits_{b\in B} b - |B|$. Then, $f^A{|B|}(f^e(n))=f^e(n)+ab=f_B^{|A|}(f^e(n))$. Since $f$ is injective, we are done. Solution 2: Let $B^a=B*(B^{a-1})$. By Lemma 2 and $A*B=B*A$, $B^a * A^b = A^b * B^a$ Let $X=B^a, Y=A^b$. Let $f_X(n)=n+f(n), f_Y(n)=n+g(n)$, so the functional equation writes as $$g(n)+f(n+g(n))=f(n)+g(n+f(n))$$ Notice $g$ is a non-decreasing continuous function. Furthermore, since $|X|=|Y|=ab$, we can see for all sufficiently large $n$, $f(n)=g(n)=n+ab$. Assume for contradiction $g(n)>f(n)$ for some $n'$. This implies $g(n'+g(n'))>g(n'+f(n'))>f(n'+g(n'))$. Let $h(n)=n+g(n)=f_Y(n)$. Since $g(n)\ge 1 \forall n>n'$, there exist $m$ such that $h^m(n)>\max\limits_{x\in X} x - |X|$ and $g(h^m(n)) > f(h^m(n))$, contradiction.

First, we make the following observation. The $k$-th smallest number not in $X * Y$ is essentially picking the $k$-th smallest number that is not in $Y$, from the numbers apart from $X$ ($\mathbb{N} \setminus X$), so we have $f_{X * Y}(k) = f_X(f_Y(k))$. From now on, let $f(n) = f_A(n)$ and $g(n) = f_B(n)$. The problem gives that $$f(g(n)) = f_A(f_B(n)) = f_{A * B}(n) = f_{B*A}(n) = f_{B}(f_{A}(n)) = g(f(n))$$ Note that $X = Y \iff f_X = f_Y$, so it suffices to show that $f_{A*(A* \cdots * (A*A))} = f_{B*(B* \cdots * (B*B))}$ which by the previous paragraph is equivalent to $f^b(n) = g^a(n)$. Also clearly both $f,g$ are strictly increasing. We also have that eventually (when $n$ goes beyond the maximum element in $A$ and $B$), $f,g$ just increase by $a,b$ respectively, so we have essentially reduced the problem to the following. Equivalent problem wrote: Call a function $f:\mathbb{N}\rightarrow \mathbb{N}$ as $k$ -good if it is strictly increasing, and $f(x) = x+k$ for sufficiently large $x$. Suppose $f,g$ are $a$ good and $b$ good respectively, and $f(g(n)) = g(f(n))$. Prove that $$f^b(n) = g^a(n)$$ Suppose not, and say $f^b(n) > g^a(n)$ for some maximal $n$, which clearly exist since once $f,g$ just start increasing by $a,b$ this clearly holds because both sides just become $n + ab$. But then we have $f^b(f^b(n)) > f^b(g^a(n)) \implies f^b(f^b(n)) > g^a(f^b(n))$. Since $n$ was maximal, we must have $f^b(n) \le n$. But obviously $f(n) \ge n$, so we have $f^b(n) = n$ and since its strictly increasing, $f(n) = n$. But we have $n \le g(n) \le g^a(n) < f^b(n) = n$, a contradiction. Therefore, we indeed have $f^b(n) = g^a(n)$ for all $n$, as desired. $\blacksquare$

$(A * B) * C = A * (B * C)$, so the operation is associative. Therefore by commutativity, $X = A^b$ and $Y = B^a$ commute, and clearly have the same size. Furthermore, notice that by casework, if two sets commute then they have the same number of missing elements less than their maximal element. Notice that removing the largest element when both sets have the same amounts of elements does not affect commutativity. Hence, it cannot be the case that upon removing the last element, one set has a smaller largest element than the other, since the number of missing elements and number of included elements is the same between the sets. Hence by induction by continually removing their maximal element, $X = Y$.

My friend recommend it to me and it's really nice though I can't solve it. Maybe it is more like an algebra than a combo.

we all love $k$th order statistic mexes

Is it true that 2017 A shortlist had 9 problems?

Very nive problem, solved in 1.5 days! I think there is group theory background though I know nothing about it. First we prove $(A*B)*C=A*(B*C)$ for all finite positive integer sets $A,B,C.$ We only need to prove $f_{A*B}=f_A\circ f_B.$ Because all of them are increasing function, we only need $\Im f_{A*B}=\Im (f_A\circ f_B).$ This is because $$\Im f_{A*B}=\mathbb N_+\setminus (A*B)=\mathbb N_+\setminus (A\cup f_A(B))=f_A(\mathbb N_+\setminus B)=f_A(\Im f_B)=\Im (f_A\circ f_B).\Box$$ Define $S^{*(n)}:=\underbrace{S*(S*\cdots (S*(S*S))\cdots )}_{\text{ S appears n times}}.$ Now by $A*B=B*A$ we get $$\begin{align*}A^{*(b)}*B^{*(a)}=A^{*(b-1)}*B*A*B^{*(a-1)}=\cdots =A^{*(b-1)}*B^{*(a)}*A=\cdots B^{*(a)}*A^{*(b)}.\end{align*}$$ So we only need $|X|=|Y|,X*Y=Y*X\Longrightarrow X=Y$ to prove $A^{*(b)}*B^{*(a)}.$ We use induction on $|X|=:n.$ $n=1$ is obvious. Now assume it is right for $n-1,$ consider ${}{}n.$ Let $\max X:=x_n,\max Y:=y_n.$ If $x_n\neq y_n,$ WLOG $x_n<y_n.$ Then $f_X(y_n)=y_n+n,$ so $\max X*Y=y_n+n.$ However $\max Y*X=\max\{y_n,f_Y(x_n)\}<y_n+n,$ contradiction! Therefore $x_n=y_n.$ Now $$(X\setminus\{x_n\})*(Y\setminus\{y_n\})=X*(Y\setminus\{y_n\})\setminus\{x_n\}=X*Y\setminus\{x_n+n,x_n\}=(Y\setminus\{y_n\})*(X\setminus\{x_n\}).$$ So use induction hypothesis on $X\setminus\{x_n\},Y\setminus\{y_n\}$ and we are done$.\Box$

Very cutesy very demure problem This is trivially true if either $A$ or $B$ is empty so assume not. Claim: We have that $(A \ast B) \ast C = A \ast (B \ast C)$. Proof. $A$ and $\{f_A(b) \in b \in B\}$ can be to seen be in both. We claim that $f_{A \ast B} (c) = f_A(f_B(c))$ for $c \in C$. Let $\overline{T} = {\mathbb N} \setminus {T}$ for set $T$. Note that $f_A$ is invertible from its codomain. Let $z = f_{A}^{-1}(f_{A \ast B}(c))$ which exists since $\overline{A \ast B} \subset \overline{A}$. Then $$f_{A \ast B} (c) > f_A(b) \iff z > b$$ The number of elements $s \ne f_A(b)$ of $\overline{A \ast B}$ less than $f_{A \ast B}(c)$ is then same as the number of elements $f_A^{-1}(s) \ne b$ of ${\mathbb N} \setminus B$ less than $z$. However, these are both just $c$, so $z = f_B(c)$ as desired. $\blacksquare$ We now define $A^k$ as taking $A \ast A \ast A \dots A$ where there are $k$ $A$s. Let $A = \{a_1, a_2, \dots, a_m\}$ and $B = \{b_1, b_2, \dots, b_n\}$ where $A$ and $B$ are sorted so $a_m, b_n$ are maximal. Claim: The difference $a_m - b_n$ between the largest element of $A$ and $B$ is equal to $|A| - |B|$. Proof. The largest element of $A \ast B$ and $B \ast A$ are equal so $$\max(f_A(b_n), a_m) = \max(f_B(a_m), b_n)$$ Note that if $a_m = f_B(a_m)$ this implies $a_m < b_n$, so this becomes $f_A(b_n) = b_n$ which can't be true. Since $f_A(b_n) > b_n$ and $f_B(a_m) > a_m$ this means that $f_A(b_n) = f_B(a_m)$. Now WLOG suppose that $a_m \ge b_n$. Then this becomes $f_A(b_n) = a_m + |B|$. Since $f_A(b_n) > a_m$, it follows that $b_n + |A| = a_m + |B|$ $\blacksquare$ Now, the largest element of $A^{|B|}$ is $f_A^{|B| - 1} (a_m) = a_m + |A| \cdot (|B| - 1)$ and the largest element of $B^{|A|}$ is similarly $b_n + |B| \cdot (|A| - 1)$ which are equal by the above lemma. Furthermore, by associativity and commutativity, we have that $$A^{|B|} \ast B^{|A|} = B^{|A|} \ast A^{|B|}$$ We now claim the following which finishes. Claim: Let $A, B$ be finite subsets of ${\mathbb N}$ such that $A \ast B = B \ast A$. If $A$ and $B$ have the same largest element, then $A = B$. Proof. Adopt the same notation for $A, B$ as above. Then since $a_m = b_n = c$ this implies that $|A| = |B|$ and $m = n$. Define $A', B'$ as $A, B$ with $c$ removed. Then $$A' \ast B' = f_{\{c\}}^{-1}(A \ast B \setminus \{c, 2c\})$$ because if $f_A(x) > c$, then $f_{A'}(x) = f_A(x) - 1$ and else $f_A(x) = f_{A'}(x)$. This implies that $A' \ast B' = B' \ast A'$. Since $|A'| = |B'|$ this implies that $a_{n-1} = b_{n-1}$ holds and we finish inductively. $\blacksquare$

First trivially notice that any such $f_X$ is strictly increasing and also that for all $x \ge M$ it is true that $f_A(x)=x+a$ and $f_B(x)=x+b$ (because both $A,B$ are finite), now we make some simple observations. Claim: $f_{X*Y}(x)=f_X(f_Y(x))$ Proof: Due to strictly increasingness it's enough to prove they have the same image, so for any finite set $X$ just note that $f_X(\mathbb Z_{>0})=\mathbb Z_{>0} \setminus X$ which means that: $$f_{X*Y}(\mathbb Z_{>0})=\mathbb Z_{>0} \setminus (X*Y)=\mathbb Z_{>0} \setminus (X \cup f_X(Y))=(\mathbb Z_{>0} \setminus X) \setminus f_X(Y)=f_X(\mathbb Z_{>0}) \setminus f_X(Y)=f_X(\mathbb Z_{>0} \setminus Y)=f_X(f_Y(\mathbb Z_{>0}))$$ Which proves that they have the same imagine and thus are in fact the same function. Trivially also from image note that if $f_X=f_Y$ then $X=Y$, so now using Claim 1 and problem condition we are given $f_A(f_B(x))=f_{A*B}(x)=f_{B*A}(x)=f_B(f_A(x))$ and now to save us work just call $f_A=f_1$ and $f_B=f_2$. Notice that all we need to prove now from everything seen above is that $f_1^b(x)=f_2^a(x)$, this is trivially true for all $x \ge M$ so now assume it was false for some maximal $n<M$. First remember that we obtained $f_1(f_2(x))=f_2(f_1(x))$ which now by messing with iterations gives that for any $u,v \in \mathbb Z_{>0}$ we have that $f_1^u(f_2^v(x))=f_2^v(f_1^u(x))$, and thus if WLOG (since other case is symetrical) we had that $f_1^b(n)>f_2^a(n)$ for this said $n$, then notice that stack of strictly increasing functions is still strictly increasing meaning that $f_1^b(f_1^b(n))>f_1^b(f_2^a(n))=f_2^a(f_1^b(n))$ and from the maximaility we obtain that $n \ge f_1^b(n)$ and since $f_1^b$ is strictly increasing this means $f_1^b(x)=x$ for all $x \le n$ but then we have $n>f_2^a(n)$ and this can't happen due to strictly increasingness thus no such $n$ exists and our desired conclusion is true. Therefore $f_1^b(x)=f_2^a(x)$ holds everywhere thus we are done

Claim. The operation $*$ is associative. Proof. Consider the "gaps" in $A$. Essentially $(A*B)*C$ is filling in these gaps with $B$ then $C$, and $A*(B*C)$ is filling in these gaps with $B*C$. But if we think of these gaps not as gaps but all of the positive integers again, then filling them with $B$ makes it exactly $B$, so filling with $B$ then $C$ is just filling it with $B*C$. Now it is not hard to see that the LHS and RHS of the big equation we want to prove commute. In fact, we claim that if $A*B=B*A$ and $|A|=|B|$ (obviously these are satisfied in the desired equation), then $A=B$. (So here, $A$ is actually $A*(A*\dots)$ and similarly for $B$). Define the $n$-gaps of a set $S$ of positive integers, $S_n'$, to be the set of positive integers not included in $S$ that are less than or equal to $n$. Then define the gaps of $S$ to be $S'=S_{\max(S)}'$. For example, the gaps of $\{1,3,5\}$ is the set $\{2,4\}$. Also, define $g_X(k)$ to be the $k$-th smallest positive integer in $X$. Note that $$\max(A*B)=\max(\max(A),|A|+\max(B)).$$ Therefore, $$M=\max(\max(A),|A|+\max(B))=\max(\max(B),|B|+\max(A)).$$ Since $M\ge |B|+\max(A)>\max(A)$, we have $M=|A|+\max(B)$. Similarly, $M=|B|+\max(A)$. Thus $$\max(A)-|A|=\max(B)-|B|\Longrightarrow |A'|=|B'|$$ $$M>\max(A),\max(B).$$ Now the idea is that the gaps of $A*B$ is just $\{g_{A_M'}(x):x\in B'\}$, because if $x\in B'$ then $g_{A_M'}(x)$ will not be covered by the $A$ or the $B$. So indeed, the equation we are actually interested in is $$\{g_{A_M'}(x):x\in B'\}=\{g_{B_M'}(x):x\in A'\}.$$ If we sort in increasing order $A_M'=\{a_1,a_2,\dots,a_n=\max(A'),a_{n+1},\dots\}$ and $B_M'=\{b_1,b_2,\dots,b_n=\max(B'),b_{n+1},\dots\}$ then $$g_{A_M'}(b_i)=g_{B_M'}(a_i)\Longleftrightarrow a_{b_i}=b_{a_i}.$$ Note that $\max(A)=|A|+|A'|=|B|+|B'|=\max(B)$, so $a_{n+1}=b_{n+1}$, $a_{n+2}=b_{n+2}$, etc. Now consider FTSOC the maximum positive integer $k\le n$ such that $a_k\ne b_k$. Then one of these can't be $k$, assume WLOG $a_k>k$. Then $a_{b_k}=b_{a_k}=a_{a_k}$, so $a_k=b_k$, contradiction. So $A'=B'$. Since $|A|=|B|$, that means $A=B$. $\blacksquare$