# Low difference between sums of blocks

Let $n,k$ be any positive integers. Given real numbers $0\leq a_1,\dots,a_n\leq C$, is it always possible to partition them into $k$ blocks, where each block contains consecutive elements of the sequence, so that the sums of any two blocks differ by at most $C$? If not, what is the best bound?

Remark that this difference may need to be as large as $C$, such as when $a_1=C$ and $a_2=\dots=a_n=0$. An idea is to start with any partition and try to reduce this difference, but since each block needs to contain consecutive elements it is not clear how far the difference can be reduced.

Edit: A difference of $2C$ can be achieved, as shown by Alex Ravsky below. So the bound is between $C$ and $2C$.

If some of the blocks may be empty then we can achieve a partition with the difference at most $2C$ and may be this bound is tight (I’ll think about it). We shall proceed as follows. For the simplicity we assume that all $a_i$’s are positive. Put $a=\frac 1k \sum_{i=1}^n a_i$, $n(0)=0$, $S_0=0$, and for each $1\le j\le k$ let $n(j)$ be the smallest number such that $S_j=\sum_{i=1}^{n(j)} a_i\ge \frac jk a$, and $A_j=\{a_{n(j-1)},\dots, a_{n(j)}\}$ (the set $A_j$ is non-empty provided $a\ge kC$). Then $s_j=\sum_{a_i\in A_j} a_i =S_j-S_{j-1}$ and
$$\frac ak-C=\frac jk a-\left(\frac {j-1}k a+C\right)\le S_j-S_{j-1}\le \left(\frac {j}k a+C\right)- \frac {j-1}k a=\frac ak+C.$$
So $|s_j-s_{j’}|\le 2C$ for any $1\le j, j’\le k$.
The text passage discusses a mathematical problem involving partitioning a sequence of real numbers into blocks such that the sums of the blocks differ by at most a certain bound. It includes a proposed solution and a proof that a difference of \(2C\) can be achieved.
single_question_with_answer
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Low difference between sums of blocks

Let $n,k$ be any positive integers. Given real numbers $0\leq a_1,\dots,a_n\leq C$, is it always possible to partition them into $k$ blocks, where each block contains consecutive elements of the sequence, so that the sums of any two blocks differ by at most $C$? If not, what is the best bound?

Remark that this difference may need to be as large as $C$, such as when $a_1=C$ and $a_2=\dots=a_n=0$. An idea is to start with any partition and try to reduce this difference, but since each block needs to contain consecutive elements it is not clear how far the difference can be reduced.

Edit: A difference of $2C$ can be achieved, as shown by Alex Ravsky below. So the bound is between $C$ and $2C$.

If some of the blocks may be empty then we can achieve a partition with the difference at most $2C$ and may be this bound is tight (I’ll think about it). We shall proceed as follows. For the simplicity we assume that all $a_i$’s are positive. Put $a=\frac 1k \sum_{i=1}^n a_i$, $n(0)=0$, $S_0=0$, and for each $1\le j\le k$ let $n(j)$ be the smallest number such that $S_j=\sum_{i=1}^{n(j)} a_i\ge \frac jk a$, and $A_j=\{a_{n(j-1)},\dots, a_{n(j)}\}$ (the set $A_j$ is non-empty provided $a\ge kC$). Then $s_j=\sum_{a_i\in A_j} a_i =S_j-S_{j-1}$ and
$$\frac ak-C=\frac jk a-\left(\frac {j-1}k a+C\right)\le S_j-S_{j-1}\le \left(\frac {j}k a+C\right)- \frac {j-1}k a=\frac ak+C.$$
So $|s_j-s_{j’}|\le 2C$ for any $1\le j, j’\le k$.
user
The text passage discusses a mathematical problem involving partitioning a sequence of real numbers into blocks such that the sums of the blocks differ by at most a certain bound. It includes a proposed solution and a proof that a difference of \(2C\) can be achieved.

TYPE: SINGLE_QUESTION_WITH_ANSWER