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}.\]
Problem
Source: USAMO 1985 Problem 5
Tags: invariant, geometry, rectangle, algebra unsolved, algebra
18.02.2014 07:22
04.08.2014 19:29
A different approach:
05.08.2014 07:17
Imagine a $85 \times 20$ rectangle, with $85$ rows and $20$ columns. The rows are numbered $1,2,\ldots,85$ from bottom to top, and the columns are numbered $0,1,\ldots,19$ from left to right. Let $(r,c)$, the cell on $r$-th row and $c$-th column, be red if $a_c \ge r$ and green otherwise; we also take $a_0 = 0$. Then observe that $(r,c)$ is green if and only if $b_r \ge c+1$; proof follows. We can imagine the red squares in each column forming a "bar", and so as the green squares in each row, and each green bar points at the leftmost red bar. The green bar on $r$-th row points to the red bar on $c$-th column, indicating that $b_r = c$, since $a_{c-1} < r \le a_c$. Now, there are $a_c$ red squares in column $c$ and $b_r$ green squares in row $r$. Thus, summing over all $c = 0,1,\ldots,19$ and $r = 1,2,\ldots,85$, we have $a_0 + a_1 + a_2 + \ldots + a_{19} + b_1 + b_2 + \ldots + b_85 = a_1 + a_2 + \ldots + a_{19} + b_1 + b_2 + \ldots + b_85$ is the total number of red and green squares. But each square in our rectangle is either red or green, so the total number of squares is just the area of the rectangle: $20 \cdot 85 = \boxed{1700}$.
07.12.2022 09:13
NewAlbionAcademy wrote:
Since $a_1,a_2,a_3,\cdots$ is a non-decreasing sequence, you can not say $b_{a_1+1}=b_{a_1+2}=...=b_{a_2}=2$. What if $a_1=a_2$? If $a_1=a_2$, then $b_1=b_2=...=b_{a_1}=...=b_{a_2}=1$ not $2$.
12.09.2024 17:34
Arslan wrote: Since $a_1,a_2,a_3,\cdots$ is a non-decreasing sequence, you can not say $b_{a_1+1}=b_{a_1+2}=...=b_{a_2}=2$. What if $a_1=a_2$? If $a_1=a_2$, then $b_1=b_2=...=b_{a_1}=...=b_{a_2}=1$ not $2$. Sure you can. If $a_1 = a_2$ then the range $(b_{a_1+1}, \dots, b_{a_2})$ subsequence contains no elements.
12.09.2024 17:58
In fact, we will prove that: Claim: If $a_X = Y$ then \[ a_1 + \dots + a_X + b_1 + \dots + b_Y = (X+1) \cdot Y. \]Hence the ``maximum'' condition in the problem is a red herring; the expression is always $(19+1) \cdot 85 = 1700$. The proof of the claim is based on the following picture. Draw an $(X+1) \times Y$ grid. The rows are labeled $b_1$, $b_2$, \dots, $b_Y$ from bottom to top. The first column has no label, and then from left to right they read $a_1$, \dots, $a_X$. For the column labeled $a_i$, put a red counter on the bottom $a_i$ cells. For the rot labeled $b_j$, put a blue counter on the leftmost $b_j$ cells. An example is illustrated below for $X = 5$ and $Y = 6$, where $a_1 = 1$, $a_2 = 3$, $a_3 = a_4 = 5$, $a_5 = 6$. [asy][asy] size(8cm); int X = 5; int Y = 6; for (int i=0; i<=X+1; ++i) { draw((i,0)--(i,Y), grey); } for (int i=0; i<=Y; ++i) { draw((0,i)--(X+1,i), grey); } int[] heights = {0,1,3,5,5,6}; int[] widths = {1,2,2,3,3,5}; for (int i=0; i<=X; ++i) { for (int j=0; j<Y; ++j) { filldraw(circle((i+0.5,j+0.5), 0.3), j >= heights[i] ? lightblue : lightred, black); } } for (int i=1; i<=X; ++i) { draw((i+0.5,0)--(i+0.5,heights[i]-0.5), darkred+1, EndArrow(TeXHead)); dot((i+0.5,0), red); label(rotate(90)*("$a_{" + ((string) i) + "} = " + ((string) heights[i]) + "$"), (i+0.5, 0), dir(-90), red); } for (int j=0; j<Y; ++j) { draw((0,j+0.5)--(widths[j]-0.5, j+0.5), darkblue+1, EndArrow(TeXHead)); label("$b_{" + ((string) (j+1)) + "} = " + ((string) widths[j]) + "$", (0, j+0.5), dir(180), blue); } [/asy][/asy] By definition, in the $j$th column from the bottom ($1 \le j \le Y$), the chain of blue counters stops exactly before the red counter begins. Consequently, the entire $(X+1) \times Y$ grid is partitioned into red and blue counters. But $\sum a_i$ is the number of red counters and $\sum b_j$ is the number of blue counters, so we're done.