Covering binary strings

[franktaw at netscape.net]

First off, there are effectively A024206(n+1) arithmetic progressions, 
given that we only care about the intersection of the progression with 
1..n.  So a(n) must be large enough that Sum_{k=0}^a(n) 
C(A024206(n+1),k) >= 2^n.  Since A024206 grows quadradically, this 
shows that at least lim_{n->infinity} a(n) = infinity.

It is also easy to show that a(n) <= ceiling(n/2).  Any string with up 
to ceiling(n/2) bits on can be made by combining single bits, while 
anything with more can be made by turning all bits on (sequence k*n), 
and then turning off the 0 bits.  This bound is achieved for n <= 6; 
however, a(7) = 3, not 4.

Franklin T. Adams-Watters


-----Original Message-----
From: stefan.steinerberger at gmail.com

  Dear seqfans,

 I invented the following problem some time ago and have
 unfortunately been unable to solve it. Perhaps some of
 you can provide a little insight, a solution or an idea.

 The problem is best described as a little game. You are
 given a string consisting of "0" and "1" of length n. An
 example would be 1000101 (in this case n = 7).

 Now you start with your own personal string who in the beginning
 has the form 00...00 (n times 0). Now you change your personal
 string by "applying arithmetical progressions" in such a manner
 that you will eventually obtain the string given (1000101).

 To clarify what I mean by "applying arithmetical progressions":
 You can chose any arithmetical progression k*x+d with k,d
 being integers. Then you look at the intersection of
 {1,2,3...,n} and the image set of that progression (where x
 takes every integer value). For any element m in that intersection
 you move to the mth position of the string and change its value
 (0 becomes 1 and 1 becomes 0). How many arithmetical progressions
 do you need before you get the "goal string" given?

 In our example we only need two arithmetical progressions:
 0000000 - we use the arithmetical progression
 6*x+1 (...-11, -5, 1, 7, 13, ...), therefore change the string at
 the first and at the seventh position and get 1000001.
 Now let us use the arithmetical progression 7*x + 5 and we
 get 1000101 which is the goal string.

 Now the question: For any natural number n, what is the
 smallest number of arithmetical progressions you need to
 get from the start string 00...00 to any string of length n?

 The question can be easily answered for n=2 as there are
 only four possible "goal strings". 00 is the start position
 and we don't even need a single arithmetical progression
 to get there. For 01 we only need to use 3*x+2. We get 10
 by applying 3*x+1 once. 11 is obtained by using the
 arithmetical progression x.
 Thus we only need to apply one arithmetical progression
 to cover all strings of length 2. But what about other n?

 (It can be easily seen that you need at most n progressions
 to cover all strings of length n, but I expect the smallest number
 to be somewhere around sqrt(n)).

 Perhaps someone can offer a proof, a proof of a special case,
 some numerical data or a comment.

 Best wishes,
 Stefan


________________________________________________________________________
Check Out the new free AIM(R) Mail -- 2 GB of storage and 
industry-leading spam and email virus protection.