On 29/09/2015 21:16, James Propp wrote:
Conjecture: In each orbit, there are exactly as many 0s as 1s.
The conjecture is correct. With an odd number of bits, there is only one orbit, containing all the m-bit numbers and hence certainly having the same number of 0s as 1s. With an even number of bits: suppose we have 2n bits, and for any n-bit strings a,b define <a|b> to be reverse(a) concat b. Then the successor of <a|b> is <b+1|a> except that if b=N:=2^n-1 then it's <0|S(a)> instead, where S(a) = reverse(reverse(a)+1). So then e.g. the orbit of <0|0> goes <0|0> <1|0> <1|1> <2|1> etc., ending up with ... <N|N-1> <N|N> <0|0>. A little more generally, the orbit of <0|b> goes <0|b> <b+1|0> <1|b+1> ... <N-b|N> <0|S(N-b)> so now we need to understand the iteration b -> S(N-b). The first operation, b -> N-b, flips all the bits. Then the second flips bits from the left up to and including the first 0. Together, this is the same as: scan from the left until finding the first 1, then flip all bits after that. Now note that this is obviously an involution; it has order 1 if b=0 or b=1, and order 2 otherwise. So. The orbits are as follows. <0|0> <1|0> <1|1> <2|1> ... <N|N-1> <N|N> <0|1> <2|0> <1|2> <3|1> ... <N|N-2> <N-1|N> for b=2..N-1: <0|b> <b+1|0> <1|b+1> ... <N|N-b-1> <N-b|N> ... <0|b'> <b'+1|0> <b'+1|1> ... <N|N-b'-1> <N-b'|N> where b' = S(N-b) = the result of flipping all bits in b after the first 1. (Sanity check: the orbit beginning <0|0> has size 2N+1; the orbit beginning <0|1> has size 2N-1; the orbit beginning <0|b> has size 2(N-b)+1 + 2(N-b')+1, and if the first 1-bit in b is in position 2^k then b+b' equals 2^(k+1) + (2^k-1), and there are 2^(k-1) such orbits. Total is 2N+1 + 2N-1 + sum {k=1..n-1} of (4N+2-2^(k+2)-2^(k+1)-2)2^(k-1) and with a little pain one may verify that this equals 2^(2n).) OK, so now let's count bits. Each orbit or half-orbit has the form <0|b> <b+1|0> ... <N|N-b-1> <N-b|N> and now we need merely observe that this is invariant under the following operation: replace each <a|b> with <N-b|N-a> and take the entries in reverse order. And this interchanges the counts of 0-bits and 1-bits, which therefore must be equal; we're done. -- g