wu :: forums - Print Page


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

        riddles >> medium >> Binary string reduction
        
(Message started by: JocK on May 27^th, 2006, 3:57am)

Title: Binary string reduction
Post by JocK on May 27^th, 2006, 3:57am

Starting from a string of 0's and 1's, one is tasked to reduce the string to a string containing only a single 1. This reduction needs to be done via repeatedly inverting triplets of two neighbouring 1's and a 0:

110 --> 001
011 --> 100

So, one can reduce the string 11001011 as follows:

11001011 --> 00101011 --> 00101100 --> 00110000 --> 00001000

One might ask the question: how many strings can be reduced in this way?

Of all the strings containing three 1's and starting and ending with a 1, precisely two can be reduced:

1011 --> 1100 --> 0010
1101 --> 0011 --> 0100

Similarly, of all the strings containing four 1's and starting and ending with a 1, three can be reduced:

101011 --> 101100 --> 110000 --> 001000
110011 --> 110100 --> 001100 --> 010000
110101 --> 001101 --> 000011 --> 000100

Of all the strings containing N 1's (N > 3) and starting and ending with a 1, how many can be reduced?