All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Choose your neighbor (Posted on 2010-04-23) Difficulty: 4 of 5
How many 12-digit binary sequences exist with no two ones(11) neighboring each other?.
How many 12-digit binary sequences exist with no 3 ones(111) neighboring each other?.
Leading zeros allowed.

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Structure | Comment 1 of 3

Building up to a 12-digit sequence it becomes clear the the first case is Fibonnacci.

1-digit has 2 ways: 0, 1

2-digits has 3 ways: 00, 01, 10

3 digits has 5 ways: put a 0 at the end of the 2-digit ways and a 01 at the end of the 1-digits ways.  3+2=5

n-digits has the sum of the n-1 and n-2-digit ways: put a 0 at the end of the n-1 digit ways and a 01 at the end of the n-2 digit ways.

The sequence (starting with n=0) goes 1,2,3,5,8,13,21,34,55,89,144,233,337

The second case is similar.

This time the n term is the sum of the n-1 (append 0) the n-2 (append 01) and the n-3 (append 011) terms.

The sequence goes 1,2,4,7,13,24,44,81,149,274,504,927,1705

If we want to exclude 1111 the sequence is 1,2,4,8,15,29,56,108,208,401,777,1490,2872

  Posted by Jer on 2010-04-23 13:31:07
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2019 by Animus Pactum Consulting. All rights reserved. Privacy Information