56th International Mathematical Olympiad Shortlisted Problems

Throughout the solution, all functions are assumed to map integers to integers. For any function $g$ and any nonzero integer $t$, define $${\Delta }_{t}g(x)=g(x+t)-g(x)$$ For any nonzero integers $a$ and $b$, notice that ${\Delta }_a{\Delta }_{b}g={\Delta }_b{\Delta }_{a}g$. Moreover, if ${\Delta }_{a}g=0$ and ${\Delta }_{b}g=0$, then ${\Delta }_{a+b}g=0$ and ${\Delta }_{at}g=0$ for all nonzero integers $t$. We say that $g$ is $t$-quasiperiodic if ${\Delta }_{t}g$ is a constant function (in other words, if ${\Delta }_1{\Delta }_{t}g=0$, or ${\Delta }_{1}g$ is $t$-periodic). In this case, we call $t$ a quasi-period of $g$. We say that $g$ is quasi-periodic if it is $t$-quasi-periodic for some nonzero integer $t$. Notice that a quasi-period of $g$ is a period of ${\Delta }_{1}g$. So if $g$ is quasi-periodic, then its minimal positive quasi-period $t$ divides all its quasi-periods. We now assume that $f$ satisfies (1). First, by setting $a=x+y$, the problem condition can be rewritten as $$\begin{array}{c}{\Delta }_{f(x)}f(a)={\Delta }_{f(x)}f(2x-a-f(x))\text{ for all }x,a\in \mathbb{Z}\end{array}\text{\hspace{1em}(2)}$$ Let $b$ be an arbitrary integer and let $k$ be an arbitrary positive integer. Applying (2) when $a$ is substituted by $b,b+f(x),\dots ,b+(k-1)f(x)$ and summing up all these equations, we get $${\Delta }_{kf(x)}f(b)={\Delta }_{kf(x)}f(2x-b-kf(x))$$ Notice that a similar argument works when $k$ is negative, so that $$\begin{array}{c}{\Delta }_{M}f(b)={\Delta }_{M}f(2x-b-M)\text{ for any nonzero integer }M\text{ such that }f(x)\mid M.\end{array}\text{\hspace{1em}(3)}$$ We now prove two lemmas. Lemma 1. For any distinct integers $x$ and $y$, the function ${\Delta }_{\mathrm{lcm}(f(x),f(y))}f$ is $2(y-x)$-periodic. Proof. Denote $L=\mathrm{lcm}(f(x),f(y))$. Applying (3) twice, we obtain $${\Delta }_{L}f(b)={\Delta }_{L}f(2x-b-L)={\Delta }_{L}f(2y-(b+2(y-x))-L)={\Delta }_{L}f(b+2(y-x)).$$ Thus, the function ${\Delta }_{L}f$ is $2(y-x)$-periodic, as required. Lemma 2. Let $g$ be a function. If $t$ and $s$ are nonzero integers such that ${\Delta }_{ts}g=0$ and ${\Delta }_t{\Delta }_{t}g=0$, then ${\Delta }_{t}g=0$. Proof. Assume, without loss of generality, that $s$ is positive. Let $a$ be an arbitrary integer. Since ${\Delta }_t{\Delta }_{t}g=0$, we have $${\Delta }_{t}g(a)={\Delta }_{t}g(a+t)=\cdots ={\Delta }_{t}g(a+(s-1)t)$$ The sum of these $s$ equal numbers is ${\Delta }_{ts}g(a)=0$, so each of them is zero, as required. We now return to the solution. Step 1. We prove that $f$ is quasi-periodic. Let $Q=\mathrm{lcm}(f(0),f(1))$. Applying Lemma 1, we get that the function $g={\Delta }_{Q}f$ is 2-periodic. In other words, the values of $g$ are constant on even numbers and on odd numbers separately. Moreover, setting $M=Q$ and $x=b=0$ in (3), we get $g(0)=g(-Q)$. Since 0 and $-Q$ have different parities, the value of $g$ at even numbers is the same as that at odd numbers. Thus, $g$ is constant, which means that $Q$ is a quasi-period of $f$. Step 2. Denote the minimal positive quasi-period of $f$ by $T$. We prove that $T\mid f(x)$ for all integers $x$. Since an odd number $Q$ is a quasi-period of $f$, the number $T$ is also odd. Now suppose, to the contrary, that there exist an odd prime $p$, a positive integer $\alpha$, and an integer $u$ such that $p^{\alpha }\mid T$ but $p^{\alpha }\nmid f(u)$. Setting $x=u$ and $y=0$ in (1), we have $2f(u)=f(u+f(u))+f(u-f(u))$, so $p^{\alpha }$ does not divide the value of $f$ at one of the points $u+f(u)$ or $u-f(u)$. Denote this point by $v$. Let $L=\mathrm{lcm}(f(u),f(v))$. Since $|u-v|=f(u)$, from Lemma 1 we get ${\Delta }_{2f(u)}{\Delta }_{L}f=0$. Hence the function ${\Delta }_{L}f$ is $2f(u)$-periodic as well as $T$-periodic, so it is $\gcd (T,2f(u))$-periodic, or ${\Delta }_{\gcd (T,2f(u))}{\Delta }_{L}f=0$. Similarly, observe that the function ${\Delta }_{\gcd (T,2f(u))}f$ is $L$-periodic as well as $T$-periodic, so we may conclude that ${\Delta }_{\gcd (T,L)}{\Delta }_{\gcd (T,2f(u))}f=0$. Since $p^{\alpha }\nmid L$, both $\gcd (T,2f(u))$ and $\gcd (T,L)$ divide $T/p$. We thus obtain ${\Delta }_{T/p}{\Delta }_{T/p}f=0$, which yields $${\Delta }_{T/p}{\Delta }_{T/p}{\Delta }_{1}f=0$$ Since ${\Delta }_T{\Delta }_{1}f=0$, we can apply Lemma 2 to the function ${\Delta }_{1}f$, obtaining ${\Delta }_{T/p}{\Delta }_{1}f=0$. However, this means that $f$ is $(T/p)$-quasi-periodic, contradicting the minimality of $T$. Our claim is proved. Step 3. We describe all functions $f$. Let $d$ be the greatest common divisor of all values of $f$. Then $d$ is odd. By Step 2, $d$ is a quasi-period of $f$, so that ${\Delta }_{d}f$ is constant. Since the value of ${\Delta }_{d}f$ is even and divisible by $d$, we may denote this constant by $2dk$, where $k$ is an integer. Next, for all $i=0,1,\dots ,d-1$, define ${\ell }_i=f(i)/d$; notice that ${\ell }_i$ is odd. Then $$f(md+i)={\Delta }_{md}f(i)+f(i)=2kmd+{\ell }_{i}d\text{ for all }m\in \mathbb{Z}\text{ and }i=0,1,\dots ,d-1.$$ This shows that all functions satisfying (1) are listed in the answer. It remains to check that all such functions indeed satisfy (1). This is equivalent to checking (2), which is true because for every integer $x$, the value of $f(x)$ is divisible by $d$, so that ${\Delta }_{f(x)}f$ is constant.