String length differences
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. Give this maximum.
The answer is 82.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
00000000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100000000001000000000010000000000100000000001000000000010000000000100000000001000000000010000000000
There are 92 1's in the long string, the 0's are all in strings of 10. 92-10= 82
The idea is to maximize the number string of 1's but you need a few of them to separate the 0's so you don't get too many of them together.
Beginning with 50 zeros 100 ones 50 zeros, call this {50,100,50} Difference = 50
take a 1 and break the zeros into 3 groups, {33,99,33,1,34} Difference = 65
do this again so you have two single 1's and 4 groups of zeros, {25,98,25,1,25,1,25} Difference =73
Let x=the number of single 1's. The long string of ones will have 100-x. The strings of zeros will have 100/(x+2) if this isn't a whole number at least one of these will round up so the longest string of zeros is ceiling(100/(x+2))
The function to maximize is then f(x)=100-x-ceiling(100/(x+2)) which happens when x=8. f(8)=82.