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

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}$

• Okay? What would you like from us? – Race Bannon Jul 24 '15 at 23:08
• Minimum is 0, let n=lcm of denominator – user175968 Jul 24 '15 at 23:14
• Maybe maximum=$m-1$, each rational=$\frac{1}{m}$ and $n=m-1$, not sure now. – user175968 Jul 24 '15 at 23:22
• Minimum is provably correct as (3) tells you $f(n) \ge 0$. As I understand the question, $r_1, r_2, \dots, r_m$ are chosen by an outside agency (we are not free to pick them), subject only to the constraints that they be be rational numbers in $(0,1)$ and of course equation (2). – Marconius Jul 24 '15 at 23:26
• @Marconius I got it. Just posted an answer. – user175968 Jul 25 '15 at 1:40

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^{'}$

• Nicely done! Point 2 is the real crux - for some reason this reminds me of that divisibility problem where a number leaves remainder 2 when divided by 3, 4 when divided by 5, etc., so just start with -1. – Marconius Jul 25 '15 at 2:02

$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$

• +1 Good answer. About the only thing missing is an assertion that $f(n)$ is an integer. Easy to see from equation (2), but worth remarking anyway. – Marconius Jul 25 '15 at 2:05
• @Marconius Thanks. – Justin Jul 25 '15 at 2:41