AlgebraDifficulty 7.9National olympiad, round 2Find the answer
Find f:Z+→Z+, such that for any x,y∈Z+, f(f(x)+y)∣x+f(y).
A number or a short expression. Spacing and $ signs are ignored.
Solution
We are tasked with finding a function f:Z+→Z+ such that for any x,y∈Z+, f(f(x)+y)∣x+f(y).
### Solution
We will prove that the only solutions are: 1. f(x)=x, 2. f(x)={n1if x=1if x>1 for any n, 3. f(x)=⎩⎨⎧n12if x=1if x>1 is oddif x is even for any n odd.
#### Lemma f(x) is either injective or bounded.
Proof. Suppose f(a)=f(b)=t. Then, f(t+y)=f(f(a)+y)∣(a+f(y))andf(t+y)=f(f(b)+y)∣(b+f(y)) for any positive integer y. Therefore, f(t+y)∣(a−b). Since y can be arbitrarily large, either the left side is bounded (implying f is bounded) or a=b. □
#### Case 1: f is injective
Claim.f(1)=1.
Proof. Let f(1)=t. Then, f(t+y)∣(1+f(y))⟹f(y+t)≤f(y)+1. Thus, f(1+nt)≤f(1)+n. This means that for any n, the set {f(1),f(1+t),…,f(1+nt)} contains at least n+1 numbers in the interval [1,n+f(1)]. If t≥2, this clearly violates f being injective. □
We now use strong induction to prove f(n)=n for all n. The base case n=1 is already proven. Now assume that f(x)=x for all x=1,…,n−1. Plug in (x,y)=(n,1) in the original equation: f(f(n)+1)∣n+1. If f(f(n)+1)=k<n, then f(n)+1=k⟹f(n)=k−1, which violates injectivity. Therefore, f(n)+1=n+1, and f(n)=n, completing the induction.
#### Case 2: f is bounded
Let S be the (finite) set of values in imgf whose preimage is infinite. Then for any a,b such that f(a)=f(b), N:=lcms∈Ss∣(a−b). Therefore, ∣S∣≥N. But N≤∣S∣ can have at most ∣S∣ distinct divisors, and equality can only be achieved when S={1} or {1,2}.
- If S={1}, then f(n)=1 for all sufficiently large n. Plugging in (x,y)=(n,y), we have f(y+1)∣f(y)+n for all large enough n. This implies f(y+1)=1 for all y≥1. Clearly, f(1) can take any value.
- If S={1,2}, then 2∣(a−b) for any f(a)=f(b), so f(n) alternates between 1 and 2 for large enough n. Plugging in (x,y)=(n,y), we get f(y+f(n))∣f(y)+n. Taking n to be n and n+2, we get f(y+1)∣2 for any y. We further divide into two cases: - If f(n)=1 for n>1 odd and f(n)=2 when n is even, then plugging in y=1 and x>1 odd to the original equation gives 2∣x+f(1), meaning that f(1) is odd. - If f(n)=1 for n even and f(n)=2 for n>1 odd, then plugging in y=1 and x>1 odd to the original equation gives 2∣x+f(1), meaning that f(1) is odd, which is a contradiction.
Having exhausted all cases, we conclude that the solutions are as stated.
The answer is: \boxed{f(x) = x \text{ or } f(x) = \begin{cases} n & \text{if } x = 1 \\ 1 & \text{if } x > 1 \end{cases} \text{ or } f(x) = \begin{cases} n & \text{if } x = 1 \\ 1 & \text{if } x > 1 \text{ is odd} \\ 2 & \text{if } x \text{ is even} \end{cases} \text{ for any } n \text{ odd}}.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: Omni-MATH,
licensed Apache-2.0.
Statement and solution reproduced as published; topic and difficulty added by this site.