Question

I think I have this one down, but I want to be sure.

"How many bit strings of length 8 contain either three consecutive zeros or four consecutive ones?"

I got 160.

Answer 1

so can it have 6 consecutive ones for example?

Answer 2

Yes

Answer 3

Really, what i'm not sure about, is finding the number of permutations that have both 4 consecutive ones and 3 consecutive zeros.

Answer 4

too many commas :/

Answer 5

00011110
00011111
00001111
10001111
11110001
11110000
11111000
01111000

8 have both

Answer 6

oh i see why!

Answer 7

for exactly 3 consecutive
000 1 ????
1 000 1 ???
?1 000 1??
?? 1 000 1?
??? 1 000 1
????1 000

first one has 15 possibilities
second one has 7
third one has 8
fourth one has 8
fifth one has 7
last one has 15

therefor a total of 60 ways
i bet there is a much easier way to do this

Answer 8

that was wrong
first and last have 14
now i get 58

Answer 9

i am lousy at this, but it looks right to me because is says "three consecutive zeros" not
"three consecutive zeros and the rest ones"

Answer 10

The way I'm reading the problem,
00000000
would also count because it has a string of 3 consecutive zeros.

Answer 11

i bet kinggeorge has a much better answer

Answer 12

i was reading as "exactly three" but i could easily be wrong

Answer 13

I don't have a better answer yet. Every time I've encountered this problem, any nice solution evades me.

Answer 14

yeah i was just counting like a donkey

Answer 15

@satellite73: @johnwessolomon88 is not interpreting the question as excactly 3 cons. zeros, or exactly consecutive 4 ones.

Answer 16

If we're allowing things like 00000000, it would be easier to find how many have no consecutive zeros, and some amount of 2 consecutive zeros, and subtract that from \(2^8\).

Answer 17

well then maybe it is easier
the consecutive zeros could be in first three slots, second 3, third 3, fourth 3 or fifth 3 slots. if you do not care what is in the others, then it would be \(5\times 2^5\)

Answer 18

That's a better way to do it than what I was trying to do.

Answer 19

oh no that was wrong, because that would include a bunch with 4 and then you would have to subtract

Answer 20

@KingGeorge i like your way better
i thought this was easy but it is going to be complicated when we try to figure out repeats

Answer 21

just count/calculate how many strings have no more than 2 consecutive zeros,
AND no more than 3 consecutive ones ... and then do 256 minus that.

Answer 22

seems an odd way to interpret the question in my mind. if it says "3 or 4" and you interpret that to mean "three or four or more" then why include the 4?

Answer 23

i would have thought it meant "exactly three or exactly four"

Answer 24

Let's see then. With no consecutive zeros, we have quite a few possibilities.
Case 1: no zeros. 1 possibility
Case 2: 1 zero. 8 possiblities
Case 3: 2 zeros. \(\binom{8}{2}-7=21\) possibilities
Case 4: 3 zeros. \(\binom{8}{3} -7-5-4-4-4-4-5=23\) (very possibly wrong)
Case 4: 4 zeros. 2 possibilities.

Sum these together, we get 55.

Answer 25

Sorry, now we need to find how many have 2 consecutive zeros before moving on.

Answer 26

Now we need to find how many have exactly two consecutive zeros.
Case 1: 2 zeros. \(7\) possibilities
Case 2: 3 zeros. \(5+4+4+4+4+5=26\)
Case 3: 4 zeros. \(10+6+6+6+6+6+10=50\)
Case 5: 5 zeros. \(7+2+3+4+3+2+7=28\)
Case 6: 6 zeros. \(1\)

Add these up as well, and I get 55+112=167, so now we subtract this from \(2^8\) and we finally get \[2^8-167=89\]I hope that's correct :/

Answer 27

I remember where I've seen this before now. These are hidden in the fibonacci numbers.

Answer 28

Now that I remember the pattern, and we already know that there are 8 that have both 3 consecutive zeros and 4 consecutive ones, I believe the final answer should be \[89+55-8=136\]

Answer 29

Allow me to check with a more direct method now.

Answer 30

ok i went to bed and got up realizing that i had misunderstood the question
3 or more consecutive zeros should be \(6\times 2^5\) i think
and 4 or more consecutive ones should be \(5\times 2^4\) and the last thing to calculate would be what we have counted twice

Answer 31

that would be how many have 4 consecutive ones and 3 or 4 consecutive zeros i believe

Answer 32

With those numbers you get 264 possibilities which is clearly too much. @satellite73

Answer 33

i do have to subtract off something

if the ones are in the first four slots there are 4 remaining to house either 3 or 4 consecutive zeros
3 ways to do this

Answer 34

And my more direct method is getting a different solution than what I was getting previously.

Answer 35

likewise if the ones are in the last 4 slots

Answer 36

and if the ones are in slot 2, 3, 4 , 5 that leaves 6,7, 8 to house 3 zeros, likewise if they are in slot 4 5 6 7

Answer 37

so by my probably incorrect count, there would be \(6\times 2^5+5\times 2^4-6-2\)

Answer 38

And that gives you 264 if my math is correct.

Answer 39

yes it does

Answer 40

i would not bet a stick of gum on this but if it is wrong i am curious to know why

Answer 41

I think you're counting things like 00010000 more than once.

Answer 42

yeah you are probably right

Answer 43

oh no i don't think so

Answer 44

i count that once in the computation of \(5\times 2^6\)

Answer 45

And with my more direct method, I'm now getting \[89+27-8=108\]instead of my previous solution where I tried to take a shortcut.

Answer 46

3 zeros in the first slot, and who cares what in the others

Answer 47

oh damn you are right.

Answer 48

OK.. I literally counted every single bit string that is not possible

I think that's 73.

So the answer should be 256-73 = 183

183 strings have atleast 3 consecutive zeros, or 4 consective ones

Answer 49

You're missing at least one string in that @PaxPolaris
01010101

Answer 50

wow this is way more complicated than it thought
number of ways you 3 or more consecutive 0s is 107 apparently it is \(2^8\)- tribononacci 11
new one one me
number of ways for 4 or more consecutive 1s is 48

Answer 51

*new one on me

Answer 52

i missed more....

Answer 53

so it is \(107+48-\text{intersection}\) which should be possible

Answer 54

reference here
http://oeis.org/A050232
and here
http://oeis.org/A050232

Answer 55

rather here
http://oeis.org/A050231

Answer 56

So a final answer of 147 in that case. Fascinating. I've got to look at this some more.

Answer 57

turned out to be way harder than i thought. i did a tiny bit of googling and came up with no snap method, so i think it is not trivial to compute

Answer 58

That's not surprising to me in the slightest.

Answer 59

here is a similar question and something like an answer
http://answers.yahoo.com/question/index?qid=20101213100138AADdpyy

Answer 60

You can take about half of the shortcut I tried to take. See here for example. http://en.wikipedia.org/wiki/Fibonacci_number#Occurrences_in_mathematics

Answer 61

and here is a much clearer answer
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=print;num=1187898466

Answer 62

clearer in the sense that after i wake up tomorrow and look at it i believe after some thought i will be able to understand it
gotta love openstudy

Answer 63

I had only seen the relation for what they're would call Z2(n), and that corresponds to the fibonacci numbers. That explains why I remembered those.

Answer 64

This is awesome - way to go guys :)