Maths Olympiad Prep

Library / /37 of 37

Algebra Difficulty 7.9 National olympiad, round 2 Find the answer

Find f:Z+Z+f: \mathbb{Z}_+ \rightarrow \mathbb{Z}_+, such that for any x,yZ+x,y \in \mathbb{Z}_+, f(f(x)+y)x+f(y).f(f(x)+y)\mid 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+ f: \mathbb{Z}_+ \rightarrow \mathbb{Z}_+ such that for any x,yZ+ x, y \in \mathbb{Z}_+ ,
f(f(x)+y)x+f(y). f(f(x) + y) \mid x + f(y).

### Solution

We will prove that the only solutions are:
1. f(x)=x f(x) = x ,
2. f(x)={nif x=11if x>1 f(x) = \begin{cases} n & \text{if } x = 1 \\ 1 & \text{if } x > 1 \end{cases} for any n n ,
3. f(x)={nif x=11if x>1 is odd2if x is even 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} for any n n odd.

#### Lemma
f(x) f(x) is either injective or bounded.

Proof. Suppose f(a)=f(b)=t 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)) f(t + y) = f(f(a) + y) \mid (a + f(y)) \quad \text{and} \quad f(t + y) = f(f(b) + y) \mid (b + f(y))
for any positive integer y y . Therefore, f(t+y)(ab) f(t + y) \mid (a - b) . Since y y can be arbitrarily large, either the left side is bounded (implying f f is bounded) or a=b a = b . \square

#### Case 1: f f is injective

Claim. f(1)=1 f(1) = 1 .

Proof. Let f(1)=t f(1) = t . Then,
f(t+y)(1+f(y))    f(y+t)f(y)+1. f(t + y) \mid (1 + f(y)) \implies f(y + t) \leq f(y) + 1.
Thus,
f(1+nt)f(1)+n. f(1 + nt) \leq f(1) + n.
This means that for any n n , the set {f(1),f(1+t),,f(1+nt)} \{f(1), f(1 + t), \dots, f(1 + nt)\} contains at least n+1 n + 1 numbers in the interval [1,n+f(1)][1, n + f(1)]. If t2 t \geq 2 , this clearly violates f f being injective. \square

We now use strong induction to prove f(n)=n f(n) = n for all n n . The base case n=1 n = 1 is already proven. Now assume that f(x)=x f(x) = x for all x=1,,n1 x = 1, \dots, n - 1 . Plug in (x,y)=(n,1) (x, y) = (n, 1) in the original equation:
f(f(n)+1)n+1. f(f(n) + 1) \mid n + 1.
If f(f(n)+1)=k<n f(f(n) + 1) = k < n , then f(n)+1=k    f(n)=k1 f(n) + 1 = k \implies f(n) = k - 1 , which violates injectivity. Therefore, f(n)+1=n+1 f(n) + 1 = n + 1 , and f(n)=n f(n) = n , completing the induction.

#### Case 2: f f is bounded

Let S S be the (finite) set of values in imgf\text{img} f whose preimage is infinite. Then for any a,b a, b such that f(a)=f(b) f(a) = f(b) ,
N:=lcmsSs(ab). N := \text{lcm}_{s \in S} s \mid (a - b).
Therefore, SN |S| \geq N . But NS N \leq |S| can have at most S |S| distinct divisors, and equality can only be achieved when S={1} S = \{1\} or {1,2} \{1, 2\} .

- If S={1} S = \{1\} , then f(n)=1 f(n) = 1 for all sufficiently large n n . Plugging in (x,y)=(n,y) (x, y) = (n, y) , we have
f(y+1)f(y)+n f(y + 1) \mid f(y) + n
for all large enough n n . This implies f(y+1)=1 f(y + 1) = 1 for all y1 y \geq 1 . Clearly, f(1) f(1) can take any value.

- If S={1,2} S = \{1, 2\} , then 2(ab) 2 \mid (a - b) for any f(a)=f(b) f(a) = f(b) , so f(n) f(n) alternates between 1 1 and 2 2 for large enough n n . Plugging in (x,y)=(n,y) (x, y) = (n, y) , we get
f(y+f(n))f(y)+n. f(y + f(n)) \mid f(y) + n.
Taking n n to be n n and n+2 n + 2 , we get f(y+1)2 f(y + 1) \mid 2 for any y y . We further divide into two cases:
- If f(n)=1 f(n) = 1 for n>1 n > 1 odd and f(n)=2 f(n) = 2 when n n is even, then plugging in y=1 y = 1 and x>1 x > 1 odd to the original equation gives 2x+f(1) 2 \mid x + f(1) , meaning that f(1) f(1) is odd.
- If f(n)=1 f(n) = 1 for n n even and f(n)=2 f(n) = 2 for n>1 n > 1 odd, then plugging in y=1 y = 1 and x>1 x > 1 odd to the original equation gives 2x+f(1) 2 \mid x + f(1) , meaning that f(1) 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.