[seqfan] Re: A puzzle from Emissary

Andrew Weimholt andrew.weimholt at gmail.com
Wed Nov 30 00:25:38 CET 2011


I can prove that at most 2 transforms are needed to reach 1. (i.e. that C=2).

let k(x) be the number of 1's in the binary representation of x.

Lemma 1:
  Let P(n) be the following proposition:

    Any x, where 2^(n-1) <= k(x) <= 2^n
    can be transformed into 2^n.

  Then if P(n) is true, P(n+1) is true
  and by induction,  P(m) is true for all m >= n.

Proof:

  Assume P(n) is true. Then all numbers with anywhere
  from 2^(n-1) to 2^n 1's in their binary representation
  can be transformed into 2^n.

  P(n+1) states that all numbers with anywhere from
  2^n to 2^(n+1) 1's can be transformed into 2^(n+1).

  Let M be any such number, and let it be represented
  by the binary string S.

  Then we can splite S into two substrings,
  S1 and S2, with x 1's and y 1's respectively,
  where 2^(n-1) <= x <= 2^n
  and 2^(n-1) <= y <= 2^n

  by P(n), the numerical values corresponding
  to S1 and S2 can each be transformed into 2^n.
  Therefore M can be transformed into
  2^n + 2^n = 2^(n+1)

Now we can prove that P(n) is true for n=4.
Along the way, we will also prove that all numbers
for which k(x) < 8 can be transformed to a power of 2.

For k(x) = 1, we already have a power of 2
For k(x) = 2, we ignore the zeros and simply add
the 1's:  1+1 = 10 (base 2)

For k(x) = 3, we either have a substring "10" or
x=7. In the former case, we have
10 + 1 + 1 = 100 (base 2)
For x=7, we have
11 + 1 = 100 (base 2)

For k(x) = 4, we again can ignore the zeros and
simply add the 1's:   1+1+1+1 = 100 (base 2)
But we will also need to show that for
any x with k(x) = 4, x can be transformed to 8.
The binary representation of x must contain
one of the following substrings:
{"100", "101", "110", "111"},
If we have "100", then we also either have
"10" or "11"
100 + 10 + 1 + 1 = 1000 (base 2)
100 + 11 + 1 = 1000 (base 2)
If we have "101", then we also either have
"10" or "11"
101 + 10 + 1 = 1000 (base 2)
101 + 11 = 1000 (base 2)
If we have "110", then
110 + 1 + 1 = 1000 (base 2)
and if we have "111", then
111 + 1 = 1000 (base 2)

For k(x) = 5, only x=31 cannot be transformed
to 8, but it can be transformed to 16 via
1111+1 = 10000 (base 2)
For all other values of x, we will have at least
one zero in our binary strings.
100 + 1 + 1 + 1 + 1 = 1000 (base 2)
101 + 1 + 1 + 1 = 1000 (base 2)
The only case that is not yet covered is
that of having all the zeros to the right of
all the 1's, in which we acheive 8 by
11 + 11 + 10 = 1000 (base 2)

For k(x) = 6, we can split the binary string
of x into two strings, with numerical values
a and b, such that k(a) = k(b) = 3.
And since a and b can each be transformed
to 4, there exists a transform of x to 8.

For k(x) = 7,  we can split the binary string
of x into two strings, with numerical values
a and b, such that k(a) = 3 and k(b) = 4.
And since a and b can each be transformed
to 4, there exists a transform of x to 8.

For k(x) = 8, we can split the binary string
of x into two strings, with numerical values
a and b, such that k(a) = k(b) = 4.
And since a and b can each be transformed
to 4, there exists a transform of x to 8.
BUT ALSO:
since a and b can each be transformed
to 8, there exists a transform of x to 16.

For 8 <= k(x) <= 16 and k(x) != 9
we can split the binary
string into a and b with k(a) and k(b)
in {4,6,7,8} (note 5 is omitted)
Therefore, for any x in this set,
x can be transformed to 16.

Therefore if we can show that for
any x with k(x)=9, we can transform x to 16,
then we have transformations to 16 for
every x in 8 <= k(x) <= 16, and by Lemma 1,
C=2.

For k(x) = 9, we split  the binary string into
a and b with k(a) = 5  and k(b) = 4
If we can avoid a=31, then we can transform
a to 8 and b to 8, and therefore we can
transform x to 16.

If we cannot avoid a=31, then the string for
x must be "111111111", in which case
we can still transform to 16 via
111 + 11 + 11 + 11 = 10000 (base 2)

Therefore C=2.

Andrew



More information about the SeqFan mailing list