IMO 2019 Shortlisted Problems

a) Let $f$ be the function where $f(0)=0$ and $f(x)$ is the largest power of $2$ dividing $2x$ for $x\ne 0$. The integer $0$ is evidently $f$-rare, so it remains to verify the functional equation.

Since $f(2x)=2f(x)$ for all $x$, it suffices to verify the functional equation when at least one of $x$ and $y$ is odd (the case $x=y=0$ being trivial). If $y$ is odd, then we have $$f(f(x+y)+y)=2=f(f(x)+y)$$ since all the values attained by $f$ are even. If, on the other hand, $x$ is odd and $y$ is even, then we already have $$f(x+y)=2=f(x)$$ from which the functional equation follows immediately.

b) An easy inductive argument (substituting $x+ky$ for $x$) shows that $$f(f(x+ky)+y)=f(f(x)+y)$$ for all integers $x$, $y$ and $k$. If $v$ is an $f$-rare integer and $a$ is the least element of $X_v$, then by substituting $y=a-f(x)$ in the above, we see that $$f(x+k\cdot (a-f(x)))-f(x)+a\in X_v$$ for all integers $x$ and $k$, so that in particular $$f(x+k\cdot (a-f(x)))⩾f(x)$$ for all integers $x$ and $k$, by assumption on $a$. This says that on the (possibly degenerate) arithmetic progression through $x$ with common difference $a-f(x)$, the function $f$ attains its minimal value at $x$.

Repeating the same argument with $a$ replaced by the greatest element $b$ of $X_v$ shows that $$f(x+k\cdot (b-f(x)))⩽f(x)$$ for all integers $x$ and $k$. Combined with the above inequality, we therefore have $$f(x+k\cdot (a-f(x))\cdot (b-f(x)))=f(x)$$ for all integers $x$ and $k$.

Thus if $f(x)\ne a,b$, then the set $X_{f(x)}$ contains a nondegenerate arithmetic progression, so is infinite. So the only possible $f$-rare integers are $a$ and $b$.

In particular, the $f$-rare integer $v$ we started with must be one of $a$ or $b$, so that $f(v)=f(a)=f(b)=v$. This means that there cannot be any other $f$-rare integers $v^{\prime }$, as they would on the one hand have to be either $a$ or $b$, and on the other would have to satisfy $f(v^{\prime })=v^{\prime }$. Thus $v$ is the unique $f$-rare integer.

---

Alternative solution.

Part (b) only. Suppose $v$ is $f$-rare, and let $a$ and $b$ be the least and greatest elements of $X_v$, respectively. Substituting $x=v$ and $y=a-v$ into the equation shows that $$f(v)-v+a\in X_v$$ and in particular $f(v)⩾v$. Repeating the same argument with $x=v$ and $y=b-v$ shows that $f(v)⩽v$, and hence $f(v)=v$.

Suppose now that $v^{\prime }$ is a second $f$-rare integer. We may assume that $v=0$ (see Comment 1). We've seen that $f(v^{\prime })=v^{\prime }$; we claim that in fact $f(k{v}^{\prime })=v^{\prime }$ for all positive integers $k$. This gives a contradiction unless $v^{\prime }=v=0$.

This claim is proved by induction on $k$. Supposing it to be true for $k$, we substitute $y=k{v}^{\prime }$ and $x=0$ into the functional equation to yield $$f((k+1)v^{\prime })=f(f(0)+k{v}^{\prime })=f(k{v}^{\prime })=v^{\prime }$$ using that $f(0)=0$. This completes the induction, and hence the proof.