Balanced Gray codes (Q1379168)

Summary: It is shown that balanced \(n\)-bit Gray codes can be constructed for all positive integers \(n\). A balanced Gray code is one in which the bit changes are distributed as equally as possible among the bit positions. The strategy used is to prove the existence of a certain subsequence which will allow successful use of the construction proposed by \textit{J. P. Robinson} and \textit{M. Cohn} in 1981 [IEEE Trans. Comput. C-30, 17-23 (1981; Zbl 0455.94053)]. Although \textit{D. G. Wagner} and \textit{J. West} proved in 1991 [Congr. Numerantium 80, 217-223 (1991; Zbl 0735.94011)] that balanced Gray code schemes exist when \(n\) is a power of 2, the question for general \(n\) has remained open since 1980 when it first attracted attention.