2019 USAJMO Problems/Problem 2

Problem

Let $\mathbb Z$ be the set of all integers. Find all pairs of integers $(a,b)$ for which there exist functions $f:\mathbb Z\rightarrow\mathbb Z$ and $g:\mathbb Z\rightarrow\mathbb Z$ satisfying $$f(g(x))=x+a\quad\text{and}\quad g(f(x))=x+b$$ for all integers $x$.

Solution 1

We claim that the answer is $|a|=|b|$.

Proof: $f$ and $g$ are surjective because $x+a$ and $x+b$ can take on any integral value, and by evaluating the parentheses in different order, we find $f(g(f(x)))=f(x+b)=f(x)+a$ and $g(f(g(x)))=g(x+a)=g(x)+b$. We see that if $a=0$ then $g(x)=g(x)+b$ to $b=0$ as well, so similarly if $b=0$ then $a=0$, so now assume $a, b\ne 0$.

We see that if $x=|b|n$ then $f(x)\equiv f(0) \pmod{|a|}$, if $x=|b|n+1$ then $f(x)\equiv f(1)\pmod{|a|}$, if $x=|b|n+2$ then $f(x)\equiv f(2)\pmod{|a|}$... if $x=|b|(n+1)-1$ then $f(x)\equiv f(|b|-1)\pmod{|a|}$. This means that the $b$-element collection $\left\{f(0), f(1), f(2), ... ,f(|b|-1)\right\}$ contains all $|a|$ residues mod $|a|$ since $f$ is surjective, so $|b|\ge |a|$. Doing the same to $g$ yields that $|a|\ge |b|$, so this means that only $|a|=|b|$ can work.

For $a=b$ let $f(x)=x$ and $g(x)=x+a$, and for $a=-b$ let $f(x)=-x$ and $g(x)=-x-a$, so $|a|=|b|$ does work and are the only solutions, as desired.

-Stormersyle

Solution 2

We claim that $f$ and $g$ exist if and only if $|a|=|b|$.

Only If:

For some fixed $j$, let $f(j)=k$.

If $b=0$, then $g(k)=j$. Suppose $a\ne 0$. Then $f(j)=f(g(k))=k+a\ne k$, a contradiction. Thus, $a=0$. Similarly, if $a=0$, then $b=0$, satisfying $|a|=|b|$.

Otherwise, $a,b\ne 0$. We know that $g(k)=g(f(j))=j+b$, $f(j+b)=f(g(k))=k+a$, $g(k+a)=j+2b$, and so on: $f(j+nb)=k+na$ and $g(k+na)=j+(n+1)b$ for $n\ge 0$.

Consider the value of $g(k-a)$. Suppose $g(k-a)=j'\ne j$. Then $f(j')=k$ and $g(f(j'))=j+b\ne j'+b$, a contradiction. Thus, $g(k-a)=j$. We repeat with $f(j-b)$. Suppose $f(j-b)=k'-b\ne k-b$. Then $g(k'-b)=j$ and $f(g(k'-b))=k\ne k'$, a contradition. Thus, $f(j-b)=k-b$. Continuing, $g(k-2a)=j-a$, and so on: $f(j+nb)=k+na$ and $g(k+na)=j+(n+1)b$ now for all $n$.

This defines $f(x)$ for all $x\equiv j\pmod{|b|}$ and $g(x)$ for all $x\equiv f(j)\pmod{|a|}$.

This means that $x\equiv j\pmod{|b|}\implies f(x)\equiv f(j)\pmod{|a|}$, and $y\equiv f(j)\pmod{|a|}\implies g(y)\equiv j\pmod{|b|}$ which implies $f(x)\equiv f(j)\pmod{|a|}\implies x\equiv j\pmod{|b|}$.

As a result, $f(x)$ maps each residue mod $|b|$ to a unique residue mod $|a|$, so $|a|\ge|b|$. Similarly, $g(x)$ maps each residue mod $|a|$ to a unique residue mod $|b|$, so $|b|\ge|a|$. Therefore, $|a|=|b|$.

If:

$|a|=|b|$ means that either $a=b$ or $a=-b$. $f(x)=x,g(x)=x+a$ works for the former and $f(x)=-x,g(x)=-x-a$ works for the latter, and we are done.

 2019 USAJMO (Problems • Resources) Preceded byProblem 1 Followed byProblem 3 1 • 2 • 3 • 4 • 5 • 6 All USAJMO Problems and Solutions