2013 Canadian MO Problems/Problem 4

Problem

Let $n$ be a positive integer. For any positive integer $j$ and positive real number $r$ , define $f_j(r) =\min (jr, n)+\min\left(\frac{j}{r}, n\right),\text{ and }g_j(r) =\min (\lceil jr\rceil, n)+\min\left(\left\lceil\frac{j}{r}\right\rceil, n\right),$ where $\lceil x\rceil$ denotes the smallest integer greater than or equal to $x$ . Prove that $\sum_{j=1}^n f_j(r)\leq n^2+n\leq \sum_{j=1}^n g_j(r)$ for all positive real numbers $r$ .

Solution

First thing to note on both functions is the following:

$f_j\left(\frac{1}{r}\right) =\min\left(\frac{j}{r}, n\right)+\min (jr, n)=f_j(r)$

and $g_j \left( \frac{1}{r} \right) =\min\left(\left\lceil\frac{j}{r}\right\rceil, n\right)+\min (\lceil jr\rceil, n)=g_j(r)$

Thus, we are going to look at two cases:\. When $r=1$ , and when $r>1$ which is the same as when $0<r<1$

Case 1: $r=1$

Since $j \le n$ in the sum, then

$f_j(1) =\min (j, n)+\min (j, n)=2j$

$\sum_{j=1}^n f_j(1)=2\sum_{j=1}^n j =n^2+n$ , and the equality holds.

Likewise,

$g_j(1) =\min (\lceil j\rceil, n)+\min (\lceil j\rceil, n)=2\lceil j\rceil$

Since $j$ is integer we have:

$\sum_{j=1}^n g_j(1)=2\sum_{j=1}^n \lceil j\rceil =2\sum_{j=1}^n j = n^2+n$ , and the equality holds.

Thus for $r=1$ we have equality as:

$\sum_{j=1}^n f_j(1) = n^2+n = \sum_{j=1}^n g_j(1)$

Case: $r>1$

Since $j \le n$ , then $\min\left(\frac{j}{r}, n\right)=\frac{j}{r}$

Therefore,

$f_j(r)=\begin{cases} n+\frac{j}{r}\; , & j > \frac{n}{r} \\ jr+\frac{j}{r}\; , & j \le \frac{n}{r}\end{cases}$

$\sum_{j=1}^n f_j(r)=r\sum_{j=1}^{\left\lfloor \frac{n}{r} \right\rfloor}j+\sum_{j=\left\lfloor \frac{n}{r} \right\rfloor +1}^{n}n+\frac{1}{r}\sum_{j=1}^{n}j$

$\sum_{j=1}^n f_j(r)=\frac{r \left\lfloor \frac{n}{r} \right\rfloor \left( \left\lfloor \frac{n}{r} \right\rfloor+1 \right)}{2}+\left( n-\left\lfloor \frac{n}{r} \right\rfloor \right)r +\frac{n^2+n}{2r}$

~Tomas Diaz. orders@tomasdiaz.com Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Page

Toolbox

Search

2013 Canadian MO Problems/Problem 4

Problem

Solution