[ELMO2] The Multiplication Table

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

[ELMO2] The Multiplication Table

G H J

Reveal topic tags

Combinatorial sum

L

G H BBookmark kLocked kLocked NReply

Source: ELMO 2015, Problem 2 (Shortlist N1)

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6874 posts

#1 h Jun 27, 2015, 1:13 AM • 5 Y

Y by kk108, Adventure10, Mango247, aidan0626, Blue_banana4

Let $m$ , $n$ , and $x$ be positive integers. Prove that $\sum_{i = 1}^n \min\left(\left\lfloor \frac{x}{i} \right\rfloor, m \right) = \sum_{i = 1}^m \min\left(\left\lfloor \frac{x}{i} \right\rfloor, n \right).$
Proposed by Yang Liu

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

55 posts

MLMC

#2 h Jun 27, 2015, 1:42 AM • 3 Y

Y by mijail, Adventure10, Mango247

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2130 posts

DrMath

#3 h Jun 27, 2015, 1:48 AM • 3 Y

Y by shinichiman, Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

977 posts

#4 h Jun 27, 2015, 2:15 AM • 1 Y

Y by Adventure10

OMG there is a combinatorial bijection for this.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

tenniskidperson3

2376 posts

tenniskidperson3

#5 h Jun 27, 2015, 2:24 AM • 16 Y

Y by fireclaw105, bobthesmartypants, drkim, Dukejukem, MSTang, WolfusA, Euler_88, electrovector, mijail, TETris5, myh2910, Adventure10, aidan0626, D_S, ihatemath123, Funcshun840

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3212 posts

#6 h Jun 27, 2015, 3:48 AM • 1 Y

Y by Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

somepersonoverhere

1313 posts

somepersonoverhere

#7 h Jun 27, 2015, 2:20 PM • 4 Y

Y by Viswanath, myh2910, Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

92 posts

#8 h Jun 28, 2015, 3:00 AM • 2 Y

Y by Adventure10, Mango247

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.

This post has been edited 1 time. Last edited by theflowerking, Jun 28, 2015, 3:01 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shiningsunnyday

1350 posts

shiningsunnyday

#9 h Jun 28, 2015, 7:56 AM • 2 Y

Y by Adventure10, mpcnotnpc

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1199 posts

#10 h Jun 28, 2015, 12:31 PM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1135 posts

#11 h Nov 22, 2015, 9:50 PM • 1 Y

Y by Adventure10

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

695 posts

#12 h Nov 24, 2015, 8:24 PM • 2 Y

Y by Complex2Liu, Adventure10

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

14 posts

HsuAn

#13 h Dec 29, 2018, 4:12 AM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1671 posts

pad

#14 h Mar 31, 2019, 12:17 AM • 1 Y

Y by Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

algebra_star1234

2467 posts

algebra_star1234

#15 h Jun 13, 2020, 11:51 PM • 1 Y

Y by Math_Kobekeye

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

113 posts

#16 h Jul 2, 2020, 3:27 AM

Y by

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$

This post has been edited 3 times. Last edited by Vitriol, Jul 2, 2020, 3:33 AM
Reason: asdfasdfsadf

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3760 posts

#17 h Nov 10, 2020, 4:41 PM • 3 Y

Y by vsamc, centslordm, Mango247

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.

motivation

This post has been edited 5 times. Last edited by Williamgolly, Nov 10, 2020, 5:35 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3217 posts

#18 h Feb 1, 2021, 3:42 PM • 6 Y

Y by centslordm, tenebrine, purplepenguin2, Mango247, Mango247, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1002 posts

Afo

#19 h Sep 9, 2021, 2:21 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3368 posts

#20 h Aug 15, 2023, 8:33 PM • 1 Y

Y by centslordm

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4221 posts

#21 h Aug 20, 2023, 8:46 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1729 posts

OronSH

#22 h Nov 11, 2023, 3:18 PM

Y by

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.

This post has been edited 1 time. Last edited by OronSH, Nov 11, 2023, 3:19 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1631 posts

#23 h Dec 22, 2023, 1:22 AM

Y by

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.

This post has been edited 2 times. Last edited by Aaryabhatta1, Dec 22, 2023, 1:22 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

651 posts

#24 h Jan 5, 2024, 6:47 AM • 1 Y

Y by lelouchvigeo

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.

This post has been edited 1 time. Last edited by mannshah1211, Jan 5, 2024, 6:49 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

274 posts

#25 h May 1, 2024, 3:26 AM

Y by

surely induct
solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1055 posts

#26 h Feb 8, 2025, 3:28 AM

Y by

both of these sums count the number of items in an $m \times n$ multiplication table that are less than or equal to $x$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

196 posts

#27 h Apr 8, 2025, 10:42 PM

Y by

Note that the RHS and LHS are counting the set
$\{(i,j) \in \mathbb Z^2: 1 \leq ij \leq x, 1 \leq i \leq m, 1 \leq j \leq n\}$ from the perspective of $i$ and the perspective of $j$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a