Proving that $\sum_{i=1}^n\min(\frac{x}{i}, m)=\sum_{i=1}^n\min(\frac{x}{i}, n)$ where divisions are rounded down to the nearest integer.(ELMO-2015) I was just trying to solve the following question:
Prove that $\sum_{i=1}^{n}\min(\frac{x}{i}, m)=\sum_{i=1}^{m}\min(\frac{x}{i}, n)$ where divisions are rounded down to the nearest integer and $x,m,n$ are integers.
I did not know where to begin with this question and hence I looked at the solution. The solution states that both sides are merely counting the amount of pairs $(k, l)$ such that $1\le k \le m$ and $1\le l \le n$ and $kl\le x$
I am trying to comprehend this beautiful solution, however I am not succeeding could you please explain to me why this holds true?
 A: The number of pairs $(k, l)$ such that $1 \le k \le m, 1\le l \le n, kl \le x$ can be written as $$\sum_{k=1}^m \sum_{l=1}^n [ kl \le x ]$$ where the brackets are Iverson brackets.
Then the restriction on $l$ for $1 \le l \le n, kl \le x$ to be true is that $1 \le l \le n$ and $l \le \frac{x}{k}$ or equivalently $1 \le l \le \min\left(n, \frac{x}{k}\right)$
$$\sum_{k=1}^m \sum_{l=1}^n [ 1 \le l \le \min\left(n, \frac{x}{k}\right) ]$$
Note that $\min\left(n, \frac{x}{k}\right) \le n$ and assuming that $\frac{x}{m} \ge 1$, we can simply count the $l$ that satisfy the condition so that the sum becomes $$\sum_{k=1}^m \min\left(n, \frac{x}{k}\right)$$
In a similar way, we can sum along $l$ instead of $k$ and the sums must be the same since they are equal to the same double sum. Note that the condition $\frac{x}{m}, \frac{x}{n} \ge 1 \to x \ge \max(m, n)$ must be true.
A: Here is an illustrated example where $m=7, n= 10$ and $x=28$. Here, we have an $m\times n$ table, where the cell in row $i$ and column $j$ is filled with the product $ij$, and that cell is shaded if and only if $ij\le 28$.
You can count the number of shaded squares in two ways; you can either count the number of shaded squares in each columns, and then add up those totals, or first count the number in each row and add those totals. Let us talk about counting the columns first:

*

*For columns $1-4$, all of the squares are green. Each columns contributes $m$ green squares, one for each row.


*For columns $5-10$, some of the squares are green. For the $i^{th}$ columns, then number of green squares is $\frac{28}i$, rounded down.
Adding these up, we get exactly $\sum_{i=1}^n \min(\frac{x}i,m)$. If you do the same reasoning for the rows, you get the other summation. Since they both count the number of green squares, they must be equal!

