Conference rusure::math

116.0. "A Binary Sequence" by HARE::STAN () Mon Aug 06 1984 12:32

Here's an interesting problem by Allen Barnes (from the journal
Mathematics and Computer Education, 18(1984)148, problem 203):

A string of zeros and ones is to be formed such that when it is
partitioned (from the left) into substrings of length k, k=1,2,3...,n,
each of the 2^k possible substrings is found with the same relative
frequency.  Example:

		0  0  0  1  1  0  1  1

satisfies n=2 as follows:

Substring:		 0    1           00    01    10    11

Relative Frequency:	1/2  1/2          1/4   1/4   1/4   1/4

The case n=3 is satisfied by  000001010100101011111110.

(a) Find a string for the n=4 case.
(b) Find an algorithm for the general case.

Here is an n=4 solution.  You should recognize it as a 4-bit binary counter
which toggles only one bit per count.  I'll conjecture that any such counter
will produce a solution.

Take the following string of 1's and 0's three times (spaces for readability).

0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

					- Gilbert

P.S.  The above is NOT a special case of the following reply, which reports a
      general solution.

Take the binary expansion of

	    B
	B (B (B-2)+1)		 lcm(1,2,...,n)
	-------------, with B = 2	       .
		2
	   (B-1)

					- Gilbert