Consider the sequence 0100111100
There are 5 zeroes and 5 ones in this sequence.
The longest string of ones is 4.
The longest string of zeroes is 2.
The difference in string lengths is 2.

Create a sequence consisting of 100 zeroes and 100 ones which maximizes the difference in lengths between the longest string of 1's and the longest string of 0's.

Find a formula for the maximum difference in string lengths with n zeroes and n ones.

Let's find the formula and then apply it to n = 100.

Let's say the longest string of 1's is greater than the longest string of 0's. If you start out with the 1's in the middle, separating two groups of 0's that are as near as possible in length, what you have is n 1's and ceil(n/2) 0's in a row and the difference is n - ceil(n/2), where ceil(x) is the ceiling function: the smallest integer that is not less than x, so for example, ceil(2.1) = 3.

By removing one 1 at a time from the main group, the 0's can be divided into more, smaller groups.  If the largest group of 1's is x in number, then the largest group of 0's will have ceil(n/(n-x+2)), and the difference will be x - ceil(n/(n-x+2)).

Wishing to maximize this amount, let's initially ignore the ceiling function, and take a derivative and set it to zero:

1 - n / (n-x+2)^2 = 0

(n-x+2)^2 = n

n-x+2 = sqrt(n)

x = n + 2 - sqrt(n)

We then choose to round x up or down (ceiling or floor).  Let's see what the results are, given that the difference is x - ceil(n/(n-x+2)):

If n is a perfect square the ceiling and floor are equal.  For example, at n=25, x=22, and the difference is 22-ceil(25/5) = 22 - 5 = 17.  (The string is 00000111111111111111111111100000100000100000100000, to take one of the four possibilities.)

Applied to 100, x=102-10=92, and the difference is 92 - ceil(100/10) = 92 - 10 = 82. If either 91 or 93 were chosen as the largest string of 1's, the best difference you could get would be 81 in either case.

In instances where n is not a perfect square, it still does not matter how you round x, up or down, as there is always leeway-- for example for n = 10, where you can't get better than 5, and that's from x = 7 through x = 10. A larger example: for n=101, the maximum difference of 82 is achieved with x's ranging from 90 through 95, so it doesn't matter if you round x down to 92 or up to 93.

So an answer to part 1 is a string of 92 1's and 8 individual 1's separating 10 groups of 10 0's:

000000000011111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111000000
000010000000000100000000001000000000010000000000100000
00000100000000001000000000010000000000

The answer to the second part is

ceil(n + 2 - sqrt(n)) - ceil(n/(n-(n + 2 - sqrt(n))+2))

which can be simplified to

ceil(n + 2 - sqrt(n)) - ceil(sqrt(n))

It seems to simplify further as

n + 2 - ceil(2 * sqrt(n))

Edited to break apart the long string above.

Edited on February 15, 2005, 3:26 pm

Posted by Charlie on 2005-02-15 15:23:00