Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2019 USAJMO Problems/Problem 2"
(Add new solution, fix incorrect example of f and g in Solution 1)
 
(2 intermediate revisions by 2 users not shown)
Line 2: Line 2:
 
Let <math>\mathbb Z</math> be the set of all integers. Find all pairs of integers <math>(a,b)</math> for which there exist functions <math>f:\mathbb Z\rightarrow\mathbb Z</math> and <math>g:\mathbb Z\rightarrow\mathbb Z</math> satisfying <cmath>f(g(x))=x+a\quad\text{and}\quad g(f(x))=x+b</cmath> for all integers <math>x</math>.
 
Let <math>\mathbb Z</math> be the set of all integers. Find all pairs of integers <math>(a,b)</math> for which there exist functions <math>f:\mathbb Z\rightarrow\mathbb Z</math> and <math>g:\mathbb Z\rightarrow\mathbb Z</math> satisfying <cmath>f(g(x))=x+a\quad\text{and}\quad g(f(x))=x+b</cmath> for all integers <math>x</math>.
  
−
==Solution==
+
==Solution 1==
 
We claim that the answer is <math>|a|=|b|</math>.
 
We claim that the answer is <math>|a|=|b|</math>.
  
Line 8: Line 8:
 
<math>f</math> and <math>g</math> are surjective because <math>x+a</math> and <math>x+b</math> can take on any integral value, and by evaluating the parentheses in different order, we find <math>f(g(f(x)))=f(x+b)=f(x)+a</math> and <math>g(f(g(x)))=g(x+a)=g(x)+b</math>. We see that if <math>a=0</math> then <math>g(x)=g(x)+b</math> to <math>b=0</math> as well, so similarly if <math>b=0</math> then <math>a=0</math>, so now assume <math>a, b\ne 0</math>.  
 
<math>f</math> and <math>g</math> are surjective because <math>x+a</math> and <math>x+b</math> can take on any integral value, and by evaluating the parentheses in different order, we find <math>f(g(f(x)))=f(x+b)=f(x)+a</math> and <math>g(f(g(x)))=g(x+a)=g(x)+b</math>. We see that if <math>a=0</math> then <math>g(x)=g(x)+b</math> to <math>b=0</math> as well, so similarly if <math>b=0</math> then <math>a=0</math>, so now assume <math>a, b\ne 0</math>.  
  
−
We see that if <math>x=|b|n</math> then <math>f(x)\equiv f(0) \pmod{|a|}</math>, if <math>x=|b|n+1</math> then <math>f(x)\equiv f(1)\pmod{|a|}</math>, if <math>x=|b|n+2</math> then <math>f(x)\equiv f(2)\pmod{|a|}</math>... if <math>x=|b|(n+1)-1</math> then <math>f(x)\equiv f(|b|-1)\pmod{|a|}</math>. This means that the <math>b</math>-element collection <math>\{f(0), f(1), f(2), ... ,f(|b|-1)\}</math> contains all <math>|a|</math> residues mod <math>|a|</math> since <math>f</math> is surjective, so <math>|b|\ge |a|</math>. Doing the same to <math>g</math> yields that <math>|a|\ge |b|</math>, so this means that only <math>|a|=|b|</math> can work.
+
We see that if <math>x=|b|n</math> then <math>f(x)\equiv f(0) \pmod{|a|}</math>, if <math>x=|b|n+1</math> then <math>f(x)\equiv f(1)\pmod{|a|}</math>, if <math>x=|b|n+2</math> then <math>f(x)\equiv f(2)\pmod{|a|}</math>... if <math>x=|b|(n+1)-1</math> then <math>f(x)\equiv f(|b|-1)\pmod{|a|}</math>. This means that the <math>b</math>-element collection <math>\left\{f(0), f(1), f(2), ... ,f(|b|-1)\right\}</math> contains all <math>|a|</math> residues mod <math>|a|</math> since <math>f</math> is surjective, so <math>|b|\ge |a|</math>. Doing the same to <math>g</math> yields that <math>|a|\ge |b|</math>, so this means that only <math>|a|=|b|</math> can work.
  
−
For <math>a=b</math> let <math>f(x)=x</math> and <math>g(x)=x+a</math>, and for <math>a=-b</math> let <math>f(x)=-x+a</math> and <math>g(x)=-x-a, so </math>|a|=|b|$ does work and are the only solutions, as desired.
+
For <math>a=b</math> let <math>f(x)=x</math> and <math>g(x)=x+a</math>, and for <math>a=-b</math> let <math>f(x)=-x</math> and <math>g(x)=-x-a</math>, so <math>|a|=|b|</math> does work and are the only solutions, as desired.
  
 
-Stormersyle
 
-Stormersyle
 +
 +
==Solution 2==
 +
 +
We claim that <math>f</math> and <math>g</math> exist if and only if <math>|a|=|b|</math>.
 +
 +
<b>Only If:</b>
 +
 +
For some fixed <math>j</math>, let <math>f(j)=k</math>.
 +
 +
If <math>b=0</math>, then <math>g(k)=j</math>. Suppose <math>a\ne 0</math>. Then <math>f(j)=f(g(k))=k+a\ne k</math>, a contradiction. Thus, <math>a=0</math>. Similarly, if <math>a=0</math>, then <math>b=0</math>, satisfying <math>|a|=|b|</math>.
 +
 +
Otherwise, <math>a,b\ne 0</math>. We know that <math>g(k)=g(f(j))=j+b</math>, <math>f(j+b)=f(g(k))=k+a</math>, <math>g(k+a)=j+2b</math>, and so on: <math>f(j+nb)=k+na</math> and <math>g(k+na)=j+(n+1)b</math> for <math>n\ge 0</math>.
 +
 +
Consider the value of <math>g(k-a)</math>. Suppose <math>g(k-a)=j'\ne j</math>. Then <math>f(j')=k</math> and <math>g(f(j'))=j+b\ne j'+b</math>, a contradiction. Thus, <math>g(k-a)=j</math>. We repeat with <math>f(j-b)</math>. Suppose <math>f(j-b)=k'-b\ne k-b</math>. Then <math>g(k'-b)=j</math> and <math>f(g(k'-b))=k\ne k'</math>, a contradition. Thus, <math>f(j-b)=k-b</math>. Continuing, <math>g(k-2a)=j-a</math>, and so on: <math>f(j+nb)=k+na</math> and <math>g(k+na)=j+(n+1)b</math> now for all <math>n</math>.
 +
 +
This defines <math>f(x)</math> for all <math>x\equiv j\pmod{|b|}</math> and <math>g(x)</math> for all <math>x\equiv f(j)\pmod{|a|}</math>.
 +
 +
This means that <math>x\equiv j\pmod{|b|}\implies f(x)\equiv f(j)\pmod{|a|}</math>, and <math>y\equiv f(j)\pmod{|a|}\implies g(y)\equiv j\pmod{|b|}</math> which implies <math>f(x)\equiv f(j)\pmod{|a|}\implies x\equiv j\pmod{|b|}</math>.
 +
 +
As a result, <math>f(x)</math> maps each residue mod <math>|b|</math> to a unique residue mod <math>|a|</math>, so <math>|a|\ge|b|</math>. Similarly, <math>g(x)</math> maps each residue mod <math>|a|</math> to a unique residue mod <math>|b|</math>, so <math>|b|\ge|a|</math>. Therefore, <math>|a|=|b|</math>.
 +
 +
<b>If:</b>
 +
 +
<math>|a|=|b|</math> means that either <math>a=b</math> or <math>a=-b</math>. <math>f(x)=x,g(x)=x+a</math> works for the former and <math>f(x)=-x,g(x)=-x-a</math> works for the latter, and we are done.
 +
 +
~[[User:emerald_block|emerald_block]]
  
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 17:53, 7 April 2021

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

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

See also

2019 USAJMO (Problems • Resources)
Preceded by
Problem 1 		Followed by
Problem 3
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_USAJMO_Problems/Problem_2&oldid=151214"