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

 Choose your neighbor (Posted on 2010-04-23)
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?.

 No Solution Yet Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 semi-analytic solution | Comment 2 of 3 |

Part 1:

A given sequence can contain zero to six 1's.

Any sequence that does not begin with a 1 can be seen as a combination of "01" groups and "0" digits. The number of such combinations containing n "01" groups is C(12-n,n).

That leaves, though, those that begin with a 1. The remaining 11 digits can then contain up to five "01" groups with the remainder as 0's. This is C(11-n,n) for n's less than 6.

` n   C(12-n,n) C(11-n,n) 0       1       1 1       11      10 2       45      36 3       84      56 4       70      35 5       21      6 6       1`

The total adds up to 377.

This program merely facilitated the calculations:

list
10        for N1s=0 to 6
20         Pieces=12-N1s
30         Tot=Tot+combi(Pieces,N1s)
40         print N1s,combi(Pieces,N1s),
50         Pieces=11-N1s
55         if Pieces>=N1s then
60          :Tot=Tot+combi(Pieces,N1s)
70          :print combi(Pieces,N1s)
75         :else print
80        next
200   print Tot
OK

Verification:

DECLARE SUB choose (w!)
DIM SHARED d(12), ct

choose 1
PRINT ct

SUB choose (w)
IF w = 1 THEN
stp = 1
ELSE
stp = 1 - d(w - 1)
END IF
FOR c = 0 TO stp
d(w) = c
IF w = 12 THEN
ct = ct + 1
ELSE
choose w + 1
END IF
NEXT
END SUB

resulting in 377.

Part 2:

This is harder. I don't have an analytic solution, just this exhaustive search:

DECLARE SUB choose (w!)
DIM SHARED d(12), ct

choose 1
PRINT ct

SUB choose (w)
IF w = 1 OR w = 2 THEN
stp = 1
ELSE
stp = 1 - INT((d(w - 1) + d(w - 2)) / 2)
END IF
FOR c = 0 TO stp
d(w) = c
IF w = 12 THEN
ct = ct + 1
ELSE
choose w + 1
END IF
NEXT
END SUB

finds 1705 sequences without "111".

 Posted by Charlie on 2010-04-23 14:06:46

 Search: Search body:
Forums (0)