|
     
|
Question: 1 > -1 Take a finite sequence of numbers 1 and -1 with length 2^k (k is natural). The next sequence is made by multiplying each number by the next one; the last is multiplied by the first. Prove that eventually the sequence will contain only ones. For example, if one begins with 1, -1, 1, 1 the next sequence would be -1, -1, 1, 1 and the next would be 1, -1, 1, -1 then -1, -1, -1, -1 and finally 1, 1, 1, 1. Answer: Let A_0 denote the series of 1's and -1's of length 2^k.
Let the series of 1's and -1's A_(i+1) denote the (i+1)-th set constructed
from series A_i for natural i > 0.
Let the j-th number (either a 1 or a -1) of series A_i be denoted by A_(i,
j), where j = 1, 2, ..., 2^k. For j > 2^k, let A_(i, j) be the element of
A_i where j "wraps around." Or, in other words, A_(i, j) = A_(i, (j-1 mod
2^k) + 1).
For any i >= 0 and j = 1, 2, ..., 2^k:
- A_(i+1, j) = A_(i, j) x A_(i, j+1)
- A_(i+2, j) = A_(i+1, j) x A_(i+1, j+1) = A_(i, j)^1 x A_(i, j+1)^2 x A_(i,
j+2)^1.
So, for i < 2^k, A_(i, j) = Product_{m=0, 1, 2, ..., i} A_(0, j+m) ^ (i over
m). In words, the j-th element of the i-th series consists of multiplying
the m-th element of A_0 a number of N times, where N is the binomial
coefficient (i over m), or i! / ( m! x (i - m)! ). Because i < 2^k, the
"wrapped" numbers of A_0 don't "collide".
A_(2^k, j) = Product_{m=0, 1, 2, ..., 2^k} A_(0, j+m) ^ (2^k over m). Now,
there is exactly 1 "collision": element j+0 is the same as element j+2^k.
If you look at the exponents of the elements of A_0 in the formula for
A_(2^k, j), you can see that all exponents are even.
The exponent of A_(0, j) is even (1 from j+0 and 1 from j+2^k makes 2).
The other exponents are even because the binomial coefficient for (2^k over
m) is even for all m = 1, 2, ..., 2^k -1. This can be proved by induction.
Thus, if you construct the 2^k-th series from A_0, you are guaranteed to
have a series A_(2^k) that consists of 1s only (an even exponent of -1
always yields +1.) It is easy to see that if a series consists of 1s only,
all succeeding series will also consist of 1s only.
QED.
-Ron L.J. van den Burg
|
