Exercise 4.5.4* (Sum of consecutive blocks on a circumference)

Question

Let the integers $1, 2,\ldots, n$ be placed in any order around the circumference of a circle. For any $k<n$, prove that there are $k$ integers in a consecutive block on the circumference having sum at least $(kn + k)/2$.

Richard Ganaye · Accepted Answer

\begin{proof}   For $1 \leq i \leq n$, let $S_i$ denote the sum of the elements of the block starting from the $i$-th place, and consider $S$ the sum of all $S_i$.

Since every integer $j$ is located in $k$ distinct consecutive blocks,
\begin{align*}
S &= \sum_{i=1}^n S_i\
 &= k (1+2+\cdots + n)\
 &= k \, \frac{n(n+1)}{2}.
\end{align*}
Assume for the sake of contradiction that for every $i \in [\![1, n ]\!]$, $S_i < \frac{kn + k}{2}$. Then $S = \sum\limits_{i = 1}^n S_i < n  \frac{kn + k}{2}$. Therefore
$$S =  k \, \frac{n(n+1)}{2} < n  \frac{kn + k}{2},$$
and this is a contradiction, since both members are equal.

So there is a consecutive block on the circumference having sum at least $(kn + k)/2$.

\end{proof}

Exercise 4.5.4* (Sum of consecutive blocks on a circumference)

Answers

Comments

Exercise 4.5.4* (Sum of consecutive blocks on a circumference)

Answers

Comments

Add answer