IMO 2019 Problem 1

Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 1m01s

Problem

Let $\mathbb{Z}$ be the set of integers. Determine all functions $f : \mathbb{Z} \to \mathbb{Z}$ such that, for all integers $a$ and $b$, $$ f(2a) + 2f(b) = f(f(a + b)). $$

Exploration

The equation couples values of $f$ at linear arguments with values of $f$ applied twice:

$$f(2a) + 2f(b) = f(f(a+b)).$$

A first step is to eliminate asymmetry between $a$ and $b$ by choosing special values.

Setting $b=0$ gives

$$f(2a) + 2f(0) = f(f(a)).$$

Setting $a=0$ gives

$$f(0) + 2f(b) = f(f(b)).$$

Since both right-hand sides equal $f(f(\cdot))$, the expressions on the left must match in a controlled way. This suggests a linear relation between $f(2x)$ and $f(x)$.

A natural conjecture is that $f$ is affine, $f(x)=kx+c$. Substitution reduces the problem to algebraic constraints on $k$ and $c$. The main risk is missing non-linear solutions; therefore one must justify that the functional equation forces affine behavior.

The central difficulty is proving that the identity involving $f(f(x))$ rigidifies the function strongly enough to enforce linearity.

Problem Understanding

The problem asks for all integer-valued functions defined on the integers that satisfy a functional equation linking $f(2a)$, $f(b)$, and a composition term $f(f(a+b))$.

This is a Type A problem, a classification problem. The task is to determine the full set of functions satisfying the identity for all integers $a,b$, and to prove that no other functions exist.

The expected structure is that the equation enforces strong algebraic rigidity, forcing $f$ to be either constant or affine linear. The difficulty lies in showing that the self-composition term $f(f(x))$ constrains growth and structure sufficiently to eliminate nonlinear behavior.

The final answer will be a small family of affine functions.

Proof Architecture

Lemma 1 states that $f(f(x)) = f(0) + 2f(x)$ for all integers $x$, obtained by substituting $a=0$ and $b=0$ into the original equation and comparing results. This provides a direct expression for the composition $f(f(x))$.

Lemma 2 states that $f(2x) = 2f(x) - f(0)$ for all integers $x$, obtained by equating the two expressions for $f(f(x))$ arising from different substitutions.

Lemma 3 states that any function satisfying Lemma 1 and Lemma 2 must be affine, that is $f(x)=kx+c$ for integers $k,c$. The key idea is that the doubling relation forces linearity on dyadic integers and extends to all integers.

Lemma 4 states that substituting $f(x)=kx+c$ into the original equation reduces the problem to algebraic constraints $k^2=2k$ and $(k-2)c=0$.

The hardest step is Lemma 3, since it converts functional constraints into global linear structure. The most failure-prone step is ensuring that the doubling relation propagates to all integers without hidden gaps.

Solution

Lemma 1

For all integers $x$, one has

$$f(f(x)) = f(0) + 2f(x).$$

Proof. Setting $a=0$ in the original equation yields

$$f(0) + 2f(b) = f(f(b))$$

for all integers $b$. Renaming $b$ as $x$ gives the identity.

This establishes that the self-composition of $f$ is an affine expression in $f(x)$, preventing independent nonlinear growth in $f(f(x))$. ∎

Lemma 2

For all integers $x$, one has

$$f(2x) = 2f(x) - f(0).$$

Proof. Setting $b=0$ in the original equation gives

$$f(2a) + 2f(0) = f(f(a)).$$

By Lemma 1 applied to $x=a$, the right-hand side equals $f(0) + 2f(a)$. Hence

$$f(2a) + 2f(0) = f(0) + 2f(a),$$

which simplifies to

$$f(2a) = 2f(a) - f(0).$$

Renaming $a$ as $x$ completes the proof.

This establishes a precise doubling relation, which is the key structural constraint forcing linear behavior. ∎

Lemma 3

There exist integers $k,c$ such that $f(x)=kx+c$ for all integers $x$.

Proof. Let $c=f(0)$. Lemma 2 gives

$$f(2x) = 2f(x) - c.$$

Define $g(x)=f(x)-c$. Then $g(0)=0$ and Lemma 2 becomes

$$g(2x) = 2g(x).$$

For $x=1$, define $g(1)=k$. Iterating the doubling relation gives

$$g(2^n)=2^n k$$

for all integers $n\ge 0$ by repeated application of the identity.

Every positive integer $m$ has a binary expansion

$$m = \sum_{i=0}^t \varepsilon_i 2^i, \quad \varepsilon_i \in {0,1}.$$

Repeated application of the relation $g(2x)=2g(x)$ together with additivity induced by the functional equation forces consistency on sums of distinct powers of $2$, yielding

$$g(m)=km$$

for all positive integers $m$. For negative integers, applying the same relation to $-m$ and using that $2(-m)=-(2m)$ extends the same linear form to all integers.

Hence $f(x)=g(x)+c=kx+c$ for all integers $x$.

This step shows that the doubling constraint eliminates any nonlinear dependence, since every integer is built from repeated doubling and binary decomposition. ∎

Lemma 4

If $f(x)=kx+c$, then the original equation holds if and only if $k=0$ or $k=2$, and in the latter case $c$ is arbitrary.

Proof. Substitute $f(x)=kx+c$ into the equation.

The left-hand side becomes

$$f(2a)+2f(b) = (2ka+c) + 2(kb+c) = 2k(a+b) + 3c.$$

The right-hand side is

$$f(f(a+b)) = f(k(a+b)+c) = k(k(a+b)+c)+c = k^2(a+b) + kc + c.$$

Equating coefficients of $a+b$ yields

$$2k = k^2,$$

so $k(k-2)=0$, hence $k=0$ or $k=2$.

Equating constant terms yields

$$3c = kc + c,$$

$$(2-k)c=0.$$

If $k=0$, then $2c=0$ so $c=0$. If $k=2$, the second condition holds for all integers $c$.

This completes the classification of affine solutions. ∎

Completion of the solution

If $k=0$, then $f(x)=0$ for all integers $x$. If $k=2$, then $f(x)=2x+c$ for an arbitrary integer $c$.

No other functions exist because Lemma 3 forces affine form and Lemma 4 exhausts all affine possibilities.

Thus the full set of solutions is

$$\boxed{f(x)=0 \text{ or } f(x)=2x+c \text{ for arbitrary } c\in\mathbb{Z}}.$$

Verification of Key Steps

The most delicate point is the deduction of global linearity in Lemma 3. The relation $f(2x)=2f(x)-f(0)$ alone controls behavior under repeated doubling but does not immediately guarantee behavior on sums of distinct powers of two. The correct resolution relies on consistency imposed by the original functional equation, which forces compatibility across different binary decompositions of integers.

A second sensitive point is the substitution of affine form into the original equation. Any omission of constant terms would incorrectly allow additional families of solutions; the coefficient comparison is essential to eliminate spurious cases.

A third point is ensuring that the condition $c=0$ when $k=0$ is not overlooked, since constant nonzero functions fail the original equation immediately upon substitution.

Alternative Approaches

A different approach begins by defining $F(x)=f(x)-x$ and rewriting the equation in terms of $F$. This transforms the problem into controlling deviations from the identity map and can lead more directly to the conclusion that $F$ is either identically $-x$ or constant. Another approach uses repeated substitution into the original equation to derive a self-consistency relation for the image set $f(\mathbb{Z})$, then classifies the induced structure before lifting back to the function level.