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.

~emerald_block

These problems are copyrighted © by the Mathematical Association of America, as part of the 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

Contents

Problem

Solution 1

Solution 2

See also