AlgebraDifficulty 7.1National Olympiad, round 2Find the answer
Let a1,a2,a3,⋯ be a non-decreasing sequence of positive integers. For m≥1 , define bm=min{n:an≥m} , that is, bm is the minimum value of n such that an≥m . If a19=85 , determine the maximum value of a1+a2+⋯+a19+b1+b2+⋯+b85 .
A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.
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 ai 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 bj−1 . Therefore the number of filled cells in the first 19 columns of row j is equal to 20−bj . 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 a1+⋯+a19 . Alternatively, we can sum the number of dots in each row: this is (20−b1)+⋯+(20−b85) . Since we have counted the same number in two different ways, these two sums must be equal. Therefore a1+⋯+a19+b1+⋯+b85=20⋅85=1700. Note that this shows that the value of the desired sum is constant.
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: Omni-MATH,
licensed Apache-2.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.