3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Okay? What would you like from us? $\endgroup$ – Race Bannon Jul 24 '15 at 23:08
  • $\begingroup$ Minimum is 0, let n=lcm of denominator $\endgroup$ – user175968 Jul 24 '15 at 23:14
  • $\begingroup$ Maybe maximum=$m-1$, each rational=$\frac{1}{m}$ and $n=m-1$, not sure now. $\endgroup$ – user175968 Jul 24 '15 at 23:22
  • $\begingroup$ 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). $\endgroup$ – Marconius Jul 24 '15 at 23:26
  • $\begingroup$ @Marconius I got it. Just posted an answer. $\endgroup$ – user175968 Jul 25 '15 at 1:40
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Marconius Jul 25 '15 at 2:02
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ +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. $\endgroup$ – Marconius Jul 25 '15 at 2:05
  • $\begingroup$ @Marconius Thanks. $\endgroup$ – Justin Jul 25 '15 at 2:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.