On a Problem of Steinhaus Concerning Binary Sequences

Abstract

A finite ±1 sequence X yields a binary triangle ΔX whose first row is X, and whose (k + 1)th row is the sequence of pairwise products of consecutive entries of its kth row, for all k ≥ 1. We say that X is balanced if its derived triangle ΔX contains as many +1s as −1s. In 1963, Steinhaus asked whether there exist balanced binary sequences of every length n ≡ 0 or 3 mod 4. While this problem has been solved in the affirmative by Harborth in 1972, we present here a different solution. We do so by constructing strongly balanced binary sequences, i.e., binary sequences of length n all of whose initial segments of length n – 4t are balanced, for 0 ≤ t ≤ n/4. Our strongly balanced sequencesdo occur in every length n ≡ 0 or 3 mod 4. Moreover, we provide a complete classification of sufficiently long strongly balanced binary sequences.

Keywords:

• Steinhaus
• balanced binary sequence
• derived sequence
• derived triangle