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

Since $\left\lfloor \frac{n}{r} \right\rfloor \le \frac{n}{r}$ ,

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

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

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

Since $r>1$ , then

$\frac{1}{2r} < \frac{1}{2}$

$\frac{1}{2r}+\frac{1}{2} < 1$

$\left( \frac{1}{2r}+\frac{1}{2} \right)n < n$

$n^2+\left( \frac{1}{2r}+\frac{1}{2} \right)n < n^2+n$

Therefore,

$\sum_{j=1}^n f_j(r) < n^2+n$ , which together with the equality case of $r=1$ proves the left side of the equation:

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

Now we look at $g_j(r)$ :

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

Therefore,

$g_j(r)=\begin{cases} n+\left\lceil \frac{j}{r} \right\rceil\; , & \left\lceil jr \right\rceil > n \\ \left\lceil jr \right\rceil+\left\lceil \frac{j}{r} \right\rceil\; , & \left\lceil jr \right\rceil \le n \end{cases}$

$\sum_{j=1}^n g_j(r)=\sum_{j=1}^{\left\lceil \frac{n}{r} \right\rceil}\left\lceil jr \right\rceil+\sum_{j=\left\lceil \frac{n}{r} \right\rceil +1}^{n}n+\sum_{j=1}^{n}\left\lceil \frac{j}{r} \right\rceil$

$\sum_{j=1}^n g_j(r) \ge \sum_{j=1}^{\left\lceil \frac{n}{r} \right\rceil} jr +\sum_{j=\left\lceil \frac{n}{r} \right\rceil +1}^{n}n+\sum_{j=1}^{n}\left\lceil \frac{j}{r} \right\rceil$

$\sum_{j=1}^n g_j(r) > \frac{r}{2}\left( \left\lceil \frac{n}{r} \right\rceil \right)\left( \left\lceil \frac{n}{r} \right\rceil+1 \right)+n\left( n- \left\lceil \frac{n}{r} \right\rceil\right)+\sum_{j=1}^{n}\left\lceil \frac{j}{r} \right\rceil$

Since $\left\lceil \frac{n}{r} \right\rceil \ge \frac{n}{r}$ ,

$\sum_{j=1}^n g_j(r) > \frac{r}{2}\left( \frac{n}{r} \right)\left( \frac{n}{r}+1 \right)+n\left( n- \frac{n}{r}\right)+\sum_{j=1}^{n}\left\lceil \frac{j}{r} \right\rceil$

When $r$ is a whole number and $n$ is divisible by $r$ we notice the following:

$\sum_{j=1}^{n}\left\lceil \frac{j}{r} \right\rceil=\frac{n(n+r)}{2r}$

Then $n$ is not divisible by $r$ then we add more ceiling terms to the expression. Likewise, when $r$ is not a whole number and $r>1$ , the sum is larger.

Therefore,

$\sum_{j=1}^{n}\left\lceil \frac{j}{r} \right\rceil \ge \frac{n(n+r)}{2r}$