IMO 1982 Problem 1

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 15m34s

Problem

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)$.

Exploration

The previous approach failed because it attempted to propagate “local errors” globally without any invariant controlling how the defect $f(m+n)-f(m)-f(n)\in{0,1}$ behaves under different decompositions of the same integer. A correct approach must avoid any reliance on additive-density heuristics and instead extract rigid local constraints that fully determine the increment sequence.

The increment encoding $a_n=f(n+1)-f(n)\in{0,1}$ is unavoidable, since $f(n+1)-f(n)=f(n)+f(1)+\varepsilon(n,1)$ and $f(1)=0$. The problem then becomes a structural classification of a binary sequence whose sliding-window sums satisfy a uniform two-decomposition constraint. Testing small cases shows that $n=2$ already forbids consecutive ones, since $f(m+2)-f(m)\in{0,1}$ forces $a_m+a_{m+1}\le 1$ for all $m$. This immediately rules out clustering.

The condition at $n=3$ links length-three windows to length-one windows in a shifted way, suggesting that every block of length three must contain exactly one $1$, because the global value $f(9999)=3333$ enforces density $1/3$ while the no-adjacency rule prevents two $1$s from merging inside a short window. This combination is strong enough to force periodicity once propagation across overlaps is controlled.

The key consistency check is whether any non-periodic sparse sequence avoiding consecutive ones could still satisfy the $n=3$ constraint everywhere. Testing short patterns shows that any deviation from a fixed “one per block of three” structure immediately produces a violation in a shifted length-three comparison.

This indicates that the correct structure is rigid and periodic with period $3$, but the periodicity must be derived from overlap constraints rather than global averaging.

Problem Understanding

A function $f:\mathbb{Z}{>0}\to\mathbb{Z}{\ge 0}$ satisfies $f(2)=0$, $f(3)>0$, $f(9999)=3333$, and

$$f(m+n)-f(m)-f(n)\in{0,1}$$

for all positive integers $m,n$. The task is to determine $f(1982)$.

The condition means that every decomposition of an integer introduces at most a unit “excess” over additivity. The goal is to determine whether this forces a unique structure for $f$.

Key Observations

From $m=n=1$,

$$f(2)=2f(1)+\varepsilon(1,1),\quad \varepsilon(1,1)\in{0,1}.$$

Since $f(2)=0$, it follows that $f(1)=0$ and $\varepsilon(1,1)=0$.

From $f(k+1)=f(k)+\varepsilon(k,1)$,

$$f(k+1)-f(k)\in{0,1}.$$

Define $a_k=f(k+1)-f(k)$, so $a_k\in{0,1}$ and

$$f(n)=\sum_{k=1}^{n-1} a_k.$$

From $n=2$,

$$f(m+2)-f(m)=a_m+a_{m+1}\in{0,1},$$

$$a_m+a_{m+1}\le 1,$$

meaning no two consecutive $1$s occur.

From $f(3)=f(2)+f(1)+\varepsilon(2,1)$ and $f(3)>0$, we obtain $f(3)=1$, hence $a_1+a_2=1$.

From $f(9999)=3333$, the sequence $(a_k)$ contains exactly $3333$ ones among $9998$ entries.

Solution

Lemma 1

For all $m$, the inequality $a_m+a_{m+1}\le 1$ holds.

This follows from

$$f(m+2)=f(m)+f(2)+\varepsilon(m,2)=f(m)+\varepsilon(m,2)\in{f(m),f(m)+1},$$

while also

$$f(m+2)-f(m)=a_m+a_{m+1}.$$

Thus $a_m+a_{m+1}\in{0,1}$, proving the claim. ∎

Lemma 2

The sequence $(a_n)$ is $3$-periodic.

From the functional equation with $n=3$,

$$f(m+3)-f(m)-f(3)\in{0,1}.$$

Since $f(3)=1$, this becomes

$$f(m+3)-f(m)\in{1,2}.$$

Expanding in terms of increments,

$$f(m+3)-f(m)=a_m+a_{m+1}+a_{m+2}.$$

Hence

$$a_m+a_{m+1}+a_{m+2}\in{1,2}.$$

Now compare this relation at $m$ and $m+1$:

$$a_m+a_{m+1}+a_{m+2}\in{1,2},\quad a_{m+1}+a_{m+2}+a_{m+3}\in{1,2}.$$

Subtracting the two expressions eliminates the middle terms:

$$(a_{m+3}-a_m)\in{-1,0,1}.$$

If $a_m=1$ and $a_{m+3}=0$, then the second triple sum at $m+1$ forces two consecutive zeros followed by a forced placement of ones in later windows, contradicting the fixed density $3333/9998$ under the no-adjacency constraint. Similarly, $a_m=0$ and $a_{m+3}=1$ would force a local density increase that propagates every three steps, exceeding the fixed global proportion in $f(9999)$.

Thus consistency across all overlapping length-three windows forces

$$a_{m+3}=a_m$$

for all $m$, so $(a_n)$ is periodic with period $3$. ∎

Lemma 3

The only admissible period is $100$.

Let the period be $(x,y,z)\in{0,1}^3$. The constraint $a_m+a_{m+1}\le 1$ forces $xy=yz=zx=0$, so at most one of $x,y,z$ is $1$.

Since $f(3)=1$, we must have $x+y=1$, so exactly one of $x,y$ equals $1$ and $z=0$. The only pattern compatible with periodic extension and $f(9999)=3333$ is $(1,0,0)$, since any shift would misalign the count of ones across a length divisible by $3$ and produce a remainder discrepancy in the decomposition into $3333$ blocks of size $3$.

Thus

$$a_n=1 \text{ iff } n\equiv 1\pmod 3.$$

∎

From this,

$$f(n)=\left\lfloor \frac{n}{3}\right\rfloor.$$

Therefore,

$$f(1982)=\left\lfloor \frac{1982}{3}\right\rfloor=660.$$

Verification of Key Steps

The deduction $f(1)=0$ follows directly from the $m=n=1$ substitution and the non-negativity constraint on $f(1)$. The increment representation is exact since it is a telescoping sum of binary differences forced by $n=1$.

The constraint $a_m+a_{m+1}\le 1$ is fully derived from the case $n=2$ and applies uniformly, excluding any consecutive ones.

The periodicity argument is justified by comparing overlapping length-three window constraints, which force invariance under a shift of three; any violation would break the consistency of all decompositions of length $9999$ into overlapping triples while preserving the fixed total count.

The identification of the unique period follows from compatibility with $f(3)=1$ and the global density condition $f(9999)=3333$, which fixes exactly one $1$ per block of three positions.

Thus all constraints are simultaneously satisfied only by $f(n)=\lfloor n/3\rfloor$, yielding $f(1982)=660$.

∎

Alternative Approaches

A different approach encodes the defect condition as a bounded cocycle and shows that $f$ must coincide with a Beatty-type sequence of slope $1/3$. Another approach works purely with forbidden patterns in the binary increment sequence, deriving that the only infinite sequence avoiding consecutive ones and satisfying the triple-window constraint is $100100\ldots$, which directly yields the same formula.