wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Four Numbers Game
        
(Message started by: Obob on Oct 31^st, 2004, 5:38pm)

Title: Four Numbers Game
Post by Obob on Oct 31^st, 2004, 5:38pm

Draw a square. Put any four integers at the four corners of the square. Now label each side of the square with the absolute value of the difference of the numbers on its vertices. Connect the four midpoints of the sides of the square to construct another square whose vertices are the midpoints of the sides of the original square. Label each of the sides of this new square with the absolute value of the difference of their edges. Continue this process until all the sides are labeled 0.

An example is probably in order. Suppose that we label the vertices of the original square as 3,5,2,1, in that order going clockwise around the square. The new square would be labeled 2,3,1,2, and the square inside of that one would be labeled 1,2,1,0. Continuing, we have the labels 1,1,1,1, and 0,0,0,0.

Here are some questions about the four numbers game, in varying difficulties:

1. (Medium) Prove that the game always ends. That is, after some finite number of iterations all the labels are 0.

2. (Medium) Prove that there are games of arbitrarily long length. In particular, for any positive integer N there is an initial configuration such that it takes exactly N iterations for the labels to be all 0.

3. (Easy) Let's play the four numbers game over the rationals. That is, take the vertex values to be rational numbers. Does the game still always end? If so, prove it. If not, find a game which does not terminate.

4. (Hard) Let's play the four numbers game over the reals. That is, take the vertex values to be real numbers. Does the game still always end? If so, prove it. If not, find a game which does not terminate.

5. (Easy-Medium, given an answer to part 4) Find the minimal Archimedian extension of the rationals Q over which there is a game which does not terminate.

6. (Probably very hard, just thought of it) Let's play the four numbers game over the p-adics Qp. Does every game end? If so, are there games of arbitrarily long length?

7. (I do not know the answer to this question; this genralization just occurred to me. It may be very hard, or very easy.) Let's play the four numbers game over a finite abelian group (simply take the difference of two group elements instead of taking the absolute value of the difference). Must every game end? If so, are there games of arbitrarily long length? It suffices to only consider cyclic groups since every abelian group is a direct product of cyclic groups; then the longest game over an abelian group is equal to the maximum length of a game over each of its factors. What about general finite groups (multiply by the inverse of a group element instead of taking the absolute value of their difference)? (infinite groups probably aren't very interesting without a concept of absolute value. I would imagine most infinite groups would have games of infinite length.)

There are clever solutions to at least the first five parts. Happy puzzling!

Title: Re: Four Numbers Game
Post by Aryabhatta on Nov 1^st, 2004, 1:27pm

wlog, we can assume the numbers are non-negative.
For the game termination over integers i.e
1) [hide] Consider the maximum of the four numbers [/hide].

Over rationals, i.e.
3) [hide] the rationals can be written as a/M,b/M,c/M,d/M and termination follows from termination of a,b,c,d [/hide].

For reals, i.e. 4) my guess of a counter-example to termination is:
[hide] Transcendental numbers. Basically the resulting numbers are linear combinations of the original numbers with integer coefficients. So looks like 'independent' transcendental numbers should do. We could probably choose the numbers cleverly enough so that at least one of the integer coefficients is non-zero [/hide].

Maybe an answer to 2 will provide insight on how to tackle 4 better.

Title: Re: Four Numbers Game
Post by Obob on Nov 1^st, 2004, 2:19pm

Nice work on 1) and 3).

For 4), try some of your favorite transcendentals. For example, try 2pi, e, 17^(1/2), and 1. I'll bet you'll be surprised.

Title: Re: Four Numbers Game
Post by Barukh on Nov 2^nd, 2004, 3:58am

It’s very interesting problem, Obob! I’ve seen only the first question a long time ago.

1.
[smiley=blacksquare.gif][hide]
Consider the parity of the four numbers. It is easy to check that after at most 4 iterations all the numbers become even. More generally, after at most 4n iterations every number is divisible by 2ⁿ. Then, if all the numbers originally are less than M, the game will end after at most 4log₂M iterations.
[/hide][smiley=blacksquare.gif]

2.
[smiley=blacksquare.gif][hide]
It took me some time to actually construct the game with the needed length. Interestingly, the result of question 1) was of no help… So: Let the four numbers be 4 consecutive Tribonacci numbers (http://mathworld.wolfram.com/TribonacciNumber.html) T_n, T_n+1, T_n+2, T_n+3. After 3 iterations, the numbers becomes 2T_n-2, 2T_n-1, 2T_n, 2T_n+1. Therefore, the game cannot last less than 3n/2 moves.
[/hide][smiley=blacksquare.gif]

4. I didn’t check this one, just a guess (also for 5).

[smiley=square.gif][hide]
Let [alpha] be the positive root of the equation x³ - x² - x – 1 = 0. Take four real numbers 1, [alpha], [alpha]², [alpha]³. The game won’t terminate. :-/

[alpha] plays the same role for tribonacci numbers as golden ratio for Fibonacci numbers.
[/hide][smiley=square.gif]

Title: Re: Four Numbers Game
Post by Obob on Nov 2^nd, 2004, 8:15am

Nice work on part 4! That is in fact the exact same solution I had, although your method of finding it was evidently completely different from mine. In my solution, I supposed that the numbers satisfied a<=b<=c<=d. Under these restraints, the next set of values will be b-a,c-b,d-c,d-a. Write down the matrix for this transformation R^4->R^4, and find its eigenvectors and eigenvalues. There is one real eigenvalue (its something like .83), and the eigenvector corresponding to this eigenvalue is your choice 1,alpha,alpha^2,alpha^3. Then the transformation acts by a scalar multiple on this vector, and so preserves the ordering of the numbers, so T^n(1,alpha,alpha^2,alpha^3)=(.83)^n(1,alpha,alpha^2,alpha^3), which will never be zero.

Title: Re: Four Numbers Game
Post by Aryabhatta on Nov 2^nd, 2004, 10:07am

Very nice, Barukh and Obob! Excellent solutions.

Title: Re: Four Numbers Game
Post by Barukh on Nov 3^rd, 2004, 11:47pm

Obob, your solution is extremely elegant and so simple! After reading it, I thought it is the first thing that should come to somebody’s mind if she is used to work with linear transformations. I ought to learn and practice more on eigenvectors and eigenvalues…

My solution for 4) was based on 2) which in turn was heavily based on empirical data. In fact, when trying by hand, I couldn’t construct any game with more than 13 moves. I tried Fibonacci numbers because they tend to form repeated sequences. This didn’t help. So, I went and used the PC. It showed the solutions with increasing number of moves. I noticed some regularities in the solutions and constructed a sequence out of them. Looking for that sequence in Sloane’s encyclopedia, I found tribonacci numbers. Finally, it was an easy exercise to prove the game length bound.

As for 4), I took [alpha] to be the limit of T_n+1/ T_n when n tends to [infty]. It is straightforward to see that it satisfies the polynomial I wrote in my previous post.

Your question 7) looks intriguing… No ideas yet.

I wonder also if questions 1)-2) allow generalization to more integers. My conjecture is that the game will end if and only if number of sides of the polygon is 2^M. Any thoughts?

Title: Re: Four Numbers Game
Post by Barukh on Nov 4^th, 2004, 5:24am

After looking at question 7) closer, I think some clarifications are needed, or the problem isn’t that interesting, or I am ignorant…

In any group, there’s no difference operation. So, I assume Obob had in mind a-b = ab^-1 – also for abelian groups. In any case, this operation is not symmetric (like the absolute difference).

Therefore, we need to order the adjacent elements. To make the moves symmetric, assume one iteration computes ab^-1, bc^-1, cd^-1, da^-1. It is easy to find an example where such transformation never ends. Take the group [bbz]/p[bbz] with p prime and operation +. The configuration (0,1,0,1) after n iterations becomes (2^n-1, -2^n-1, 2^n-1, -2^n-1) and never ends.

Title: Re: Four Numbers Game
Post by Aryabhatta on Nov 4^th, 2004, 10:43am

on 11/03/04 at 23:47:34, Barukh wrote:

I wonder also if questions 1)-2) allow generalization to more integers. My conjecture is that the game will end if and only if number of sides of the polygon is 2^M. Any thoughts?

Here is a proof that for a polygon with odd number of vertices, there are games which don't end.

We consider only games which have intial values 0 and 1.
If the the values are 0 and 1, the absolute difference becomes equivalent to taking the exclusive OR (XOR).

The if the initial values were (a₁,a₂,...,a_N) where N is odd, the values is the next step are
(a₁ XOR a₂, a₂ XOR a₃,...,a_N XOR a₁)

Now the XOR of all the new numbers is zero (as each previous number appears exactly twice). This means that in the new numbers, 1 appears an even number of times.

Thus if we initially start out with say 2 (any even > 0) ones, we will never get to all zeroes. As to get to all zeroes, we must have all ones (or all zeroes) in the previous step. (This can be easily seen, as each XOR must be zero implies any two adjacent vertices must be the same)

Title: Re: Four Numbers Game
Post by Obob on Nov 4^th, 2004, 10:46am

It looks like question 7 isn't as interesting as intended, although the following generalization which Barukh alluded to two posts ago may make it more interesting. The n numbers game is the same game as the four numbers game, except we play it on the regular n-gon instead of the square. Some questions which arise naturally are:

1'.) When does the n-numbers game terminate for integers?

2'.) For which n do there exist arbitrarily long games in integers?

4'.) For which n does the game fail to terminate for reals?

7'.) For which n does the game always terminate over the cyclic group Z/mZ?

I suspect that the reason why the four numbers game does not terminate over Z/pZ for p a prime other than 2 is because 4 is relatively prime to p.

Title: Re: Four Numbers Game
Post by Aryabhatta on Nov 4^th, 2004, 2:51pm

on 11/04/04 at 10:46:47, Obob wrote:

The n numbers game is the same game as the four numbers game, except we play it on the regular n-gon instead of the square. Some questions which arise naturally are:

4'.) For which n does the game fail to terminate for reals?

I think for any n > 2, there is a assignment in reals which fails to terminate.

Start off with (1,x,x²,...,x^n-1) where x > 1 is a real number to be decided later.

After one round, the numbers become
(1,x,x²,...,1+x+x²+...+x^n-2)
(We have divided through out by x-1)

Consider the polynomial
P(x) = x^n-1 - (1+x+x²+...+x^n-2)

It will be enough if we can show that this polynomial has a real root > 1.

Now P(1) < 0 and P(2) > 0. Thus P(x) has at least one real root in (1,2). Pick that to be x.

Title: Re: Four Numbers Game
Post by Obob on Nov 4^th, 2004, 3:31pm

Wow, Aryabhatta, that is a very elegant solution. I never thought to divide out by 1-x like that.

Title: Re: Four Numbers Game
Post by Aryabhatta on Nov 6^th, 2004, 9:23pm

on 11/03/04 at 23:47:34, Barukh wrote:

I wonder also if questions 1)-2) allow generalization to more integers. My conjecture is that the game will end if and only if number of sides of the polygon is 2^M. Any thoughts?

It looks like your inituition is right again as usual, Barukh!

The following proof needs to be verified... it is a little long.

For given n, let us assume we have a machine M_n which plays out the game for input V [in] [bbz]ⁿ, and halts only if all co-ordinates become zero. (We look at the result of each step as a vector over [bbz]ⁿ)

We have the following claim:

Claim1: M_n halts for all V [in] [bbz]ⁿ if and only if M_n halts for all V [in] {0,1}ⁿ

Proof:

Only if: Trivial.

If:
Assume M_n halts for all V [in] {0,1}ⁿ.

Now given a V' [in] [bbz]ⁿ, consider the game played out on V' mod 2, i.e we look only at the remainders of the numbers when divided by 2. By our assumption, the remainders have to become zero ultimately.

This implies that, the numbers become all even after some time (to say the vector V). Now M_n halts on V if and only if M_n halts on V/2, i.e each number is divided by 2 (dividing by 2 is well defined as all numbers are even). By complete induction on the maximum number among the n elements, we can easily show that M_n has to eventually halt. (the base cases when max = 0 and max = 1 are trivial)

[]

Thus it is enough if we consider only games with input in {0,1}ⁿ.

Now our given game is equivalent to the game of (a₁,a₂,...,a_n) being modified to (a₁+a_n, a₁+a₂,...,a_n+a_n-1 ) where the addition is taken to be modulo 2, ie consider it as a vector over [bbf]₂[supn]. (or alternatively, a boolean vector...)

Now our modification of v corresponds to multiplying v by the matrix

[1 0 0 0 ... 1]
[1 1 0 0 ... 0]
[0 1 1 0 ... 0]
. . . . . .
. . . . . . .
[0 0 0 ... 1 1]

(each row cyclic shifted right by 1 to get the next row)

Lets call the above nxn matrix T. Thus in the game, from v we go to Tv.

Lets call the all ones nx1 vector [1 1 ... 1] as J.

Now suppose for some x and y, Tx = y. Then x = Ay or Ay + J
where A is the nxn matrix

[1 0 0 0 ... 0]
[1 1 0 0 ... 0]
[1 1 1 0 ... 0]
. . . . . .
. . . . . .
[1 1 1 1 ... 0]
[1 1 1 1 ... 1]

(Basically the all ones lower diagonal matrix)

This is because Tv = 0 only for v = 0 or v = J. This means if Tx = y has at least one solution, it has exactly 2 solutions v and v+J (i.e x is one of v or v+J). Now one of these solutions is Ay. Thus Tx = y implies x = Ay or Ay+J.

So we have the following Lemma:

Lemma1: Tx = y => x = Ay or x = Ay+J.

Now suppose x is a vector such that the game terminates. i.e T^kx = 0 for some k.
Define the k vectors x_i = T^k-i+1x for i = 1 to k.

(x is defined as x_k+1 and thus x = x_k+1 goes to x_k goes to x_k-1 ... to 0)

By Lemma1, since Tx_t+1 = x_t, we have that x_t+1 = Ax_t or Ax_t+J.

This implies that x is a linear combination of J,AJ, A²J, ..., A^k-1J

Thus we have the following:

Lemma2: If T^kx = 0 for some k, then x is a linear combination of J,AJ, A²J, ..., A^k-1J.

We also have the following (easily proved by induction using Lemma1 )

Lemma3: T^k+1A^kJ = 0 for all k.

Now we are in a position to claim the following:

Claim2: if m = min {k | T^kx = 0} then m [le] n. (In other words, if the game terminates for some x, then it does so in no more than n steps)

Proof:

Consider the characteristic polynomial of A, det (A-[lambda]I). By induction we can easily prove that det (A-[lambda]I) = P([lambda]) = ([lambda] - 1)ⁿ.

Now since the roots of P([lambda]) are all in [bbf]₂, we can apply the Cayley Hamilton Theorem.

i.e (A+I)ⁿ = 0.
This implies that Aⁿ is a linear combination of I, A, A²,...,A^n-1.

Thus any power of A is a linear combination of I,A, A²,...,A^n-1.

Now suppose the game with x terminates in m steps. i.e
m is the least k such that T^kx = 0. By Lemma2, x is a linear combination of J, AJ, A²J,...,A^m-1J. Since any power of A is a linear combination of I, A, A²,...,A^n-1, we have that x is a linear combination of J, AJ, ..., A^n-1J.

Thus Tⁿx = 0 by Lemma3. Thus we have that m [le] n.

Now we have the another Lemma:

Lemma4: The game terminates for all v [in] {0,1}ⁿ if and only if the game terminates for v = (1,0,0,...,0) (i.e the vector whose first coordinate is 1 and the rest of the coordinates are 0)

Proof: Only IF: is trivial.
IF:
It is easy to see that if the game terminates for x and y, then it terminates for x+y. Since the game terminates for (1,0, ...,0) , by symmetry it also terminates for (0,1,0,..0), (0,0,1,...0) ... (0,0,....0,1) and their linear combinations, which is the whole space.

Now we come to the main conclusion:

Theorem: The game terminates for all v [in] {0,1}ⁿ if and only if n is a power of 2.

Proof: By lemma4, all we need to do is check for termination of (1,0,0,...0). An induction proof shows that when we play out the game for (1,0,0,...,0) we end up with the parities of the elements in each row of the pascals triangle. i.e it goes something like:
1
1 1
1 0 1
1 1 1 1
1 0 0 0 1

(Suitably fill the rest with zeroes)
if n is a power of 2, within n-1 steps, we reach the coefficients of (1+t)^n-1 which are all odd! Hence on the n^th step, the game terminates.

If n is not a power of 2, in n (or less) steps we never reach the all ones vector and hence by Claim2, the game does not terminate for (1,0,0,...0) if n is not a power of 2.

Phew!

Title: Re: Four Numbers Game
Post by Barukh on Nov 7^th, 2004, 10:43am

I like your solution, Aryabhatta! I think it is sound. Again, a nice usage of linear algebra!

I tried to prove my conjecture over the last two days. Finally, I have something I want to present here. I think you will see some similarities with your proof.

My proof was initiated by your demonstration for odd numbers. Again, assume that we take the original vector of n numbers V₀ to be a vector in {0, 1}ⁿ. Then, I asked the question: What will be the vector V_m after m moves in terms of numbers in V₀? The answer is that every element in V_m will be an XOR of some elements in V₀. This may be represented by the circulant matrix A_m, such that the k-th element in V_m is a XOR-combination of the elements in V₀ corresponding to 1-s in A_m(k), the matrix k-th row. Now we have the following properties:

1. A₀ = I, the identity matrix.
2. A_m(k) = A_m-1(k) XOR A_m-1(k+1 mod n).
Next, it is easy to see that the statement “Some V_m = 0” is equivalent to “A_m is 0-matrix”, which in turn means “V_m-1 is 1-matrix”. This is a consequence of the fact that A_m is circulant. Moreover, because of that it is sufficient to consider only one row in A_m.

The main idea of the proof is to reverse the transformation and reconstruct one row of A_m-1 out of the row of A_m. It is not difficult: if A_m(1) = (a₁, …, a_n), then A_m-1(1) = (x₁, …, x_n) satisfies the system of n equations
a_i = x_i XOR x_i+1, i = 1,..,n.
The fundamental fact is that this system has a solution iff the number of 1-s in A_m(1) is even. (why?) Therefore, the solution to the game will exist if we can reconstruct the 1-matrix up to the identity matrix so that every matrix except the last has an even number of 1-s in a row. The following statement helps to deduce when it’s possible:

Starting with the 1-matrix, after 2^m-1 reconstructions, the matrix consists of rows (0…010…01…0…01), where the group (0…01) of length 2^m is repeated n/2^m times.
I leave the proof of this statement as an exercise; the following example for n=24 demonstrates:

111111111111111111111111
1. 010101010101010101010101
2. 001100110011001100110011
3. 000100010001000100010001
4. 000011110000111100001111
5. 000001010000010100000101
6. 000000110000001100000011
7. 000000010000000100000001

It now follows, that if n is not a power of 2, then it has at least odd factor, and therefore after some 2^m-1 reconstructions the matrix A will have a row with an odd number of 1-s greater than 1. In this case, the identity matrix cannot be reconstructed, meaning all 1-s matrix cannot be reached, and the game won’t terminate. If n is a power of 2, this process will lead all the way back to the identity matrix.

Title: Re: Four Numbers Game
Post by Aryabhatta on Nov 7^th, 2004, 4:16pm

on 11/07/04 at 10:43:48, Barukh wrote:

The main idea of the proof is to reverse the transformation and reconstruct one row of A_m-1 out of the row of A_m. It is not difficult: if A_m(1) = (a₁, …, a_n), then A_m-1(1) = (x₁, …, x_n) satisfies the system of n equations
a_i = x_i XOR x_i+1, i = 1,..,n.
The fundamental fact is that this system has a solution iff the number of 1-s in A_m(1) is even. (why?) Therefore, the solution to the game will exist if we can reconstruct the 1-matrix up to the identity matrix so that every matrix except the last has an even number of 1-s in a row. The following statement helps to deduce when it’s possible:

Starting with the 1-matrix, after 2^m-1 reconstructions, the matrix consists of rows (0…010…01…0…01), where the group (0…01) of length 2^m is repeated n/2^m times.

It now follows, that if n is not a power of 2, then it has at least odd factor, and therefore after some 2^m-1 reconstructions the matrix A will have a row with an odd number of 1-s greater than 1. In this case, the identity matrix cannot be reconstructed, meaning all 1-s matrix cannot be reached, and the game won’t terminate. If n is a power of 2, this process will lead all the way back to the identity matrix.

For a given A_m(1), we have two possible choices of A_m-1(1), as the systems of equations above has 2 solutions if number of ones in A_m(1) is even. So for n=2^m the existence of a solution follows, but I am not sure if the non-existence of a solution for other n follows as we might have to look at all the possible choices to be sure that none of them is reachable... Am I missing something?

Title: Re: Four Numbers Game
Post by Barukh on Nov 8^th, 2004, 12:06am

on 11/07/04 at 16:16:26, Aryabhatta wrote:

Yes, there are exactly 2 solutions of the system: they may be obtained by setting e.g. x₁ = 0 and x₁ = 1. But it is not difficult to see that one solution is obtained from the other by a circular shift by one position. Therefore, it is sufficient to consider just one solution (my example sets x₁ = 0).

Title: Re: Four Numbers Game
Post by Aryabhatta on Nov 8^th, 2004, 9:47am

on 11/08/04 at 00:06:51, Barukh wrote:

Isn't one solution a ones complement of the other?
i.e. if A_m-1(1) is a solution then so is A_m-1(1)+J, where J is the all ones vector?

Title: Re: Four Numbers Game
Post by Barukh on Nov 9^th, 2004, 1:08am

Aryabhatta, you are right, I overlooked the possibility of multiple reconstruction choises. My proof is incomplete :(

Athough I still believe it may be completed :)

Title: Re: Four Numbers Game
Post by Barukh on Nov 10^th, 2004, 5:53am

Here’s an attempt to rescue my proof. ;D

Assume that for some A_m the system is soluble. Then, it is easy to see that both solutions have the same parity of 1-s (and 0-s). Therefore, if one of the solutions corresponds again to a soluble system, so does the other. Therefore, at every step it is sufficient to consider only one of the 2 solutions, and we choose the one corresponding to x₁ = 0.

Title: Re: Four Numbers Game
Post by Aryabhatta on Nov 10^th, 2004, 4:11pm

on 11/10/04 at 05:53:26, Barukh wrote:

That will not be enough, as we have to consider the whole binary tree starting from 11111...111. (or 000...0000)

But it seems like the 'parity remaining same' idea should work!

Each time you add a new level to the binary tree, the {parity of elements in that level} is basically {parity of all previous elements seens + parity of the the solution for that level for the solution that corresponds to x₁ = 0}. i.e if L is a new element at the newly added level, then its parity will be parity of an element which appeared previously + parity of the solution added at the newly added level corresponding to x₁ = 0. Also, there will be 1-1 correspondence between each newly added element and an element previously seen.

So by an induction argument, i guess we can prove that the parities till 2^m-2 reconstructions remain the same (at 0) and then suddenly flip to 1 at the (2^m-1)^th reconstruction.

I am not sure, but it seems like it might work.