Maths Olympiad Prep

Library / /8 of 27

Algebra Difficulty 6.5 National olympiad Find the answer

Find all functions f:NNf:\mathbb{N}\rightarrow \mathbb{N} such that the inequality f(x)+yf(f(x))x(1+f(y))f(x)+yf(f(x))\le x(1+f(y))
holds for all positive integers x,yx, y.

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

Solution

Let's analyze the problem by working with the given inequality:

f(x)+yf(f(x))x(1+f(y)) f(x) + y f(f(x)) \le x(1 + f(y))

for all positive integers x,yx, y.

To find all functions f:NNf: \mathbb{N} \rightarrow \mathbb{N} satisfying this inequality, we will first test some small values and then generalize our findings.

Step 1: Consider specific cases.

1. **For y=1y = 1:**

f(x)+f(f(x))x(1+f(1)) f(x) + f(f(x)) \le x(1 + f(1))

Rearranging gives:

f(x)+f(f(x))x+xf(1) f(x) + f(f(x)) \le x + x f(1)

2. **For x=1x = 1:**

f(1)+yf(f(1))1(1+f(y))=1+f(y) f(1) + y f(f(1)) \le 1(1 + f(y)) = 1 + f(y)

Which simplifies to:

yf(f(1))1+f(y)f(1) y f(f(1)) \le 1 + f(y) - f(1)

Since yy is arbitrary, this implies f(f(1))=0f(f(1)) = 0 unless f(x)=xf(x) = x.

**Step 2: Consider f(x)=xf(x) = x.**

Assume f(x)=xf(x) = x for all xNx \in \mathbb{N}.

Substitute into the original inequality:

x+yf(x)x(1+f(y)) x + y f(x) \le x(1 + f(y))

which becomes:

x+yxx+xy x + yx \le x + xy

This simplifies to:

x+yxx+xy x + yx \le x + xy

The inequality holds, which suggests that f(x)=xf(x) = x is indeed a solution.

Step 3: Consider the nature of the function.

Assuming any function f(x)f(x) other than the identity leads to contradictions in maintaining the inequality universally.

For instance, choosing other forms may not satisfy for larger values of x,yx, y, due to the restrictive nature of the inequality, especially where powers of ff terms (like f(f(x))f(f(x))) would arise.

Therefore, after analyzing potential options, we determine that the function:

f(x)=x f(x) = x

is the only solution that satisfies the given inequality for all x,yNx, y \in \mathbb{N}.

Thus, the solution to the problem is:

f(x)=x \boxed{f(x) = x}

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.