Olympiad question involving divisibility and floor function

Question

I am having difficulty with this Olympiad question:

Let $r \geq 1$ be a real number such that whenever $m$ divides $n$ (for any positive integers $m$ and $n$), it is also true that $\left \lfloor mr \right \rfloor$ divides $\left \lfloor nr \right \rfloor$. Show that $r$ is an integer.

Had no idea where to begin as it mixes the floor function with divisibility.

Answer 1

Let $\{x\}$ denote fractional part, i.e. $x = \lfloor x\rfloor + \{x\}$.

Observation 1: When $x$ is doubled, either the integer and fractional part both double, or if this would cause the fractional part to reach or exceed 1, then 1 "rolls over" from the fractional part to the integer part. In other words: If $\{x\} < \frac 12$, then $\lfloor 2x\rfloor = 2\lfloor x\rfloor$ and $\{2x\} = 2\{x\}$; if $\{x\}\ge\frac 12$, then $\lfloor 2x\rfloor = 2\lfloor x\rfloor + 1$ and $\{2x\} = 2\{x\}-1$.

Observation 2: If $k>1$ is an integer, then $k$ does not divide $2k+1$.

Now we argue by contradiction. Suppose $r$ is not an integer, and choose an integer $a$ such that $ar>2$ and $ar$ is not an integer. Consider the sequence $ar,2ar,4ar,8ar,\ldots,2^nar,\ldots$. If the fractional part of any term in this sequence is $\ge\frac 12$, then Observations 1 and 2 give a contradiction. If not, then the fractional parts double forever, but this is not possible because $ar$ has positive fractional part and yet all fractional parts must be smaller than 1. Thus we are finished.

Answer 2

As with any problem you don't immediately know how to solve, you can start by looking at concrete examples to get a feel for what's going on. Consider some particular non-integer $r$ (say $r=2.5$) and try to find (by guess-and-check) a counterexample to the divisibility property, i.e. a pair $(m,n)$ such that $m\mid n$ but $\lfloor mr\rfloor\nmid\lfloor nr\rfloor$. Can you generalize this into a procedure for finding a counterexample for any non-integer $r$? If so (and you can justify that it works), then you're done.

Answer 3

I would approach this problem using what saulspatz suggested in the comment.

Here is a skeleton of the proof (by contradiction). Let $r = p + t$ where $p \in \mathbb{Z}$, $t \in \mathbb{R}$, and $0<t<1$. Since $m\mid n$, we write $n = am$ where $a$ can be any integer. Similarly, since we also have $\lfloor mr \rfloor \mid \lfloor nr \rfloor$, we write $b\lfloor mr \rfloor = \lfloor nr \rfloor$ where $b$ can be any integer. Combining the two equations, we have $$b\lfloor mp+mt \rfloor = bmp + b\lfloor mt \rfloor = \lfloor np + nt\rfloor = \lfloor amp + amt \rfloor = amp + \lfloor amt \rfloor.$$ In other words, $bmp + b\lfloor mt \rfloor = amp + \lfloor amt \rfloor$. Rearranging the terms, we have $$(b-a)mp = \lfloor amt\rfloor - b\lfloor mt\rfloor.$$ Note that the LHS is an integer and is divisible by $m$. This means that $$\lfloor amt \rfloor - b \lfloor mt \rfloor \equiv 0 \pmod m,$$ or $$\lfloor amt \rfloor \pmod m \equiv b\lfloor mt \rfloor\pmod m.$$ Also note that since $0 < t <1$, $0 < mt < m$, which also means that $0 < \lfloor mt \rfloor \leq m-1$. Since we can make $m$ arbitrarily large, we know that for any $t$, we can find some large $m$ such that $mt > 1$. This means that for some large $m$, $1 \leq \lfloor mt \rfloor \leq m-1$, i.e. $\lfloor mt \rfloor \not \equiv 0 \pmod m$.

Now we just need to find some $a,b$ such that $\lfloor amt \rfloor \not \equiv b \lfloor mt \rfloor \pmod m$ to complete the contradiction. Since $a, b$ can be literally any integers, cherry-picking some examples would produce the contradiction.