Maths Olympiad Prep

Library / /4 of 21

Number theory Difficulty 7.5 National olympiad, round 2 Find the answer

Given an integer k2k\geq 2, determine all functions ff from the positive integers into themselves such that f(x1)!+f(x2)!+f(xk)!f(x_1)!+f(x_2)!+\cdots f(x_k)! is divisibe by x1!+x2!+xk!x_1!+x_2!+\cdots x_k! for all positive integers x1,x2,xkx_1,x_2,\cdots x_k.

AlbaniaAlbania

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

Solution

Consider the function f f from the positive integers into themselves. We need to determine all such functions such that for every collection of positive integers x1,x2,,xk x_1, x_2, \ldots, x_k , the expression

f(x1)!+f(x2)!++f(xk)! f(x_1)! + f(x_2)! + \cdots + f(x_k)!

is divisible by

x1!+x2!++xk!. x_1! + x_2! + \cdots + x_k!.

Given that k2 k \geq 2 , let's analyze the problem by initially testing simple cases and then move towards a general solution.

### Step 1: Substituting x1=x2==xk=x x_1 = x_2 = \cdots = x_k = x

Consider the case where x1=x2==xk=x x_1 = x_2 = \cdots = x_k = x . The condition reduces to:

kf(x)!0(modkx!). k \cdot f(x)! \equiv 0 \pmod{k \cdot x!}.

This can be simplified to:

f(x)!0(modx!). f(x)! \equiv 0 \pmod{x!}.

The most straightforward solution would be the case f(x)=x f(x) = x , resulting in f(x)!=x! f(x)! = x! . This satisfies the divisibility condition since x!0(modx!) x! \equiv 0 \pmod{x!} holds trivially for any x x .

### Step 2: Generalization and Testing

Now, consider the general function f f where f(n)n f(n) \neq n . We need to show whether f(n)=n f(n) = n is uniquely valid or if other functions also satisfy the condition:

Assume f(n)n f(n) \neq n for some n n . Consider x1=x2==xk1=n x_1 = x_2 = \cdots = x_{k-1} = n and xk=f(n) x_k = f(n) .

For divisibility, we should have:

(k1)f(n)!+n! is divisible by (k1)n!+f(n)!. (k-1) \cdot f(n)! + n! \text{ is divisible by } (k-1) \cdot n! + f(n)!.

By the properties of factorials, if f(n)<n f(n) < n , then f(n)! f(n)! does not divide n! n! , causing issues in divisibility unless kf(n)!n! k \cdot f(n)! \geq n! . Similarly, if f(n)>n f(n) > n , f(n)! f(n)! exceeds any term of the form n! n! , contradicting divisibility.

### Conclusion

Therefore, the function f(n)=n f(n) = n ensures f(x1)!+f(x2)!++f(xk)! f(x_1)! + f(x_2)! + \cdots + f(x_k)! is divisible by x1!+x2!++xk! x_1! + x_2! + \cdots + x_k! for all choices of x1,x2,,xk x_1, x_2, \ldots, x_k .

Thus, the only solution is:
f(n)=n. \boxed{f(n) = n}.

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.