Difference between revisions of "2019 USAJMO Problems/Problem 2"
The jake314 (talk | contribs) (→Solution) |
(Add new solution, fix incorrect example of f and g in Solution 1) |
||
(One intermediate revision by one other user 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 | + | 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 18:53, 7 April 2021
Contents
Problem
Let be the set of all integers. Find all pairs of integers
for which there exist functions
and
satisfying
for all integers
.
Solution 1
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
Solution 2
We claim that and
exist if and only if
.
Only If:
For some fixed , let
.
If , then
. Suppose
. Then
, a contradiction. Thus,
. Similarly, if
, then
, satisfying
.
Otherwise, . We know that
,
,
, and so on:
and
for
.
Consider the value of . Suppose
. Then
and
, a contradiction. Thus,
. We repeat with
. Suppose
. Then
and
, a contradition. Thus,
. Continuing,
, and so on:
and
now for all
.
This defines for all
and
for all
.
This means that , and
which implies
.
As a result, maps each residue mod
to a unique residue mod
, so
. Similarly,
maps each residue mod
to a unique residue mod
, so
. Therefore,
.
If:
means that either
or
.
works for the former and
works for the latter, and we are done.
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 |