2012 USAMO Problems/Problem 4
Find all functions (where is the set of positive integers) such that for all positive integers and such that divides for all distinct positive integers , .
Note that and , so or and similarly for . We always have (1)
Now if for any , then for all . This follows because then , which is only possible if , and the rest follows by induction. We now divide into cases:
This gives always from the previous claim, which is a solution.
This implies for all , but this does not satisfy the initial conditions. Indeed, we would have so , a contradiction.
Case 3: ,
We claim always by induction. The bases cases are already shown. If , then by (1) we have Which gives (otherwise ). Also we have so . This gives the solutions (obviously impossible) and . Then by induction, this always holds. Note that this also satisfies the requirements.
We claim by a similar induction. Again if , then by (1) we have Which gives similarly. Also note that so . Then the only possible solution is . By induction this always holds, and note that this satisfies the requirements.
The solutions are .
|2012 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|