Problem 1564

Solution:

We first prove the left hand side inequality. We begin by drawing an $n \times n$ board, with corners at $(0,0),(n, 0),(0, n)$ and $(n, n)$ on the Cartesian plane.
Consider the line $\ell$ with slope $r$ passing through $(0,0)$. For each $j \in\{1, \ldots, n\}$, consider the point $(j, \min (j r, n))$. Note that each such point either lies on $\ell$ or the top edge of the board. In the $j^{\text{th}}$ column from the left, draw the rectangle of height $\min (j r, n)$. Note that the sum of the $n$ rectangles is equal to the area of the board under the line $\ell$ plus $n$ triangles (possibly with area 0) each with width at most 1 and whose sum of the heights is at most $n$. Therefore, the sum of the areas of these $n$ triangles is at most $n / 2$. Therefore, $\sum_{j=1}^{n} \min (j r, n)$ is at most the area of the square under $\ell$ plus $n / 2$.

Consider the line with slope $1 / r$. By symmetry about the line $y=x$, the area of the square under the line with slope $1 / r$ is equal to the area of the square above the line $\ell$. Therefore, using the same reasoning as before, $\sum_{j=1}^{n} \min (j / r, n)$ is at most the area of the square above $\ell$ plus $n / 2$.

Therefore, $\sum_{j=1}^{n} f_{j}(r)=\sum_{j=1}^{n}\left(\min (j r, n)+\min \left(\frac{j}{r}, n\right)\right)$ is at most the area of the board plus $n$, which is $n^{2}+n$. This proves the left hand side inequality.

To prove the right hand side inequality, we will use the following lemma:

Lemma: Consider the line $\ell$ with slope $s$ passing through $(0,0)$. Then the number of squares on the board that contain an interior point below $\ell$ is $\sum_{j=1}^{n} \min (\lceil j s\rceil, n)$.

Proof of Lemma: For each $j \in\{1, \ldots, n\}$, we count the number of squares in the $j^{\text{th}}$ column (from the left) that contain an interior point lying below the line $\ell$. The line $x=j$ intersects the line $\ell$ at $(j, j s)$. Hence, since each column contains $n$ squares total, the number of such squares is $\min (\lceil j s\rceil, n)$. Summing over all $j \in\{1,2, \ldots, n\}$ proves the lemma. End Proof of Lemma

By the lemma, the rightmost expression of the inequality is equal to the number of squares containing an interior point below the line with slope $r$ plus the number of squares containing an interior point below the line with slope $1 / r$. By symmetry about the line $y=x$, the latter number is equal to the number of squares containing an interior point above the line with slope $r$. Therefore, the rightmost expression of the inequality is equal to the number of squares of the board plus the number of squares of which $\ell$ passes through the interior. The former is equal to $n^{2}$. Hence, to prove the inequality, it suffices to show that every line passes through the interior of at least $n$ squares. Since $\ell$ has positive slope, each $\ell$ passes through either $n$ rows and/or $n$ columns. In either case, $\ell$ passes through the interior of at least $n$ squares. Hence, the right inequality holds.

Solution:

We first prove the left inequality. Define the function $f(r)=\sum_{j=1}^{n} f_{j}(r)$. Note that $f(r)=f(1 / r)$ for all $r>0$. Therefore, we may assume that $r \geq 1$.

Let $m=\lfloor n / r\rfloor$, where $\lfloor x\rfloor$ denotes the largest integer less than or equal to $x$. Then $\min (j r, n)=j r$ for all $j \in\{1, \ldots, m\}$ and $\min (j r, n)=n$ for all $j \in\{m+1, \ldots, n\}$. Note that since $r \geq 1, \min (j / r, n) \leq n$ for all $j \in\{1, \ldots, n\}$. Therefore,
$$\begin{gathered} f(r)=\sum_{j=1}^{n} f_{j}(r)=(1+2+\ldots m) r+(n-m) n+(1+2+\ldots+n) \cdot \frac{1}{r} \\ =\frac{m(m+1)}{2} \cdot r+\frac{n(n+1)}{2} \cdot \frac{1}{r}+n(n-m) \end{gathered}$$
Then $f(r) \leq n^{2}+n$ if and only if
$$\frac{m(m+1) r}{2}+\frac{n(n+1)}{2 r} \leq n(m+1)$$
if and only if
$$m(m+1) r^{2}+n(n+1) \leq 2 r n(m+1)$$
Since $m=\lfloor n / r\rfloor$, there exists a real number $b$ satisfying $0 \leq b<r$ such that $n=m r+b$. Substituting this into the previous equation yields
$$m(m+1) r^{2}+(m r+b)(m r+b+1) \leq 2 r(m r+b)(m+1),$$
if and only if
$$2 m^{2} r^{2}+m r^{2}+(2 m b+m) r+b^{2}+b \leq 2 m^{2} r^{2}+2 m r^{2}+2 m b r+2 b r,$$
which simplifies to $m r+b^{2}+b \leq m r^{2}+2 b r \Leftrightarrow b(b+1-2 r) \leq m r(r-1)$. This is true since
$$b((b-r)+(1-r)) \leq m r(r-1).$$
This holds since $r \geq 1$ and $b<r$. Therefore, the left inequality holds.

We now prove the right inequality. Define the function $g(r)=\sum_{j=1}^{n} g_{j}(r)$. Note that $g(r)=g(1 / r)$ for all $r>0$. Therefore, we may assume that $r \geq 1$. We will consider two cases: $r \geq n$ and $1 \leq r<n$.

If $r \geq n$, then $\min (\lceil j r\rceil, n)=n$ and $\min (\lceil j / r\rceil, n)=1$ for all $j \in\{1, \ldots, n\}$. Hence, $g_{j}(r)=n+1$ for all $j \in\{1, \ldots, n\}$. Therefore, $g(r)=n(n+1)=n^{2}+n$, implying that the inequality is true.

Now we consider the case $1 \leq r<n$. Let $m=\lfloor n / r\rfloor$. Hence, $j r \leq n$ for all $j \in\{1, \ldots, m\}$, i.e. $\min (\lceil j r\rceil, n)=\lceil j r\rceil$ and $j r \geq n$ for all $j \in\{m+1, \ldots, n\}$, i.e. $\min (\lceil j r\rceil, n)=n$. Therefore,
$$\sum_{j=1}^{n} \min (\lceil j r\rceil, n)=\sum_{j=1}^{m}\lceil j r\rceil+(n-m) n$$
We will now consider the second sum $\sum_{j=1}^{n} \min \{\lceil j / r\rceil, n\}$.
Since $r \geq 1, \min (\lceil j / r\rceil, n) \leq \min (\lceil n / r\rceil, n) \leq n$. Therefore, $\min (\lceil j / r\rceil, n)=\lceil j / r\rceil$. Since $m=\lfloor n / r\rfloor,\lceil n / r\rceil \leq m+1$. Since $r>1, m<n$, which implies that $m+1 \leq n$. Therefore, $\min \{\lceil j / r\rceil, n\}=\lceil j / r\rceil \leq\lceil n / r\rceil \leq m+1$ for all $j \in\{1, \ldots, n\}$.

For each positive integer $k \in\{1, \ldots, m+1\}$, we now determine the number of positive integers $j \in\{1, \ldots, n\}$ such that $\lceil j / r\rceil=k$. We denote this number by $s_{k}$.

Note that $\lceil j / r\rceil=k$ if and only if $k-1<j / r \leq k$ if and only if $(k-1) r<j \leq \min (k r, n)$, since $j \leq n$. We will handle the cases $k \in\{1, \ldots, m\}$ and $k=m+1$ separately. If $k \in\{1, \ldots, m\}$, then $\min (k r, n)=k r$, since $r \leq m$ and $m=\lfloor n / r\rfloor$.

The set of positive integers $j$ satisfying $(k-1) r<j \leq k r$ is $\{\lfloor(k-1) r\rfloor+1,\ldots,\lfloor k r\rfloor\}$. Hence,
$$s_{k}=\lfloor r k\rfloor-\lfloor r(k-1)\rfloor$$
for all $k \in\{1, \ldots, m\}$. If $k=m+1$, then $(k-1) r<j \leq \min (k r, n)=n$. The set of positive integers $j$ satisfying $(k-1) r<j \leq k r$ is $\{\lfloor(k-1) r\rfloor+1, \ldots, n\}$. Then $s_{m+1}=n-\lfloor m r\rfloor$. Note that this number is non-negative by the definition of $m$. Therefore, by the definition of $s_{k}$, we have
$$\begin{aligned} & \sum_{j=1}^{n} \min \left(\left\lceil\frac{j}{r}\right\rceil, n\right)=\sum_{k=1}^{m+1} k s_{k} \\ & \quad=\sum_{k=1}^{m}(k(\lfloor k r\rfloor-\lfloor(k-1) r\rfloor))+(m+1)(n-\lfloor r m\rfloor)=(m+1) n-\sum_{k=1}^{m}\lfloor k r\rfloor . \end{aligned}$$
Summing the two expressions yields that
$$g(r)=n^{2}+n+\sum_{j=1}^{m}(\lceil j r\rceil-\lfloor j r\rfloor) \geq n^{2}+n$$
which proves the right inequality.