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
NewAlbionAcademy
18.02.2014 07:22
Note that $b_1=b_2=...=b_{a_1}=1$, $b_{a_1+1}=b_{a_1+2}=...=b_{a_2}=2$ and so on.
Thus we have
$a_1+a_2+\cdots a_{19}+b_1+b_2+\cdots b_{85} = a_1+a_2+\cdots a_{19}+1(a_1)+2(a_2-a_1)+3(a_3-a_2)+\cdot\cdot\cdot+19(a_{19}-a_{18})=20a_{19}=\boxed{1700}$.
McTeague
04.08.2014 19:29
A different approach:
Let the sum described in the problem be $S$. We claim that we can transform any non-decreasing sequence of $19$ positive integers with $a_{19} = 85$ into the sequence of $19$ occurrences of $85$ while leaving $S$ invariant, i.e. every such sequence has the same value of $S$.
Consider a sequence different from a list of all $85$s. Then there exists $a_i$ such that $a_i < a_{i+1}$; in particular, $a_i < 85$. If we increase $a_i$ by $1$, then $a_1+a_2+\cdots+a_{19}$ increases by $1$. Call the new $a_i$ as ${a_i}'$ (so we have $a_i + 1 = {a_i}'$).
On the other hand, we then have that $b_{{a_i}'}$ becomes $i$ rather than $i+1$, so that $b_1+b_2+\cdots+b_{85}$ is decreased by $1$. Thus, $S$ has a net change of $0$. Therefore, we can increase the terms of the sequence one by one so that all of them are $85$ while leaving $S$ unchanged. We can then calculate the maximum $S$ by determining what it is for this particular sequence of all $85$s, namely $1700$.
Note that $a_i$ being increased by $1$ and $b_{a_i}$ being decreased by $1$ are the only changes that occur to $S$ in one occurrence of the operation. If $a_{i-1} < a_i$, then any $j$ such that $b_j = i$ will still satisfy that after $a_i$ is transformed to $a_i+1$, while if $a_{i-1} = a_i$, then there existed no $j$ initially such that $b_j = i$ anyway.
chaotic_iak
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}$.
Arslan
07.12.2022 09:13
NewAlbionAcademy wrote:
Note that $b_1=b_2=...=b_{a_1}=1$, $b_{a_1+1}=b_{a_1+2}=...=b_{a_2}=2$ and so on.
Thus we have
$a_1+a_2+\cdots a_{19}+b_1+b_2+\cdots b_{85} = a_1+a_2+\cdots a_{19}+1(a_1)+2(a_2-a_1)+3(a_3-a_2)+\cdot\cdot\cdot+19(a_{19}-a_{18})=20a_{19}=\boxed{1700}$.
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$.
v_Enhance
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.
v_Enhance
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.