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


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+a$ and $g(x)=-x-a$, so $|a|=|b|$ does work and are the only solutions, as desired.


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
Invalid username
Login to AoPS