Merp, I inducted on $n$ starting from the case $m=n$ and using $\text{min}(a,b)=\frac{a+b-|a-b|}{2}$.

OMG there is a combinatorial bijection for this.

Both sides count the ordered pairs $(a,b)$ of integers where $1\leq a\leq m$ and $1\leq b\leq n$ and $ab\leq x$, the first by casework on $b$ and the second in $a$.

DrMath wrote: Merp, I inducted on $n$ starting from the case $m=n$ and using $\text{min}(a,b)=\frac{a+b-|a-b|}{2}$. Can you post your solution using that ? Thank you.

I solved this using lattice points. It wasn't as elegant as the official solution but it was very similar to the official solution.

Let $|x|$ denote $x$ if it's positive and $0$ otherwise. It clearly is equivalent to proving $ \sum_{i=1}^n |m - \lfloor x/i \rfloor| = \sum_{i=1}^m |n - \lfloor x/i \rfloor| $, but the above equation counts the number of ordered pairs $(a,b)$ where $ 1 \le a \le m, 1 \le b \le n$ and $ab>x$! So we're done.

Whoever notices the multiplication table during clearly has a lot of time to spare... If you plan to finish the test then you better have the first 2 cleared within the first hour.

I broke that into cases......and inducted on $m+n$.............

I wonder why ELMO #1 is A1 and ELMO #2 is N1...

WLOG suppose that $m \le n.$ Then fix $m, x$, and we will show that the result holds for all $n \ge m$ by induction on $n.$ The base case, $n = m$ trivially holds by symmetry. For the inductive step, assume that the claim holds for $n$, and we will prove the claim true for $n + 1.$ Note that $\min\left(\left\lfloor \frac{x}{i} \right\rfloor, n + 1\right) = \min\left(\left\lfloor \frac{x}{i} \right\rfloor, n\right) + 1$ whenever $\left\lfloor \frac{x}{i} \right\rfloor \ge n + 1$ and $\min\left(\left\lfloor \frac{x}{i} \right\rfloor, n + 1\right) = \min\left(\left\lfloor \frac{x}{i} \right\rfloor, n\right)$ otherwise. But observe that $\left\lfloor \frac{x}{i} \right\rfloor \ge n + 1$ for $i = 1, 2, \cdots , \left\lfloor \frac{x}{n + 1}\right\rfloor$ because \[\left\lfloor \frac{x}{i} \right\rfloor \ge n + 1 \iff \frac{x}{i} \ge n + 1 \iff \frac{x}{n + 1} \ge i.\] Therefore, since the summation $\sum_{i = 1}^m \min\left(\left\lfloor \frac{x}{i} \right\rfloor, n + 1\right)$ contains $m$ terms, it follows from the inductive hypothesis that \begin{align*} \sum_{i = 1}^m \min\left(\left\lfloor \frac{x}{i} \right\rfloor, n + 1\right) &= \sum_{i = 1}^m \min\left(\left\lfloor \frac{x}{i} \right\rfloor, n\right) + \min\left(\left\lfloor \frac{x}{n + 1} \right\rfloor, m\right) \\ &= \sum_{i = 1}^n \min\left(\left\lfloor \frac{x}{i} \right\rfloor, m\right) + \min\left(\left\lfloor \frac{x}{n + 1} \right\rfloor, m\right) \\ &= \sum_{i = 1}^{n + 1} \min\left(\left\lfloor \frac{x}{i} \right\rfloor, m\right), \end{align*}which completes the induction. $\square$

I prove that pair (n, n+1) is true for the question. It seems to be done

Consider making a grid of dots as follows: In row $i$ of the table, draw $\lfloor x/i \rfloor$ dots horizontally, for all $1\le i \le x$. Firstly, we claim that the number of dots in column $k$ is the same as the number of dots in row $k$ for all $1\le k\le x$. The number of dots in row $k$ is $\lfloor x/k \rfloor$ by definition. On the other hand, a dot is in column $k$ and row $j$ if and only if row $j$ has at least $k$ dots in it. Hence, $\lfloor x/j \rfloor \ge k$, so $jk\le x$. The number of such $j$ is $\lfloor x/k \rfloor$, so this is the number of dots in column $k$. This proves our claim. We claim that $\sum_{i = 1}^n \min\left(\left\lfloor \frac{x}{i} \right\rfloor, m \right)$ is the number of dots in the grid which are in the first $n$ rows and in the first $m$ columns. If we wanted to just find $\sum_{i = 1}^n \left\lfloor \frac{x}{i} \right \rfloor$, then we would take the number of dots in the first $n$ rows, since this sum is counting precisely the number of dots in the first $n$ rows. Because of the $\min\left(\left\lfloor \frac{x}{i} \right\rfloor, m \right)$ condition, we have to just take the dots in the first $n$ rows that are also in the first $m$ columns. In essence, we are ``cutting'' the original grid to only include the first $m$ columns and first $n$ rows. Now, we know by our first claim that this is equivalent to cutting the original grid to only include the first $n$ columns and first $m$ rows. Using the same argument as before, we know this is $\sum_{i = 1}^m \min\left(\left\lfloor \frac{x}{i} \right\rfloor, n \right)$, and we are done.

We will utilize a double counting argument. Consider the following grid of numbers: \[ \begin{matrix} 1 & 2 & 3 & \cdots & m \\ 2 &4 & 6 & \cdots & 2m \\ 3 & 6 & 9 & \cdots & 3m \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ n & 2n & 3n & \cdots & mn \end{matrix} \]The left side counts the number of integers less than or equal to $x$ by columns. The right side counts the number of integers less than or equal to $x$ by rows.

hELp why is everything so tall also this is combo? Notice that \[ \sum_{i = 1}^n \min\left(\left\lfloor \frac{x}{i} \right\rfloor, m \right) = \sum_{i=1}^n \sum_{\stackrel{i|k}{k \le x, \ mi}} 1 = \sum_{k=1}^x \sum_{\stackrel{i|k}{\tfrac{k}{m} \le i \le n}} 1. \]Hence it suffices to show that $\displaystyle{\sum_{\stackrel{i|k}{\tfrac{k}{m} \le i \le n}} 1 = \sum_{\stackrel{i|k}{\tfrac{k}{n} \le i \le m}} 1}$. But this comes from swapping $i \longleftrightarrow \tfrac{k}{i}$. $\blacksquare$

Without loss of generality, suppose $n \geq m.$ We now prove the following: if there are $k$ terms in the summation $\sum_{i=1}^n \min(\lfloor \frac{x}{i} \rfloor, m) \geq j$ for $1 \leq i \leq k$ and at $i = k$ we have $\min(\lfloor \frac{x}{i} \rfloor, m) = j$, then there are $j$ terms in the second summation $\sum_{i=1}^m \min(\lfloor \frac{x}{i} \rfloor, n) \geq k$ with $1 \leq i \leq j$ and at $i = j,$ we have $\min(\lfloor \frac{x}{i} \rfloor, n) = k$. Proof: Because at $i = k$ we have $\min(\lfloor \frac{x}{i} \rfloor, m) = j,$ we have $kj \leq x < k(j+1)$ so $\min(\lfloor \frac{x}{j} \rfloor, n) = k.$ As $i$ decreases, so does the $\min(\lfloor \frac{x}{i} \rfloor, n).$ Also, $j \leq m \leq n$ so we are allowed to do this. By using our above lemma, we can biject each term of the summation $\sum_{i=1}^n \min(\rfloor \frac{x}{i} \lfloor , m)$ to $p$ terms in the summation $\sum_{i=1}^m \min(\rfloor \frac{x}{i} \lfloor, n)$ for some values(including multiplicity) of $p$ $1 \leq p \leq n,$ so these two summations are equal.

as the wise chdenmathcountz once said, induct to winduct. We proceed with induction. The base case, $m=n=1$ is trivial. For the inductive step, we aim to prove that if $(m,n)$ works, then $(m,n+1)$ also does, which finishes the problem because we can symmetrically apply the hypothesis on $(m+1,n)$. If $x>m(n+1)$ we are done. Otherwise, notice that LHS increases by $\lfloor\frac{x}{n+1}\rfloor$; this is exactly the amount of $i$'s on RHS such that $\lfloor\frac{x}{i}\rfloor>n+1$, and each such $i$ would increase the RHS by 1, finishing the problem.

Solution. Fix $n$. Let $m\ge n$. We induct on $m$. For $m=n$, it's trivially true. Assume that it's true for all $m=1,2,\dots,k$ with $m \ge n$. We show that it's true for $m=k+1$. Note that \begin{align*} \sum_{i = 1}^n \min \left(\left\lfloor \frac{x}{i} \right\rfloor, k+1\right) &= \sum_{i = 1}^{k+1} \min \left(\left\lfloor \frac{x}{i} \right\rfloor, n\right)\\ &= \sum_{i = 1}^k \min \left(\left\lfloor \frac{x}{i} \right\rfloor, n\right) + \min \left(\left\lfloor \frac{x}{k+1} \right\rfloor, n\right)\\ &= \sum_{i = 1}^n \min \left(\left\lfloor \frac{x}{i} \right\rfloor, k\right) + \min \left(\left\lfloor \frac{x}{k+1} \right\rfloor, n\right) \iff \\ \sum_{i = 1}^n \min \left(\left\lfloor \frac{x}{i} \right\rfloor, k+1\right)-\min \left(\left\lfloor \frac{x}{i} \right\rfloor, k\right) &= \min \left(\left\lfloor \frac{x}{k+1} \right\rfloor, n\right) \end{align*}Let $a$ be a number such that $\left\lfloor \frac{x}{a} \right\rfloor \ge k+1$ and $\left\lfloor \frac{x}{a+1} \right\rfloor < k+1$. There are two cases: a. Case 1: $n \ge a$. Obviously the $LHS = a$. Note that $\left\lfloor \frac{x}{a} \right\rfloor \ge k+1 \implies \frac{x}{a}\ge\left\lfloor \frac{x}{a} \right\rfloor \ge k+1 \implies \frac{x}{a} \ge k+1 \implies \frac{x}{k+1} \ge a$. Also $\left\lfloor \frac{x}{a+1} \right\rfloor < k+1 \implies \frac{x}{a+1} < k+1 \implies \frac{x}{k+1} < a+1$. Thus $\left\lfloor \frac{x}{k+1} \right\rfloor = a$. Since $n \ge a$, $RHS = a$. b. Case 2: $a > n$. Obviously $LHS = n$. Note that $\left\lfloor \frac{x}{a} \right\rfloor \ge k+1 \implies \frac{x}{a}\ge\left\lfloor \frac{x}{a} \right\rfloor \ge k+1 \implies \frac{x}{a} \ge k+1 \implies \frac{x}{k+1} \ge a >n$, so $RHS = n$ too.

We will perform induction. The base case is obvious. Notice that we essentially wish to prove $$\sum_{i=1}^{m+1} \min\left( \left\lfloor \frac xi \right\rfloor, n \right) - \sum_{i=1}^m \min\left( \left\lfloor \frac xi \right\rfloor, n \right) = \min \left ( \left\lfloor \frac{x}{m+1} \right\rfloor , n \right) = \sum_{i=1}^n \min\left( \left\lfloor \frac xi \right\rfloor, m+1 \right) - \sum_{i=1}^n \min\left( \left\lfloor \frac xi \right\rfloor, m \right)$$Notice that all the terms on the RHS where $\min \left( \left\lfloor \frac{x}{i} \right\rfloor, m \right) = \left\lfloor \frac{x}{i} \right\rfloor$ will cancel. Now the RHS will simply count all $i \le n$ such that $\left\lfloor \frac{x}{i} \right\rfloor > m+1$, which is clearly what the LHS counts. Therefore we are done.

The graph of $y\le\lfloor\frac{x}{i}\rfloor$ is symmetric about $y=x$ and the sums just find the areas in the graph inside a $m$ by $n$ and $n$ by $m$ rectangle, which would be the same by symmetry.

Rename $x$ to $k;$ then the left side counts the number of lattice points in the intersection of the points on or under $xy=k$ and the rectangle with vertices $(1,1),(n,1),(n,m),(1,m)$ and the right side counts the same thing, but with the rectangle reflected over $y=x.$ These are the same by symmetry.

Consider the tuples $(i, j)$ of positive integers where $i \le m, j \le n, ij \le x.$ We double count the number of tuples by fixing $i, j$ respectively. Fixing $i$, note that $j\le \lfloor \frac{x}{i} \rfloor$ But we also condition $j \le n$, hence $j \le \min{(\lfloor \frac{x}{i} \rfloor, n)}.$ Spanning $i$ over integers $1, 2, \dots, m,$ number of tuples are, $$\sum_{i = 1}^{m} \left ( \min{(\lfloor \frac{x}{i} \rfloor, n)} \right ).$$We can find a symmetric relation by fixing $j$ and attain the desired equality.

Both sides count the number of $1 \le i \le n, 1 \le j \le n$ such that $ij \le x$. Indeed, the left hand side counts by cases on $i$, the right hand side counts by cases on $j$, since they count the same thing, they must be equal. The end. Remark. Having solved this problem before really helped me a lot.

surely induct