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"

(Created page with "==Problem== 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\m...")
 
(→‎Solution)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
 
+
<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>. Note that if <math>a=0</math> then <math>f(g(x))=x</math>, so <math>g(f(x))=x</math> and <math>b=0</math>, because <math>f</math> and <math>g</math> are surjective Similarly, we find that if <math>b=0</math> then <math>a=0</math>.
 +
Now, 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.
 +
For <math>a=b</math> let <math>f(x)=g(x)=x+\frac{a}{2}</math> and for <math>a=-b</math> let <math>f(x)=-x+\frac{a}{2}</math> and <math>g(x)=-x-\frac{a}{s}</math>, so <math>|a|=|b|</math> does work.
 +
-Stormersyle
  
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 19:37, 19 April 2019

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

$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$. Note that if $a=0$ then $f(g(x))=x$, so $g(f(x))=x$ and $b=0$, because $f$ and $g$ are surjective Similarly, we find that if $b=0$ then $a=0$. Now, 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)=g(x)=x+\frac{a}{2}$ and for $a=-b$ let $f(x)=-x+\frac{a}{2}$ and $g(x)=-x-\frac{a}{s}$, so $|a|=|b|$ does work. -Stormersyle

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=105378"