Difference between revisions of "2019 USAJMO Problems/Problem 2"
Brendanb4321 (talk | contribs) m (→Solution) |
(Add new solution, fix incorrect example of f and g in Solution 1) |
||
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 10: | Line 10: | ||
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. | 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 17: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 |