Maths Olympiad Prep

Library / /4 of 20

Number theory Difficulty 6.3 National olympiad Find the answer

Find all f:NNf : \mathbb{N} \to \mathbb{N} such that f(a)+f(b)f(a) + f(b) divides 2(a+b1)2(a + b - 1) for all a,bNa, b \in \mathbb{N}.

Remark: N={1,2,3,}\mathbb{N} = \{ 1, 2, 3, \ldots \} denotes the set of the positive integers.

A number or a short expression. Spacing and $ signs are ignored.

Solution

We need to find all functions f:NN f : \mathbb{N} \to \mathbb{N} such that f(a)+f(b) f(a) + f(b) divides 2(a+b1) 2(a + b - 1) for all a,bN a, b \in \mathbb{N} .

Begin by analyzing the given divisibility condition:
f(a)+f(b)2(a+b1). f(a) + f(b) \mid 2(a + b - 1).

### Step 1: Simplify for Special Cases

Consider the case where a=b a = b :
f(a)+f(a)2(2a1). f(a) + f(a) \mid 2(2a - 1).
This implies:
2f(a)4a2. 2f(a) \mid 4a - 2.
Thus, f(a)2a1 f(a) \mid 2a - 1 .

### Step 2: Testing Specific Values

Let's test some simple function forms to see if they satisfy the condition:

**Case 1: f(x)=1 f(x) = 1 for all xN x \in \mathbb{N} **

If f(a)=1 f(a) = 1 for all a a ,
1+1=22(a+b1). 1 + 1 = 2 \mid 2(a + b - 1).
This simplifies to:
22(a+b1), 2 \mid 2(a + b - 1),
which is always true. Thus, f(x)=1 f(x) = 1 is a solution.

**Case 2: f(x)=2x1 f(x) = 2x - 1 for all xN x \in \mathbb{N} **

Consider f(a)=2a1 f(a) = 2a - 1 and f(b)=2b1 f(b) = 2b - 1 ,
(2a1)+(2b1)=2a+2b2. (2a - 1) + (2b - 1) = 2a + 2b - 2.
This implies:
2a+2b22(a+b1), 2a + 2b - 2 \mid 2(a + b - 1),
which is obviously true as they are equal. Thus, f(x)=2x1 f(x) = 2x - 1 is also a solution.

### Step 3: Confirm that there are no other forms

To ensure there are no other forms, consider the condition f(a)2a1 f(a) \mid 2a - 1 from step 1. For f(a)=k f(a) = k , imply k2a1 k \mid 2a - 1 . Testing this divisibility will only work straightforwardly with k=1 k = 1 or k=2a1 k = 2a - 1 due to divisibility constraints dictated by the natural number range.

### Conclusion

As our formed solutions satisfy all conditions with no divisibility conflicts, and no arbitrary other functions satisfy the condition f(a)2a1 f(a) \mid 2a - 1 consistently across all a a , we find that the solutions are:
f(x)=1orf(x)=2x1. f(x) = 1 \quad \text{or} \quad f(x) = 2x - 1.

Since these are the only functions that satisfy the given condition for all a,bN a, b \in \mathbb{N} , the answer is:
f(x)=1orf(x)=2x1. \boxed{f(x) = 1 \quad \text{or} \quad f(x) = 2x - 1.}

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.