International Mathematical Olympiad Shortlisted Problems

Answer. There are three kinds of such functions, which are: all constant functions, the floor function, and the ceiling function.

Solution 1. I. We start by verifying that these functions do indeed satisfy (1). This is clear for all constant functions. Now consider any triple $(x,a,b)\in \mathbb{Q}\times \mathbb{Z}\times {\mathbb{Z}}_{>0}$ and set $$q=\lfloor \frac{x+a}{b}\rfloor$$ This means that $q$ is an integer and $bq⩽x+a<b(q+1)$. It follows that $bq⩽\lfloor x\rfloor +a<b(q+1)$ holds as well, and thus we have $$\lfloor \frac{\lfloor x\rfloor +a}{b}\rfloor =\lfloor \frac{x+a}{b}\rfloor$$ meaning that the floor function does indeed satisfy (1). One can check similarly that the ceiling function has the same property.

II. Let us now suppose conversely that the function $f:\mathbb{Q}⟶\mathbb{Z}$ satisfies (1) for all $(x,a,b)\in \mathbb{Q}\times \mathbb{Z}\times {\mathbb{Z}}_{>0}$. According to the behaviour of the restriction of $f$ to the integers we distinguish two cases.

Case 1: There is some $m\in \mathbb{Z}$ such that $f(m)\ne m$. Write $f(m)=C$ and let $\eta \in \{-1,+1\}$ and $b$ denote the sign and absolute value of $f(m)-m$, respectively. Given any integer $r$, we may plug the triple ( $m,rb-C,b$ ) into ( 1 ), thus getting $f(r)=f(r-\eta )$. Starting with $m$ and using induction in both directions, we deduce from this that the equation $f(r)=C$ holds for all integers $r$. Now any rational number $y$ can be written in the form $y=\frac{p}{q}$ with $(p,q)\in \mathbb{Z}\times {\mathbb{Z}}_{>0}$, and substituting $(C-p,p-C,q)$ into (1) we get $f(y)=f(0)=C$. Thus $f$ is the constant function whose value is always $C$.

Case 2: One has $f(m)=m$ for all integers $m$. Note that now the special case $b=1$ of (1) takes a particularly simple form, namely $$\begin{array}{c}f(x)+a=f(x+a)\text{ for all }(x,a)\in \mathbb{Q}\times \mathbb{Z}\end{array}\text{\hspace{1em}(2)}$$ Defining $f\left(\frac{1}{2}\right)=\omega$ we proceed in three steps.

Step A. We show that $\omega \in \{0,1\}$. If $\omega ⩽0$, we may plug $\left(\frac{1}{2},-\omega ,1-2\omega \right)$ into (1), obtaining $0=f(0)=f\left(\frac{1}{2}\right)=\omega$. In the contrary case $\omega ⩾1$ we argue similarly using the triple $\left(\frac{1}{2},\omega -1,2\omega -1\right)$.

Step B. We show that $f(x)=\omega$ for all rational numbers $x$ with $0<x<1$. Assume that this fails and pick some rational number $\frac{a}{b}\in (0,1)$ with minimal $b$ such that $f\left(\frac{a}{b}\right)\ne \omega$. Obviously, $\gcd (a,b)=1$ and $b⩾2$. If $b$ is even, then $a$ has to be odd and we can substitute $\left(\frac{1}{2},\frac{a-1}{2},\frac{b}{2}\right)$ into (1), which yields $$\begin{array}{c}f\left(\frac{\omega +(a-1)/2}{b/2}\right)=f\left(\frac{a}{b}\right)\ne \omega \end{array}\text{\hspace{1em}(3)}$$ Recall that $0⩽(a-1)/2<b/2$. Thus, in both cases $\omega =0$ and $\omega =1$, the left-hand part of (3) equals $\omega$ either by the minimality of $b$, or by $f(\omega )=\omega$. A contradiction.

Thus $b$ has to be odd, so $b=2k+1$ for some $k⩾1$. Applying (1) to $\left(\frac{1}{2},k,b\right)$ we get $$\begin{array}{c}f\left(\frac{\omega +k}{b}\right)=f\left(\frac{1}{2}\right)=\omega \end{array}\text{\hspace{1em}(4)}$$ Since $a$ and $b$ are coprime, there exist integers $r\in \{1,2,\dots ,b\}$ and $m$ such that $ra-mb=k+\omega$. Note that we actually have $1⩽r<b$, since the right hand side is not a multiple of $b$. If $m$ is negative, then we have $ra-mb>b⩾k+\omega$, which is absurd. Similarly, $m⩾r$ leads to $ra-mb<br-br=0$, which is likewise impossible; so we must have $0⩽m⩽r-1$.

We finally substitute $\left(\frac{k+\omega }{b},m,r\right)$ into (1) and use (4) to learn $$f\left(\frac{\omega +m}{r}\right)=f\left(\frac{a}{b}\right)\ne \omega$$ But as above one may see that the left hand side has to equal $\omega$ due to the minimality of $b$. This contradiction concludes our step B.

Step $C$. Now notice that if $\omega =0$, then $f(x)=\lfloor x\rfloor$ holds for all rational $x$ with $0⩽x<1$ and hence by (2) this even holds for all rational numbers $x$. Similarly, if $\omega =1$, then $f(x)=\lceil x\rceil$ holds for all $x\in \mathbb{Q}$. Thereby the problem is solved.

Comment 1. An alternative treatment of Steps B and C from the second case, due to the proposer, proceeds as follows. Let square brackets indicate the floor function in case $\omega =0$ and the ceiling function if $\omega =1$. We are to prove that $f(x)=[x]$ holds for all $x\in \mathbb{Q}$, and because of Step A and (2) we already know this in case $2x\in \mathbb{Z}$. Applying (1) to ( $2x,0,2$ ) we get $$f(x)=f\left(\frac{f(2x)}{2}\right)$$ and by the previous observation this yields $$\begin{array}{c}f(x)=\left[\frac{f(2x)}{2}\right]\text{ for all }x\in \mathbb{Q}\end{array}\text{\hspace{1em}(5)}$$ An easy induction now shows $$\begin{array}{c}f(x)=\left[\frac{f\left(2^{n}x\right)}{2^n}\right]\text{ for all }(x,n)\in \mathbb{Q}\times {\mathbb{Z}}_{>0}\end{array}\text{\hspace{1em}(6)}$$ Now suppose first that $x$ is not an integer but can be written in the form $\frac{p}{q}$ with $p\in \mathbb{Z}$ and $q\in {\mathbb{Z}}_{>0}$ both being odd. Let $d$ denote the multiplicative order of 2 modulo $q$ and let $m$ be any large integer. Plugging $n=dm$ into (6) and using (2) we get $$f(x)=\left[\frac{f\left(2^{dm}x\right)}{2^{dm}}\right]=\left[\frac{f(x)+\left(2^{dm}-1\right)x}{2^{dm}}\right]=\left[x+\frac{f(x)-x}{2^{dm}}\right]$$ Since $x$ is not an integer, the square bracket function is continuous at $x$; hence as $m$ tends to infinity the above fomula gives $f(x)=[x]$. To complete the argument we just need to observe that if some $y\in \mathbb{Q}$ satisfies $f(y)=[y]$, then (5) yields $f\left(\frac{y}{2}\right)=f\left(\frac{[y]}{2}\right)=\left[\frac{[y]}{2}\right]=\left[\frac{y}{2}\right]$.

---

Alternative solution.

Here we just give another argument for the second case of the above solution. Again we use equation (2). It follows that the set $S$ of all zeros of $f$ contains for each $x\in \mathbb{Q}$ exactly one term from the infinite sequence $\dots ,x-2,x-1,x,x+1,x+2,\dots$.

Next we claim that $$\begin{array}{c}\text{ if }(p,q)\in \mathbb{Z}\times {\mathbb{Z}}_{>0}\text{ and }\frac{p}{q}\in S,\text{ then }\frac{p}{q+1}\in S\text{ holds as well. }\end{array}\text{\hspace{1em}(7)}$$ To see this we just plug $\left(\frac{p}{q},p,q+1\right)$ into (1), thus getting $f\left(\frac{p}{q+1}\right)=f\left(\frac{p}{q}\right)=0$.

From this we get that $$\begin{array}{c}\text{ if }x,y\in \mathbb{Q},x>y>0,\text{ and }x\in S,\text{ then }y\in S.\end{array}\text{\hspace{1em}(8)}$$ Indeed, if we write $x=\frac{p}{q}$ and $y=\frac{r}{s}$ with $p,q,r,s\in {\mathbb{Z}}_{>0}$, then $ps>qr$ and (7) tells us $$0=f\left(\frac{p}{q}\right)=f\left(\frac{pr}{qr}\right)=f\left(\frac{pr}{qr+1}\right)=\dots =f\left(\frac{pr}{ps}\right)=f\left(\frac{r}{s}\right).$$ Essentially the same argument also establishes that $$\begin{array}{c}\text{ if }x,y\in \mathbb{Q},x<y<0,\text{ and }x\in S,\text{ then }y\in S.\end{array}\text{\hspace{1em}(9)}$$ From (8) and (9) we get $0\in S\subseteq (-1,+1)$ and hence the real number $\alpha =\sup (S)$ exists and satisfies $0⩽\alpha ⩽1$.

Let us assume that we actually had $0<\alpha <1$. Note that $f(x)=0$ if $x\in (0,\alpha )\cap \mathbb{Q}$ by (8), and $f(x)=1$ if $x\in (\alpha ,1)\cap \mathbb{Q}$ by (9) and (2). Let $K$ denote the unique positive integer satisfying $K\alpha <1⩽(K+1)\alpha$. The first of these two inequalities entails $\alpha <\frac{1+\alpha }{K+1}$, and thus there is a rational number $x\in \left(\alpha ,\frac{1+\alpha }{K+1}\right)$. Setting $y=(K+1)x-1$ and substituting $(y,1,K+1)$ into ( 1 ) we learn $$f\left(\frac{f(y)+1}{K+1}\right)=f\left(\frac{y+1}{K+1}\right)=f(x).$$ Since $\alpha <x<1$ and $0<y<\alpha$, this simplifies to $$f\left(\frac{1}{K+1}\right)=1$$ But, as $0<\frac{1}{K+1}⩽\alpha$, this is only possible if $\alpha =\frac{1}{K+1}$ and $f(\alpha )=1$. From this, however, we get the contradiction $$0=f\left(\frac{1}{(K+1{)}^2}\right)=f\left(\frac{\alpha +0}{K+1}\right)=f\left(\frac{f(\alpha )+0}{K+1}\right)=f(\alpha )=1.$$ Thus our assumption $0<\alpha <1$ has turned out to be wrong and it follows that $\alpha \in \{0,1\}$. If $\alpha =0$, then we have $S\subseteq (-1,0]$, whence $S=(-1,0]\cap \mathbb{Q}$, which in turn yields $f(x)=\lceil x\rceil$ for all $x\in \mathbb{Q}$ due to (2). Similarly, $\alpha =1$ entails $S=[0,1)\cap \mathbb{Q}$ and $f(x)=\lfloor x\rfloor$ for all $x\in \mathbb{Q}$. Thereby the solution is complete.