[seqfan] Switching Binary Digits And Runs Of Digits

[Leroy Quet]

I posted the text below to sci.math. It isn't strictly about sequences (except finite binary sequences). But it is inspired by sequence A166166. (Maybe someone could up with a more concise way to express the idea of exchanging runs, which seems to me to be intuitively easy to understand, but difficult to express in words.)

Also I post this because it makes for a fun puzzle.

----

Let's say we start with a binary string of finite length. I will use 0's and 1's for the characters in the string, but any two distinct symbols will do. (A string may begin with either a 0 or a 1.)

We then alternate between transformation A and transformation B of the string, starting with either A or B, and not ever following transformation A immediately with transformation A, and not ever following transformation B immediately with transformation B.

A: Either replace any 0 in the string with a 1, or replace any 1 in the string with a 0. In other words, flip exactly one digit.

B: (More difficult to describe.) Rewrite the string with each run (of either digit b) of the kth-longest distinct run-length replaced with a run of digit b of a length equal to that of the k-th shortest distinct run-length, where k is any integer between 1 and the number of distinct run-lengths. In other words, let b(k) be the kth largest distinct run-length (considering both runs of 0's and of 1's) in the string yet to be transformed in this step. Let r be the number of distinct run-lengths in the string. Rewrite the string by replacing each run (of any given digit) of length b(k) with a run (of that same digit) of length b(r+1-k). 
(A binary string alternates between "runs" each completely of 1's and runs completely of 0's. No two runs of the same digit are consecutive.)

(An example for transformation B: Let us say we have the string 0010000110. So, there is a run of length 2, followed by a run of length 1, followed by a run of length 4, followed by a run of length 2, followed finally by a run of length 1. The run-lengths are therefore (2,1,4,2,1). The distinct run lengths, written in order, are therefore (1,2,4).
So, we replace all runs of length 1 with runs (of the same digit ) of length 4, because 1 is the smallest run-length, and 4 is the greatest run-length. Then we replace all runs of length 2 with runs of length 2 (leaving those runs unchanged), because 2 is both the 2nd longest run-length and the second shortest. And finally, we replace all runs of length 4 with runs of length 1.
And we get:
0011110110000.)

The first question: Is it always possible to transform, through a series of such steps, any string of 4 or more digits to any other string of 4 or more digits?
(I don't know the answer to this question.)

Now, let us say we have the relatively short string:
010011.

We can "reverse" the order of the digits easily either by starting with transformation A or with transformation B.

Start:: 010011
B: 001101
A: 001100
B: 001100
A: 101100
B: 110010

Or:

Start: 010011
A: 110011
B: 110011
A: 110010

Simple stuff.

But what if we have a string of n(n+1) digits, made by:
One 0, followed by one 1, followed by two 0's, followed by two 1's, followed by three 0's, followed by three 1's,... followed by n 0's, followed finally by n 1's?

Is there a simple algorithm that "reverses" the order of the digits that works for all n >= 1?

(I don't know the answer to this question. I don't even know if this is possible for all n.)

It should be noted -- although this is obvious if you play with this -- that the binary string can alter in length whenever transformation B is applied.
In regards to this and the first question, a clarification:  The starting string and the target string can be of different lengths, as long as both the start and the finish both have 4 or more digits. (At least 4 digits are necessary because strings of length 3 only produce strings of length 3; and strings of length 2 produce only strings of length 2, and strings of length 1 produce only strings of length 1 -- so you cannot transform a string of 3 digits, say, to an arbitrary string of any other length.)


Thanks,
Leroy Quet

 
[ ( [ ([( [ ( ([[o0Oo0Ooo0Oo(0)oO0ooO0oO0o]]) ) ] )]) ] ) ]