Solution to Problem (1) by Gareth McCaughan:

I accepted this solution after some thought:

The conjecture on your web page about taking differences of digits is true.
Suppose to begin with that all digits are 0 or 1. Then after
t iterations you have, mod 2, a_new(k) = sum {0..t} of (t choose r)
times a(k+r mod n).

1. If n is a power of 2, then take t=n and note that all those
binomial coefficients are even other than (n choose 0)
and (n choose n), and that those two catch the same a(k),
so to speak; so all the a_new(k) are 0. That was all
assuming that the digits are 0 or 1, but notice that the same
argument works with the (digits mod 2), so we've proved
that after iterating n times all your digits are even. So do it
again and get all the digits to be multiples of 4, then again
making them multiples of 8, and so on until you reach a
power of 2 larger than any of the original digits, at which
point all the digits must equal 0. So if n is a power of 2,
you must end up with the all-zero string.

2. If n is odd and > 1, start with any string of 0s and 1s other than
all-0 or all-1. I claim you never end up at all-0. Why? Because
the only possible predecessors of all-0 are all-0 and all-1, and
there is *no* possible predecessor of all-1 (easy exercise for
the reader). So when n is odd and > 1, there must be some possible
fate other than all-0.

3. If n is neither odd nor a power of 2, write it as m*2^k where
m is odd. Take any string S of 0s and 1s of length m, other than
all-0 and all-1, and repeat it 2^k times. Now the t'th iterate of
this string is the t'th iterate of S, repeated 2^k times (easy
exercise for the reader), and *that* is never all-0. So when
n is an odd number > 1 times a power of 2, there must be some
possible fate other than all-0. We're done.


Back to Maths Corner