Block partitions of sequences (Q2339607)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Block partitions of sequences |
scientific article |
Statements
Block partitions of sequences (English)
0 references
2 April 2015
0 references
For a sequence \(A=\left(a_1,a_2,\dots,a_n\right)\) of real numbers, a \textit{block} \(B\) is either the empty set or a subsequence of the form \(\{a_i,a_{i+1},\dots,a_j\}\) with \(i\leq j\), whose \textit{size} is the sum of its elements; the blocks \(B_1,B_2,\dots,B_k\) form a \(k\)-partition \(B_1,B_2,\dots,B_k\) of \(A\) of respective sizes \(b_1,b_2,\dots,b_k\) if they decompose the sequence so that if \(a_h\) is the last element of a non-empty block, then \(a_{h+1}\) is the first element of the next labelled non-empty block. The authors prove the following theorem algorithmically, and then generalize it: {Theorem 2.1.} For positive integers \(n,k\), any sequence \(A=\left(a_1,a_2,\dots,a_n\right)\) (\(0\leq a_i\leq1\), \(i=1,\dots,n\)) admits a \(k\)-partition \(B_1,B_2,\dots,B_k\) with \(\max\limits_{i=1,\dots,k} b_i\leq\min\limits_{i=1,\dots,k} b_i+1\). Related problems have been treated in [\textit{I. Bárány} and \textit{B. Doerr}, Linear Algebra Appl. 414, No. 2--3, 464--469 (2006; Zbl 1091.15030)] and [\textit{I. Barany} and \textit{V. S. Grinberg}, Linear Algebra Appl. 41, 1--9 (1981; Zbl 0467.90079)].
0 references