Given a positive integer $n$, let $a_1,a_2,..,a_n$ be a sequence of nonnegative integers. A sequence of one or more consecutive terms of $a_1,a_2,..,a_n$ is called $dragon$ if their aritmetic mean is larger than 1. If a sequence is a $dragon$, then its first term is the $head$ and the last term is the $tail$. Suppose $a_1,a_2,..,a_n$ is the $head$ or/and $tail$ of some $dragon$ sequence; determine the minimum value of $a_1+a_2+\cdots +a_n$ in terms of $n$.
Problem
Source: China Western Mathematical Olympiad 2014 No.4
Tags: floor function, algorithm, algebra, combinatorics, hard combinatorics
19.08.2014 15:30
$\lfloor \frac{n}{2} \rfloor +1.$ China Mathematical Olympiad 1988 problem3: Given a finite sequence of real numbers $a_1,a_2,\dots ,a_n$ ($\ast$), we call a segment $a_k,\dots ,a_{k+l-1}$ of the sequence ($\ast$) a “long”(Chinese dragon) and $a_k$ “head” of the “long” if the arithmetic mean of $a_k,\dots ,a_{k+l-1}$ is greater than $1988$. (especially if a single item $a_m>1988$, we still regard $a_m$ as a “long”). Suppose that there is at least one “long” among the sequence ($\ast$), show that the arithmetic mean of all those items of sequence ($\ast$) that could be “head” of a certain “long” individually is greater than $1988$.
23.08.2014 23:43
Hint. cover the sequence $a_1 \cdots a_n $ with dragons such that each $a_i$ belongs to at least one dragon and at most two dragons. To do this use an algorithm to put dragons from the left until you cover everything such that if you have dragons $D_1 \cdots D_k $ pick $D_{k+1}$ the dragon with the leftmost head such that it intersects the dragon $D_K \cup $ the number after the head of the dragon to the right. Answer $ \lfloor\frac{n}{2}\rfloor+1. $
03.10.2014 14:32
DraPekka wrote: if their aritmetic mean is larger than 1. Hey guys did you misread as "not less than" 1? I keep getting $\lfloor{\dfrac{n}{2}}\rfloor + 2$.
27.03.2016 14:24
The original question should be "not less than $1$" instead of "larger than $1$". The question follows quite directly from the CMO 1988 problem - replacing $1988$ by $1$, we know that the arithmetic mean of all heads in the sequence, and by symmetry all tails, is not less than $1$. Clearly the whole sequence cannot be all $0$s, thus there must be an $a_i\ge 1$ in the sequence, which taken individually is both a head and a tail. Since all $a_i$s are either head or tail, the number of heads or the number of tails must not be less than $\left\lceil \frac{n+1}{2}\right\rceil$, and by the lemma the arithmetic mean of these terms is not less than $1\implies \sum a_i\ge \left\lceil \frac{n+1}{2}\right\rceil = \left\lfloor \frac{n}{2} \right\rfloor +1$. This is achievable by letting $a_{ \left\lceil \frac{n+1}{2}\right\rceil}= \left\lceil \frac{n+1}{2}\right\rceil$, and all other $a_i$s$=0$.