2019 USAJMO Problems/Problem 2
Contents
[hide]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 |