Difference between revisions of "2019 USAJMO Problems/Problem 2"
Stormersyle (talk | contribs) (→Solution) |
Stormersyle (talk | contribs) |
||
Line 3: | Line 3: | ||
==Solution== | ==Solution== | ||
+ | We claim that the answer is <math>|a|=|b|</math>. | ||
+ | |||
+ | Proof: | ||
<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>\{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}{ | + | 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}{2}</math>, so <math>|a|=|b|</math> does work and are the only solutions, as desired. |
-Stormersyle | -Stormersyle |
Revision as of 19:43, 19 April 2019
Problem
Let be the set of all integers. Find all pairs of integers for which there exist functions and satisfying for all integers .
Solution
We claim that the answer is .
Proof: and are surjective because and can take on any integral value, and by evaluating the parentheses in different order, we find and . We see that if then to as well, so similarly if then , so now assume .
We see that if then , if then , if then ... if then . This means that the -element collection contains all residues mod since is surjective, so . Doing the same to yields that , so this means that only can work.
For let and for let and , so 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.
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 |