Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2013 Canadian MO Problems/Problem 4"
Line 66: Line 66:
  
 
<math>\left( \frac{1}{2r}+\frac{1}{2} \right)n < n</math>
 
<math>\left( \frac{1}{2r}+\frac{1}{2} \right)n < n</math>
 +
 +
<math>n^2+\left( \frac{1}{2r}+\frac{1}{2} \right)n < n^2+n</math>
  
 
Therefore,
 
Therefore,
  
 +
<math>\sum_{j=1}^n f_j(r) < n^2+n</math>, which together with the equality case of <math>r=1</math> proves the left side of the equation:
  
 +
<math>\sum_{j=1}^n f_j(r) \le n^2+n</math>
  
  

Revision as of 17:15, 27 November 2023

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) < 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)<\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}{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$


~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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2013_Canadian_MO_Problems/Problem_4&oldid=206159"