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 22: Line 22:
 
<math>f_j(1) =\min (j, n)+\min (j, n)=2j</math>
 
<math>f_j(1) =\min (j, n)+\min (j, n)=2j</math>
  
−
<math>\sum_{j=1}^n f_j(1)=2\sum_{j=1}^n j =n^2+n</math> and the equality holds.
+
<math>\sum_{j=1}^n f_j(1)=2\sum_{j=1}^n j =n^2+n</math>, and the equality holds.
  
 
Likewise,
 
Likewise,
Line 30: Line 30:
 
Since <math>j</math> is integer we have:
 
Since <math>j</math> is integer we have:
  
−
<math>\sum_{j=1}^n g_j(1)=2\sum_{j=1}^n \lceil j\rceil =2\sum_{j=1}^n j = n^2+n</math>
+
<math>\sum_{j=1}^n g_j(1)=2\sum_{j=1}^n \lceil j\rceil =2\sum_{j=1}^n j = n^2+n</math>, and the equality holds.
 +
 
 +
Thus for <math>r=1</math> we have equality as:
 +
 
 +
<math>\sum_{j=1}^n f_j(r) = n^2+n = \sum_{j=1}^n g_j(r)</math>
 +
 
 +
Case <math>r>1</math>:
 +
 
  
 
~Tomas Diaz. orders@tomasdiaz.com
 
~Tomas Diaz. orders@tomasdiaz.com
 
{{alternate solutions}}
 
{{alternate solutions}}

Revision as of 16:50, 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(r) = n^2+n = \sum_{j=1}^n g_j(r)$

Case $r>1$:


~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=206148"