Successive Zeros

How many seven-digit sequences of 0s and 1s are there that have a block of three successive 0s but do not have a block of four or more successive 0s?
Source: mathcontest.olemiss.edu 2/17/2014

SOLUTION
Seven-digit binary sequences start from 0000000 to 1111111, in decimal from 0 to 127.
There are 5 possible locations for a block of three successive zeros
1) 000\text{- - - -}
2) \text{-}000\text{- - -}
3) \text{- -}000\text{- -}
4) \text{- - -}000\text{-}
5)  \text{- - - -}000
We examine each case in details.
1) 000\text{- - - -}
After putting a 1 at the end of the block of three successive 0s, 0001\text{- - -}, the three remaining bits can take on 8 possible values from 000 to 111. Case 1 has 8 sequences that meet the requirement that they have a block of three successive 0s but do not have a block of four or more successive 0s.
2) \text{-}000\text{- - -}
After sandwiching the block with two 1s, 10001\text{- -}, the two remaining bits can take on 4 possible values from 00 to 11. Case 2 has 4 sequences.
3) \text{- -}000\text{- -}
After sandwiching the block with two 1s, \text{-}10001\text{-}, the two remaining bits can take on 4 possible values from 00 to 11. Case 3 has 4 sequences.
4) \text{- - -}000\text{-}
After sandwiching the block with two 1s, \text{- -}1001, the two remaining bits can take on 4 possible values from 00 to 11. Case 4 has 4 sequences.
5) \text{- - - -}000
After putting a 1 at the beginning of the block, \text{- - -}1000, the three remaining bits can take on 8 possible values from 000 to 111. Case 5 would have 8 sequences but for sequence 0001000 which is a duplicate of Case 1.

Total =8+4+4+4+7=27

Answer: 27

Advertisements

About mvtrinh

Retired high school math teacher.
This entry was posted in Problem solving and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s