1985 USAMO Problems/Problem 5
Let be a non-decreasing sequence of positive integers. For , define , that is, is the minimum value of such that . If , determine the maximum value of .
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 th column we fill the first cells with one dot each. Then the th row shall have 85 dots. Now consider the first 19 columns of this array, and consider the first 85 rows. In row , we see that the number of blank cells is equal to . Therefore the number of filled cells in the first 19 columns of row is equal to .
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 . Alternatively, we can sum the number of dots in each row: this is . Since we have counted the same number in two different ways, these two sums must be equal. Therefore Note that this shows that the value of the desired sum is constant.
|1985 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5|
|All USAMO Problems and Solutions|