Maximum and minimum of a sum involving floor functions of rational numbers (contest question)

Question

This question originates from the 1996 Canada National Olympiad.

Let $r_1, r_2, \dots, r_m$ be a given set of $m$ positive rational numbers such that

$\sum\limits^{m}_{k=1}{r_k} = 1 \tag{1}$

Define the function $f$ by

$f(n) = n − \sum\limits^{m}_{k=1}{\lfloor{r_k n}\rfloor} \tag{2}$

for each positive integer $n$, where $\lfloor{x}\rfloor$ denotes the greatest integer less than or equal to x.

Determine the minimum and maximum values of $f(n)$.

---

The floor of a real number can be expressed in terms of the fractional part:

$\lfloor{x}\rfloor = x - \{x\}$

so we can use (1) to re-express (2) as

$f(n) = n - \sum\limits^{m}_{k=1}{(r_k n - \{r_k n\}}) = n - n\sum\limits^{m}_{k=1}{r_k} + \sum\limits^{m}_{k=1}{\{r_k n\}}$ so $f(n) = \sum\limits^{m}_{k=1}{\{r_k n\}} \tag{3}$

Since $r_i \in \mathbb{Q^+}$ we may write for each $i$:

$r_i = \dfrac{p_i}{q_i}\text{ with }0 < p_i \le q_i; p_i,q_i \in \mathbb{Z^+} \tag{4}$

Answer 1

The minimum is $0$ when $n=$ common multiplier of $q_i$ in OP's notation.

The maximum is $m-1$, to achieve the result, we need to prove

1. $f(n)<m$

2. For any set of $r_i$ exist $n$ such that $f(n)=m-1$

3. $f(n)$ is always integer

Prove of 1. is obvious because {x}<1 .

For 2., first make all the given rational numbers common denominator $\frac{p_1'}{q}$, $\frac{p_2'}{q}$, …, $\frac{p_m'}{q}$, let $n=q-1$, $\{\frac{p_1'(q-1)}{q}\}+…\{\frac{p_m'(q-1)}{q}\}$=$\{\frac{-p_1'}{q}\}+…\{\frac{-p_m'}{q}\}=m-1$, last equality comes from $\{-x\}=1-\{x\}$.

For 3., notice $\{\frac{np_i'}{q}\}=\frac{np_i'-n_i^{'}q}{q}$ for some integer $n_i^{'}$

Answer 2

$f(n)=\sum_{k=1}^{m}(r_k n - \lfloor {r_k n}\rfloor)$

$\lfloor {r_k n}\rfloor \leq r_k n$

So, $f(n) \geq 0$

$r_k n - \lfloor {r_k n}\rfloor <1 $

$f(n) < \sum_{k=1}^{m}1$

So, $f(n) < m$

$r_k = p_k / q_k$ where $p_k < q_k$

If $n = q_1.q_2.....q_m - 1$

Then $n= (q_1.q_2.....q_m-q_k)+(q_k-1)$

So,

$r_k n - \lfloor {r_k n}\rfloor = p_k/q_k (q_k-1)- \lfloor {p_k/q_k(q_k-1)}\rfloor $

$= 1-p_k/q_k$

So, $max(f(n)) = \sum_{k=1}^{m}(1-r_k)$ $= m-1$