On a problem of Steinhaus concerning binary sequences. (English) Zbl 1070.11008

Eliahou, Shalom; Hachez, Delphine

Exp. Math. 13, No. 2, 215-229 (2004).

For a finite sequence \(X=(x_1,x_2,\dots,x_n)\) of length \(n\) with \(x_i\in \{ -1,1\}\) let \(\delta X=\delta^1 X=(x_1x_2,x_2x_3,\dots,x_{n-1}x_n)\), \(\delta^k X=\delta(\delta^{k-1}X)\) for \(k\geq 2\) and \(\Delta X=\{ X,\delta X,\dots,\delta^{n-1}X\}\). A sequence \(X\) is called balanced if \(\sum_{(z_1,\dots,z_i)\in \Delta X}\sum_{j=1}^i z_j=0\).
In [One hundred problems in elementary mathematics. Oxford etc.: Pergamon Press (1963; Zbl 0116.24102)], H. Steinhaus asked whether there are balanced sequences of lengths \(n\) for every \(n\equiv 0\) or \(3\) mod \(4\). While this question was given a positive answer by H. Harborth [J. Comb. Theory, Ser. A 12, 253–259 (1972; Zbl 0229.05003)], the authors establish a stronger result by constructing sequences of length \(n\) for every \(n\equiv 0\) or \(3\) mod \(4\) such that all initial segments of length \(n-4t\) for \(0\leq t\leq \frac{n}{4}\) are balanced. Furthermore, the authors provide a complete classification of sufficiently long such sequences.

Reviewer: Dieter Rautenbach (Bonn)

MSC:

11B75	Other combinatorial number theory
05A05	Permutations, words, matrices
05A15	Exact enumeration problems, generating functions

Keywords:

Steinhaus; balanced binary sequence

Citations:

Zbl 0116.24102; Zbl 0229.05003

References:

[1]	Duchet Pierre, MATh.en. JEANS pp 139– (1995)
[2]	DOI: 10.1016/0097-3165(72)90039-8 · Zbl 0229.05003 · doi:10.1016/0097-3165(72)90039-8
[3]	Steinhaus Hugo, One Hundred Problems in Elementary Mathematics. (1963) · Zbl 0116.24102