2014 USAMO Problems/Problem 2
Let be the set of integers. Find all functions such that for all with .
Note: This solution is kind of rough. I didn't want to put my 7-page solution all over again. It would be nice if someone could edit in the details of the expansions.
Lemma 1: . Proof: Assume the opposite for a contradiction. Plug in (because we assumed that ), . What you get eventually reduces to: which is a contradiction since the LHS is divisible by 2 but not 4.
Then plug in into the original equation and simplify by Lemma 1. We get: Then:
Therefore, must be 0 or .
Now either is for all or there exists such that . The first case gives a valid solution. In the second case, we let in the original equation and simplify to get: But we know that , so: Since is not 0, is 0 for all (including 0). Now either is 0 for all , or there exists some such that . Then must be odd. We can let in the original equation, and since is 0 for all , stuff cancels and we get: [b]for .[/b] Now, let and we get: Now, either both sides are 0 or both are equal to . If both are then: which simplifies to: Since and is odd, both cases are impossible, so we must have: Then we can let be anything except 0, and get is 0 for all except . Also since , we have , so is 0 for all except . So is 0 for all except . Since , . Squaring, and dividing by , . Since , , which is a contradiction for . However, if we plug in with and as an arbitrary large number with into the original equation, we get which is a clear contradiction, so our only solutions are and .
Given that the range of f consists entirely of integers, it is clear that the LHS must be an integer and must also be an integer, therefore is an integer. If divides for all integers , then must be a factor of , therefore . Now, by setting in the original equation, this simplifies to . Assuming , we have . Substituting in for gives us . Substituting in in for in the second equation gives us , so . In particular, if , then we have , therefore is equivalent to or for every integer . Now, we shall prove that if for some integer , if , then for all integers . If we assume and in the original equation, this simplifies to . However, since , we can rewrite this equation as , must therefore be equivalent to . Since, by our initial assumption, , this means that , so, if for some integer , , then for all integers . The contrapositive must also be true, i.e. If for all integers , then there is no integral value of such that , therefore must be equivalent for for every integer , including , since . Thus, are the only possible solutions.