Maths Olympiad Prep

Library / /43 of 115

Algebra Difficulty 7.1 National olympiad, round 2 Find the answer

Let a1,a2,a3,a_1,a_2,a_3,\cdots be a non-decreasing sequence of positive integers. For m1m\ge1 , define bm=min{n:anm}b_m=\min\{n: a_n \ge m\} , that is, bmb_m is the minimum value of nn such that anma_n\ge m . If a19=85a_{19}=85 , determine the maximum value of a1+a2++a19+b1+b2++b85a_1+a_2+\cdots+a_{19}+b_1+b_2+\cdots+b_{85} .

A number or a short expression. Spacing and $ signs are ignored.

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 ii th column we fill the first aia_i cells with one dot each. Then the 1919 th row shall have 85 dots. Now consider the first 19 columns of this array, and consider the first 85 rows. In row jj , we see that the number of blank cells is equal to bj1b_j-1 . Therefore the number of filled cells in the first 19 columns of row jj is equal to 20bj20-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 a1++a19a_1+\cdots+a_{19} . Alternatively, we can sum the number of dots in each row: this is (20b1)++(20b85)(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 a1++a19+b1++b85=2085=1700.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.

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 and solution reproduced as published; topic and difficulty added by this site.