2012 USAMO Problems/Problem 4
Problem
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
,
.
Solution
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:
Case 1:
This gives always from the previous claim, which is a solution.
Case 2:
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.
Case 4:
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 .
See also
2012 USAMO (Problems • Resources) | ||
Preceded by Problem 3 |
Followed by Problem 5 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |