1985 USAMO Problems/Problem 5

Problem

Let $a_1,a_2,a_3,\cdots$ be a non-decreasing sequence of positive integers. For $m\ge1$ , define $b_m=\min\{n: a_n \ge m\}$ , that is, $b_m$ is the minimum value of $n$ such that $a_n\ge m$ . If $a_{19}=85$ , determine the maximum value of $a_1+a_2+\cdots+a_{19}+b_1+b_2+\cdots+b_{85}$ .

Solution

We create an array of dots like so: the array shall go out infinitely to the right and downwards, and at the top of the $i$ th column we fill the first $a_i$ cells with one dot each. Then the $19$ th row shall have 85 dots. Now consider the first 19 columns of this array, and consider the first 85 rows. In row $j$ , we see that the number of blank cells is equal to $b_j-1$ . Therefore the number of filled cells in the first 19 columns of row $j$ is equal to $20-b_j$ .

We now count the number of cells in the first 19 columns of our array, but we do it in two different ways. First, we can sum the number of dots in each column: this is simply $a_1+\cdots+a_{19}$ . Alternatively, we can sum the number of dots in each row: this is $(20-b_1)+\cdots +(20-b_{85})$ . Since we have counted the same number in two different ways, these two sums must be equal. Therefore $a_1+\cdots +a_{19}+b_1+\cdots +b_{85}=20\cdot 85=\boxed{1700}.$ Note that this shows that the value of the desired sum is constant.

1985 USAMO (Problems • Resources)
Preceded by Problem 4	Followed by Last Question
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

Page

Toolbox

Search

1985 USAMO Problems/Problem 5

Problem

Solution

See Also