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$

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

~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