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: for . 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.
Let's assume Substitute to get
This means that is a perfect square. However, this is impossible, as it is equivalent to Therefore, Now substitute to get Similarly, From these two equations, we can find either or Both of these are valid solutions on their own, so let's see if there are any solutions combining the two.
Let's say we can find and Then (NEEDS FIXING: , so the RHS is instead of .)
If then which is only possible when This contradicts our assumption. Therefore, This forces due to the right side of the equation. Let's consider the possibility Substituting into the original equation yields which is impossible. So and there are no solutions "combining" and
Therefore our only solutions are and