Problem 1

The function

f(n)

is defined on the positive integers and takes non-negative integer values.

f(2)=0

f(3)>0

f(9999)=3333

, and for all

m,n

f(m+n)-f(m)-f(n)=0 \text{ or } 1.

Determine

f(1982)

Step 1 of 7: Superadditivity forces

f(1)=0

Previous step Next step

In plain words

The whole problem rests on one observation: the defect $f(m+n)-f(m)-f(n)$ never goes negative, so splitting an argument into pieces can only help, never hurt, the value of $f$ .

f(2)=f(1+1)\ge f(1)+f(1) \ \Rightarrow\ 0\ge 2f(1) \ \Rightarrow\ f(1)=0

Detailed analysis

The hypothesis says $f(m+n)-f(m)-f(n)$ is always $0$ or $1$ , hence always $\ge 0$ : $f$ is superadditive, $f(m+n)\ge f(m)+f(n)$ . Taking $m=n=1$ gives $f(2)\ge 2f(1)$ . Since $f(2)=0$ and $f$ only takes non-negative values, $f(1)=0$ .