The exceptional value 2008 in a functional inequality

bonk.dll·Jul 2, 2025(edited)

I found

f\equiv1

and

f(n)=n

. I suspect

f(n)\le n

, but the shortlist claims there is one more possible value at 2007. Where does that extra one come from? Problem: Consider those functions

f: \mathbb{N} \rightarrow \mathbb{N}

which satisfy the condition

f(m+n) \geq f(m)+f(f(n))-1

for all

m, n \in \mathbb{N}

. Find all possible values of

f(2007)

. (

\mathbb{N}

denotes the set of all positive integers.) Source: IMO 2007 Shortlist · MNET-06P7

Open MNET-06P7 in the question bank →

8 replies

respawn_pending·Jul 4, 2025(edited)

First,

f

is nondecreasing: write

m=n+(m-n)

and use

f(f(m-n))\ge1

. But the bound you want is actually

f(n)\le n+1

bonk.dll·Jul 4, 2025

How do we control

f(n)-n

without assuming it has a maximum?

respawn_pending·Jul 4, 2025

Unless

f\equiv1

, let a be the first index with

f(a)>1

. If

f(n)>n

, apply the inequality with arguments

f(n)-n

and n. It forces

f(f(n)-n)=1

, hence

f(n)-n<a

. The positive integer excesses are bounded, so a maximum c exists if there is any excess.

korok_delivery·Jul 4, 2025

At an index k with

f(k)=k+c

, monotonicity gives

f(f(k))\ge f(k)

. Then

2k+c\ge f(2k)\ge2(k+c)-1

, so

c\le1

bonk.dll·Jul 5, 2025

That proves the upper bound. Is

f(n)=n+1

the extremal example?

respawn_pending·Jul 5, 2025

No: composition makes that fail by one. Instead set

f(n)=n+1

when

2007\mid n

, and

f(n)=n

otherwise. For this function

f(f(n))=f(n)

bonk.dll·Jul 5, 2025

If m+n is divisible by 2007, the left side gets the extra one. If it isn't, m and n cannot both be multiples, so the right side gets at most one extra before subtracting 1. That works.

respawn_pending·Jul 5, 2025

For each

1\le j\le2007

, use

g_j(n)=\max(1,n+j-2007)

. It is nondecreasing and

g_j(n)\le n

. If

g_j(m)=1

, monotonicity handles the inequality; otherwise

g_j(m)+g_j(g_j(n))-1\le m+j-2007+n-1<g_j(m+n)

. Thus every value 1 through 2008 occurs.

Join the discussion

A hint, a different approach, or a thoughtful question can help.

Loading discussion…

The exceptional value 2008 in a functional inequality

bonk.dll·Jul 2, 2025(edited)

I found

f\equiv1

and

f(n)=n

. I suspect

f(n)\le n

, but the shortlist claims there is one more possible value at 2007. Where does that extra one come from? Problem: Consider those functions

f: \mathbb{N} \rightarrow \mathbb{N}

which satisfy the condition

f(m+n) \geq f(m)+f(f(n))-1

for all

m, n \in \mathbb{N}

. Find all possible values of

f(2007)

. (

\mathbb{N}

denotes the set of all positive integers.) Source: IMO 2007 Shortlist · MNET-06P7

Open MNET-06P7 in the question bank →

8 replies

respawn_pending·Jul 4, 2025(edited)

First,

f

is nondecreasing: write

m=n+(m-n)

and use

f(f(m-n))\ge1

. But the bound you want is actually

f(n)\le n+1

bonk.dll·Jul 4, 2025

How do we control

f(n)-n

without assuming it has a maximum?

respawn_pending·Jul 4, 2025

Unless

f\equiv1

, let a be the first index with

f(a)>1

. If

f(n)>n

, apply the inequality with arguments

f(n)-n

and n. It forces

f(f(n)-n)=1

, hence

f(n)-n<a

. The positive integer excesses are bounded, so a maximum c exists if there is any excess.

korok_delivery·Jul 4, 2025

At an index k with

f(k)=k+c

, monotonicity gives

f(f(k))\ge f(k)

. Then

2k+c\ge f(2k)\ge2(k+c)-1

, so

c\le1

bonk.dll·Jul 5, 2025

That proves the upper bound. Is

f(n)=n+1

the extremal example?

respawn_pending·Jul 5, 2025

No: composition makes that fail by one. Instead set

f(n)=n+1

when

2007\mid n

, and

f(n)=n

otherwise. For this function

f(f(n))=f(n)

bonk.dll·Jul 5, 2025

If m+n is divisible by 2007, the left side gets the extra one. If it isn't, m and n cannot both be multiples, so the right side gets at most one extra before subtracting 1. That works.

respawn_pending·Jul 5, 2025

For each

1\le j\le2007

, use

g_j(n)=\max(1,n+j-2007)

. It is nondecreasing and

g_j(n)\le n

. If

g_j(m)=1

, monotonicity handles the inequality; otherwise

g_j(m)+g_j(g_j(n))-1\le m+j-2007+n-1<g_j(m+n)

. Thus every value 1 through 2008 occurs.