International Mathematical Olympiad

For any function $g:{\mathbb{Z}}_{>0}\to {\mathbb{Z}}_{>0}$ and any subset $X\subset {\mathbb{Z}}_{>0}$, we define $g(X)=\{g(x):x\in X\}$. We have that the image of $f_X$ is $f_X({\mathbb{Z}}_{>0})={\mathbb{Z}}_{>0}\setminus X$. We now show a general lemma about the operation $\ast$, with the goal of showing that $\ast$ is associative.

Lemma 1. Let $X$ and $Y$ be finite sets of positive integers. The functions $f_{X\ast Y}$ and $f_X\circ f_Y$ are equal.

Proof. We have $$f_{X\ast Y}({\mathbb{Z}}_{>0})={\mathbb{Z}}_{>0}\setminus (X\ast 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}))$$ Thus, the functions $f_{X\ast Y}$ and $f_X\circ f_Y$ are strictly increasing functions with the same range. Because a strictly increasing function is uniquely defined by its range, we have $f_{X\ast Y}=f_X\circ f_Y$.

Lemma 1 implies that $\ast$ is associative, in the sense that $(A\ast B)\ast C=A\ast (B\ast C)$ for any finite sets $A,B$, and $C$ of positive integers. We prove the associativity by noting $$\begin{array}{c}{\mathbb{Z}}_{>0}\setminus ((A\ast B)\ast C)=f_{(A\ast B)\ast C}({\mathbb{Z}}_{>0})=f_{A\ast B}(f_C({\mathbb{Z}}_{>0}))=f_A(f_B(f_C({\mathbb{Z}}_{>0})))\\ =f_A(f_{B\ast C}({\mathbb{Z}}_{>0}))=f_{A\ast (B\ast C)}({\mathbb{Z}}_{>0})={\mathbb{Z}}_{>0}\setminus (A\ast (B\ast C))\end{array}$$ In light of the associativity of $\ast$, we may drop the parentheses when we write expressions like $A\ast (B\ast C)$. We also introduce the notation $$X^{\ast k}=\underset{X\text{ appears }k\text{ times }}{\underbrace{X\ast (X\ast \cdots \ast (X\ast (X\ast X))\dots )}}$$ Our goal is then to show that $A\ast B=B\ast A$ implies $A^{\ast b}=B^{\ast a}$. We will do so via the following general lemma.

Lemma 2. Suppose that $X$ and $Y$ are finite sets of positive integers satisfying $X\ast Y=Y\ast X$ and $|X|=|Y|$. Then, we must have $X=Y$.

Proof. Assume that $X$ and $Y$ are not equal. Let $s$ be the largest number in exactly one of $X$ and $Y$. Without loss of generality, say that $s\in X\setminus Y$. The number $f_X(s)$ counts the $s^{th}$ number not in $X$, which implies that $$\begin{array}{c}{f}_X(s)=s+|X\cap \{1,2,\dots ,f_X(s)\}|\end{array}\text{\hspace{1em}(1)}$$ Since $f_X(s)⩾s$, we have that $$\{f_X(s)+1,f_X(s)+2,\dots \}\cap X=\{f_X(s)+1,f_X(s)+2,\dots \}\cap Y$$ which, together with the assumption that $|X|=|Y|$, gives $$\begin{array}{c}|X\cap \{1,2,\dots ,f_X(s)\}|=|Y\cap \{1,2,\dots ,f_X(s)\}|\end{array}\text{\hspace{1em}(2)}$$ Now consider the equation $$t-|Y\cap \{1,2,\dots ,t\}|=s$$ This equation is satisfied only when $t\in [f_Y(s),f_Y(s+1))$, because the left hand side counts the number of elements up to $t$ that are not in $Y$. We have that the value $t=f_X(s)$ satisfies the above equation because of (1) and (2). Furthermore, since $f_X(s)\notin X$ and $f_X(s)⩾s$, we have that $f_X(s)\notin Y$ due to the maximality of $s$. Thus, by the above discussion, we must have $f_X(s)=f_Y(s)$.

Finally, we arrive at a contradiction. The value $f_X(s)$ is neither in $X$ nor in $f_X(Y)$, because $s$ is not in $Y$ by assumption. Thus, $f_X(s)\notin X\ast Y$. However, since $s\in X$, we have $f_Y(s)\in Y\ast X$, a contradiction.

---

Alternative solution.

We will use Lemma 1 from Solution 1. Additionally, let $X^{\ast k}$ be defined as in Solution 1. If $X$ and $Y$ are finite sets, then $$\begin{array}{c}{f}_X=f_Y⟺f_X({\mathbb{Z}}_{>0})=f_Y({\mathbb{Z}}_{>0})⟺({\mathbb{Z}}_{>0}\setminus X)=({\mathbb{Z}}_{>0}\setminus Y)⟺X=Y,\end{array}\text{\hspace{1em}(3)}$$ where the first equivalence is because $f_X$ and $f_Y$ are strictly increasing functions, and the second equivalence is because $f_X({\mathbb{Z}}_{>0})={\mathbb{Z}}_{>0}\setminus X$ and $f_Y({\mathbb{Z}}_{>0})={\mathbb{Z}}_{>0}\setminus Y$.

Denote $g=f_A$ and $h=f_B$. The given relation $A\ast B=B\ast A$ is equivalent to $f_{A\ast B}=f_{B\ast A}$ because of (3), and by Lemma 1 of the first solution, this is equivalent to $g\circ h=h\circ g$. Similarly, the required relation $A^{\ast b}=B^{\ast a}$ is equivalent to $g^b=h^a$. We will show that $$\begin{array}{c}{g}^b(n)=h^a(n)\end{array}\text{\hspace{1em}(4)}$$ for all $n\in {\mathbb{Z}}_{>0}$, which suffices to solve the problem.

To start, we claim that (4) holds for all sufficiently large $n$. Indeed, let $p$ and $q$ be the maximal elements of $A$ and $B$, respectively; we may assume that $p⩾q$. Then, for every $n⩾p$ we have $g(n)=n+a$ and $h(n)=n+b$, whence $g^b(n)=n+ab=h^a(n)$, as was claimed.

In view of this claim, if (4) is not identically true, then there exists a maximal $s$ with $g^b(s)\ne h^a(s)$. Without loss of generality, we may assume that $g(s)\ne s$, for if we had $g(s)=h(s)=s$, then $s$ would satisfy (4). As $g$ is increasing, we then have $g(s)>s$, so (4) holds for $n=g(s)$. But then we have $$g(g^b(s))=g^{b+1}(s)=g^b(n)=h^a(n)=h^a(g(s))=g(h^a(s))$$ where the last equality holds in view of $g\circ h=h\circ g$. By the injectivity of $g$, the above equality yields $g^b(s)=h^a(s)$, which contradicts the choice of $s$. Thus, we have proved that (4) is identically true on ${\mathbb{Z}}_{>0}$, as desired.

Comment 2. We present another proof of Lemma 2 of the first solution.

Let $x=|X|=|Y|$. Say that $u$ is the smallest number in $X$ and $v$ is the smallest number in $Y$; assume without loss of generality that $u⩽v$.

Let $T$ be any finite set of positive integers, and define $t=|T|$. Enumerate the elements of $X$ as $x_1<x_2<\cdots <x_n$. Define $S_m=f_{T\ast X^{\ast (m-1)}}(X)$, and enumerate its elements $s_{m,1}<s_{m,2}<\cdots <s_{m,n}$. Note that the $S_m$ are pairwise disjoint; indeed, if we have $m<m^{\prime }$, then $$S_m\subset T\ast X^{\ast m}\subset T\ast X^{\ast (m^{\prime }-1)}\text{and}{S}_{m^{\prime }}=(T\ast X^{\ast m^{\prime }})\setminus (T\ast X^{\ast (m^{\prime }-1)})$$ We claim the following statement, which essentially says that the $S_m$ are eventually linear translates of each other:

Claim. For every $i$, there exists some $m_i$ and $c_i$ such that for all $m>m_i$, we have that $s_{m,i}=t+mn-c_i$. Furthermore, the $c_i$ do not depend on the choice of $T$.

First, we show that this claim implies Lemma 2. We may choose $T=X$ and $T=Y$. Then, there is some $m^{\prime }$ such that for all $m⩾m^{\prime }$, we have $$\begin{array}{c}{f}_{X^{\ast m}}(X)=f_{Y\ast X^{\ast (m-1)}}(X)\end{array}\text{\hspace{1em}(5)}$$ Because $u$ is the minimum element of $X$, $v$ is the minimum element of $Y$, and $u⩽v$, we have that $$\left(\bigcup _{m=m^{\prime }}^{\infty }{f}_{X\ast m}(X)\right)\cup X^{\ast m^{\prime }}=\left(\bigcup _{m=m^{\prime }}^{\infty }{f}_{Y\ast X^{\ast (m-1)}}(X)\right)\cup (Y\ast X^{\ast (m^{\prime }-1)})=\{u,u+1,\dots \}$$ and in both the first and second expressions, the unions are of pairwise distinct sets. By (5), we obtain $X^{\ast m^{\prime }}=Y\ast X^{\ast (m^{\prime }-1)}$. Now, because $X$ and $Y$ commute, we get $X^{\ast m^{\prime }}=X^{\ast (m^{\prime }-1)}\ast Y$, and so $X=Y$.

We now prove the claim.

Proof of the claim. We induct downwards on $i$, first proving the statement for $i=n$, and so on.

Assume that $m$ is chosen so that all elements of $S_m$ are greater than all elements of $T$ (which is possible because $T$ is finite). For $i=n$, we have that $s_{m,n}>s_{k,n}$ for every $k<m$. Thus, all $(m-1)n$ numbers of the form $s_{k,u}$ for $k<m$ and $1⩽u⩽n$ are less than $s_{m,n}$. We then have that $s_{m,n}$ is the $((m-1)n+x_n{)}^{\text{th}}$ number not in $T$, which is equal to $t+(m-1)n+x_n$. So we may choose $c_n=x_n-n$, which does not depend on $T$, which proves the base case for the induction.