2019 USAJMO Problems/Problem 2
Let be the set of all integers. Find all pairs of integers for which there exist functions and satisfying for all integers .
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.
We claim that and exist if and 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, .
means that either or . works for the former and works for the latter, and we are done.
|2019 USAJMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAJMO Problems and Solutions|