Competition problem — Combinatorics

Library / /103 of 105

Combinatorics Difficulty 5.8 AIME, harder Prove it United States

Problem:
Define a multiplication table to be a rectangular array in which every row is labeled with a different positive integer, every column is labeled with a different positive integer, and every cell is labeled with the product of its row and column numbers, for instance:

$\times$	2	6	4	3
2	4	12	8	6
1	2	6	4	3
3	6	18	12	9

The above table is

3 \times 4

but contains only 8 distinct products. What is the minimum number of distinct products in a

2012 \times 2012

multiplication table?

Solution

Solution:
The answer is $2 \cdot 2012 - 1 = 4013$ .

To get a multiplication table with only 4013 products, it suffices to fill the rows and columns with successive powers of two: $2^{0}, 2^{1}, 2^{2}, \ldots, 2^{2012}$ for both the rows and the columns. Then the products within the table will be $2^{0}, 2^{1}, \ldots, 2^{2 \cdot 2012}$ .

To prove that the number of products can be no fewer, let us rearrange the rows and columns of the table so that they are in increasing order. Then consider moving in an L-shaped path from the upper left product to the upper right product to the lower right product:

$\times$	2	3	4	6
1	$2$	$3$	$4$	$6$
2	4	6	8	$12$
3	6	9	12	$18$

In a

2012 \times 2012

table, this traverses 4013 cells, and all the while the products are increasing, so there are at least 4013 distinct products.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.