2019 USAJMO Problems/Problem 2


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.


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|$.


$|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.


The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

See also

2019 USAJMO (ProblemsResources)
Preceded by
Problem 1
Followed by
Problem 3
1 2 3 4 5 6
All USAJMO Problems and Solutions