wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Longest Binary Number
        
(Message started by: ThudanBlunder on Apr 21st, 2007, 6:58pm)
Title: Longest Binary Number
Post by ThudanBlunder on Apr 21st, 2007, 6:58pm
What is the longest binary number which does not contain any 3-bit sequence more than twice or the sequence 11?
Title: Re: Longest Binary Number
Post by tiber13 on Apr 22nd, 2007, 1:04pm
? 1010101010101010101....?
Title: Re: Longest Binary Number
Post by towr on Apr 22nd, 2007, 1:27pm

on 04/22/07 at 13:04:16, tiber13 wrote:
? 1010101010101010101....?
That contains the sequence 101 and 010 a lot more than twice.

There are 8 three bit sequences, two contain 11, so that leaves 6. Each can occur at most twice, and they overlap with two. So at most the string is 14 characters long.
Another more fruitfull approach is to consider we must always have one or two 0's between every two 1's. But then any internal 1 will be part of the sequence 010, and we can have only two of those.
Tentatively, [hide]101001001[/hide]
Title: Re: Longest Binary Number
Post by tiber13 on Apr 22nd, 2007, 1:31pm
? sorry, but i dont understand binary, but i do know statistics, 5/4 people are terrible at fractions
Title: Re: Longest Binary Number
Post by towr on Apr 22nd, 2007, 1:33pm

on 04/22/07 at 13:31:24, tiber13 wrote:
? sorry, but i dont understand binary, but i do know statistics, 5/4 people are terrible at fractions
Hmm, yes, I always forget there are 10 kinds of people: those that understand binary and those that don't. :P

Instead of binary, you can consider decimal (i,.e. regular) numbers which only have 1's and 0's.
Title: Re: Longest Binary Number
Post by Grimbal on Apr 22nd, 2007, 2:52pm
Would 10101 contain 2 times the sequence 101?
Title: Re: Longest Binary Number
Post by Grimbal on Apr 22nd, 2007, 3:07pm
I get [hide]10001000101[/hide] or reversed.
Or [hide]100010001010[/hide] depending on how you count the multiplicity.
Title: Re: Longest Binary Number
Post by Eigenray on Apr 22nd, 2007, 4:29pm
There are 6 permutations of [hide]10100100001[/hide] that should also work.

Consider the lengths of the runs of 0s between adjacent 1s.  [hide]There are no more than 3 runs.
If any has length 4, the others have length http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 2, and we can't have more than 2 of length http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 2.  So if some run has length 4, the longest string has lengths (4,2,1).
Otherwise, there longest it could be is (3,3,1).[/hide]
So there are a total of 9 strings with length [hide]11[/hide], and none longer.
Title: Re: Longest Binary Number
Post by rmsgrey on Apr 23rd, 2007, 7:18am

on 04/22/07 at 13:27:56, towr wrote:
There are 8 three bit sequences, two contain 11

technically, three contain 11  - 110, 011 and 111
Title: Re: Longest Binary Number
Post by Grimbal on Apr 23rd, 2007, 8:21am
Technically?  As opposed to what?
Title: Re: Longest Binary Number
Post by towr on Apr 23rd, 2007, 8:46am

on 04/23/07 at 07:18:41, rmsgrey wrote:
technically, three contain 11  - 110, 011 and 111
Oops.. Yeah, that was careless of me to miss.
Title: Re: Longest Binary Number
Post by rmsgrey on Apr 24th, 2007, 6:17am

on 04/23/07 at 08:21:36, Grimbal wrote:
Technically?  As opposed to what?

As opposed to a wild estimate. Two, plus or minus one is reasonable compared to some of the estimates I've seen over the years...


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board