Author |
Topic: Four Numbers Game (Read 1206 times) |
|
Obob
Guest
|
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!
|
|
 IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Re: Four Numbers Game
« Reply #1 on: Nov 1st, 2004, 1:27pm » |
 Quote  Modify
|
wlog, we can assume the numbers are non-negative.
For the game termination over integers i.e
1) Consider the maximum of the four numbers .
Over rationals, i.e.
3) the rationals can be written as a/M,b/M,c/M,d/M and termination follows from termination of a,b,c,d .
For reals, i.e. 4) my guess of a counter-example to termination is:
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 .
Maybe an answer to 2 will provide insight on how to tackle 4 better.
|
|
IP Logged |
|
|
|
Obob
Guest
|
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.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Four Numbers Game
« Reply #3 on: Nov 2nd, 2004, 3:58am » |
Quote Modify
|
It’s very interesting problem, Obob! I’ve seen only the first question a long time ago.
1.
[smiley=blacksquare.gif]
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 2n. Then, if all the numbers originally are less than M, the game will end after at most 4log2M iterations.
[smiley=blacksquare.gif]
2.
[smiley=blacksquare.gif]
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 Tn, Tn+1, Tn+2, Tn+3. After 3 iterations, the numbers becomes 2Tn-2, 2Tn-1, 2Tn, 2Tn+1. Therefore, the game cannot last less than 3n/2 moves.
[smiley=blacksquare.gif]
4. I didn’t check this one, just a guess (also for 5).
[smiley=square.gif]
Let [alpha] be the positive root of the equation x3 - x2 - x – 1 = 0. Take four real numbers 1, [alpha], [alpha]2, [alpha]3. The game won’t terminate. 
[alpha] plays the same role for tribonacci numbers as golden ratio for Fibonacci numbers.
[smiley=square.gif]
|
| « Last Edit: Nov 2nd, 2004, 7:40am by Barukh » |
IP Logged |
|
|
|
Obob
Guest
|
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.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Four Numbers Game
« Reply #5 on: Nov 2nd, 2004, 10:07am » |
Quote Modify
|
Very nice, Barukh and Obob! Excellent solutions.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Four Numbers Game
« Reply #6 on: Nov 3rd, 2004, 11:47pm » |
Quote Modify
|
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 Tn+1/ Tn 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 2M. Any thoughts?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Four Numbers Game
« Reply #7 on: Nov 4th, 2004, 5:24am » |
Quote Modify
|
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 (2n-1, -2n-1, 2n-1, -2n-1) and never ends.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Four Numbers Game
« Reply #8 on: Nov 4th, 2004, 10:43am » |
Quote Modify
|
on Nov 3rd, 2004, 11:47pm, 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 2M. 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 (a1,a2,...,aN) where N is odd, the values is the next step are
(a1 XOR a2, a2 XOR a3,...,aN XOR a1)
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)
|
|
IP Logged |
|
|
|
Obob
Guest
|
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.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Four Numbers Game
« Reply #10 on: Nov 4th, 2004, 2:51pm » |
Quote Modify
|
on Nov 4th, 2004, 10:46am, 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,x2,...,xn-1) where x > 1 is a real number to be decided later.
After one round, the numbers become
(1,x,x2,...,1+x+x2+...+xn-2)
(We have divided through out by x-1)
Consider the polynomial
P(x) = xn-1 - (1+x+x2+...+xn-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.
|
|
IP Logged |
|
|
|
Obob
Guest
|
Wow, Aryabhatta, that is a very elegant solution. I never thought to divide out by 1-x like that.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Four Numbers Game
« Reply #12 on: Nov 6th, 2004, 9:23pm » |
Quote Modify
|
on Nov 3rd, 2004, 11:47pm, 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 2M. 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 Mn which plays out the game for input V [in] [bbz]n, and halts only if all co-ordinates become zero. (We look at the result of each step as a vector over [bbz]n)
We have the following claim:
Claim1: Mn halts for all V [in] [bbz]n if and only if Mn halts for all V [in] {0,1}n
Proof:
Only if: Trivial.
If:
Assume Mn halts for all V [in] {0,1}n.
Now given a V' [in] [bbz]n, 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 Mn halts on V if and only if Mn 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 Mn 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}n.
Now our given game is equivalent to the game of (a1,a2,...,an) being modified to (a1+an, a1+a2,...,an+an-1 ) where the addition is taken to be modulo 2, ie consider it as a vector over [bbf]2[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 Tkx = 0 for some k.
Define the k vectors xi = Tk-i+1x for i = 1 to k.
(x is defined as xk+1 and thus x = xk+1 goes to xk goes to xk-1 ... to 0)
By Lemma1, since Txt+1 = xt, we have that xt+1 = Axt or Axt+J.
This implies that x is a linear combination of J,AJ, A2J, ..., Ak-1J
Thus we have the following:
Lemma2: If Tkx = 0 for some k, then x is a linear combination of J,AJ, A2J, ..., Ak-1J.
We also have the following (easily proved by induction using Lemma1 )
Lemma3: Tk+1AkJ = 0 for all k.
Now we are in a position to claim the following:
Claim2: if m = min {k | Tkx = 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)n.
Now since the roots of P([lambda]) are all in [bbf]2, we can apply the Cayley Hamilton Theorem.
i.e (A+I)n = 0.
This implies that An is a linear combination of I, A, A2,...,An-1.
Thus any power of A is a linear combination of I,A, A2,...,An-1.
Now suppose the game with x terminates in m steps. i.e
m is the least k such that Tkx = 0. By Lemma2, x is a linear combination of J, AJ, A2J,...,Am-1J. Since any power of A is a linear combination of I, A, A2,...,An-1, we have that x is a linear combination of J, AJ, ..., An-1J.
Thus Tnx = 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}n 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}n 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 nth 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!
|
| « Last Edit: Nov 6th, 2004, 10:00pm by Aryabhatta » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Four Numbers Game
« Reply #13 on: Nov 7th, 2004, 10:43am » |
Quote Modify
|
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 V0 to be a vector in {0, 1}n. Then, I asked the question: What will be the vector Vm after m moves in terms of numbers in V0? The answer is that every element in Vm will be an XOR of some elements in V0. This may be represented by the circulant matrix Am, such that the k-th element in Vm is a XOR-combination of the elements in V0 corresponding to 1-s in Am(k), the matrix k-th row. Now we have the following properties:
1. A0 = I, the identity matrix.
2. Am(k) = Am-1(k) XOR Am-1(k+1 mod n).
Next, it is easy to see that the statement “Some Vm = 0” is equivalent to “Am is 0-matrix”, which in turn means “Vm-1 is 1-matrix”. This is a consequence of the fact that Am is circulant. Moreover, because of that it is sufficient to consider only one row in Am.
The main idea of the proof is to reverse the transformation and reconstruct one row of Am-1 out of the row of Am. It is not difficult: if Am(1) = (a1, …, an), then Am-1(1) = (x1, …, xn) satisfies the system of n equations
ai = xi XOR xi+1, i = 1,..,n.
The fundamental fact is that this system has a solution iff the number of 1-s in Am(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 2m-1 reconstructions, the matrix consists of rows (0…010…01…0…01), where the group (0…01) of length 2m is repeated n/2m 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 2m-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.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Four Numbers Game
« Reply #14 on: Nov 7th, 2004, 4:16pm » |
Quote Modify
|
on Nov 7th, 2004, 10:43am, Barukh wrote:The main idea of the proof is to reverse the transformation and reconstruct one row of Am-1 out of the row of Am. It is not difficult: if Am(1) = (a1, …, an), then Am-1(1) = (x1, …, xn) satisfies the system of n equations
ai = xi XOR xi+1, i = 1,..,n.
The fundamental fact is that this system has a solution iff the number of 1-s in Am(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 2m-1 reconstructions, the matrix consists of rows (0…010…01…0…01), where the group (0…01) of length 2m is repeated n/2m times.
It now follows, that if n is not a power of 2, then it has at least odd factor, and therefore after some 2m-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 Am(1), we have two possible choices of Am-1(1), as the systems of equations above has 2 solutions if number of ones in Am(1) is even. So for n=2m 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?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Four Numbers Game
« Reply #15 on: Nov 8th, 2004, 12:06am » |
Quote Modify
|
on Nov 7th, 2004, 4:16pm, Aryabhatta wrote:| For a given Am(1), we have two possible choices of Am-1(1), as the systems of equations above has 2 solutions if number of ones in Am(1) is even. So for n=2m 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? |
|
Yes, there are exactly 2 solutions of the system: they may be obtained by setting e.g. x1 = 0 and x1 = 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 x1 = 0).
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Four Numbers Game
« Reply #16 on: Nov 8th, 2004, 9:47am » |
Quote Modify
|
on Nov 8th, 2004, 12:06am, Barukh wrote:
Yes, there are exactly 2 solutions of the system: they may be obtained by setting e.g. x1 = 0 and x1 = 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 x1 = 0).
|
|
Isn't one solution a ones complement of the other?
i.e. if Am-1(1) is a solution then so is Am-1(1)+J, where J is the all ones vector?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Four Numbers Game
« Reply #17 on: Nov 9th, 2004, 1:08am » |
Quote Modify
|
Aryabhatta, you are right, I overlooked the possibility of multiple reconstruction choises. My proof is incomplete 
Athough I still believe it may be completed 
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Four Numbers Game
« Reply #18 on: Nov 10th, 2004, 5:53am » |
Quote Modify
|
Here’s an attempt to rescue my proof. 
Assume that for some Am 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 x1 = 0.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Four Numbers Game
« Reply #19 on: Nov 10th, 2004, 4:11pm » |
Quote Modify
|
on Nov 10th, 2004, 5:53am, Barukh wrote:Here’s an attempt to rescue my proof.
Assume that for some Am 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 x1 = 0.
|
|
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 x1 = 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 x1 = 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 2m-2 reconstructions remain the same (at 0) and then suddenly flip to 1 at the (2m-1)th reconstruction.
I am not sure, but it seems like it might work.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove