Difference between revisions of "2019 USAJMO Problems/Problem 2"
The jake314 (talk | contribs) (→Solution) |
Brendanb4321 (talk | contribs) m (→Solution) |
||
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 < | + | 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</math>, so <math>|a|=|b|</math> does work and are the only solutions, as desired. |
-Stormersyle | -Stormersyle |
Revision as of 12:25, 14 May 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
, 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 |