Author |
Topic: Binary string reduction (Read 406 times) |
|
JocK
Uberpuzzler
Gender: 
Posts: 877
|
 |
Binary string reduction
« on: May 27th, 2006, 3:57am » |
 Quote  Modify
|
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?
|
| « Last Edit: May 27th, 2006, 3:59am by JocK » |
 IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print