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

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 $\{f(0), f(1), f(2), ... ,f(|b|-1)\}$ 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.

-Stormersyle

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

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

Page

Toolbox

Search

2019 USAJMO Problems/Problem 2

Problem

Solution

See also