Thread: Number Squares Game

Here is the general question:

Start with a square, with a natural number at each corner. Now write, at the
midpoint of each edge, the absolute value |a-b| of the difference of numbers
(a, b) at the endpoints of that edge. Draw a smaller square connecting those
midpoints, and repeat. The game stops if you get to (0; 0; 0; 0). For instance,
(1; 3; 9; 7) ! (2; 6; 2; 6) ! (4; 4; 4; 4) ! (0; 0; 0; 0):
For a longer game, try (44; 24; 13; 7).
Are there games of infinite length, or of arbitrarily long finite length?
Given a bound on the size of the initial numbers, what can one say about
the maximum length of the game?

-----------------------

Now, based on examination of several cases, I have found that all odd (2N+1) sided games have at least one base case that never ends [often it's the case of (2*N) 1s and (1) zero...(1,1,1,1,1...1,1,0)]

I've also found an upper bound on the steps it takes for the game to "recycle," meaning the game returns to its base stage (or at least a rotation of the base stage...for example 1,1,1,1,0 = 1,1,0,1,1 because the sides are connected), and this upper bound is [(2^N)-1]...in fact, all games with this "binary identity" (all 1s and a 0) will take exactly that many steps to circulate...the only exceptions are when N is a power of two...in this case, it takes (2*N)-1 steps to "recycle."

I was wondering if anyone can prove why this is true...since it was only presumed based upon the collected data.

For starters, this is a fascinating problem. Reminds me of the Collatz Conjecture. I've been trying to formalize your hypothesis and achieve a result, but it is difficult. To review, you have asked three questions that are extremely relevant:

1) For N even, do there exist any "loops" or infinite cycles?
2) For N odd, do there exist any loops other than (1,1,1,...,1,0)?
3) Does the system terminate after at most 2^N-1?

The only solid result I was able to prove is that the range cannot increase. Consider starting with . Define Range(a)=max(a)-min(a). It is easy to see that max(b)<=Range(a). Since min(b)>=0, Range(b)<=Range(a). Therefore the range must be decreasing or constant. The questions can then be rephrased...

1) For N even, are there any sequences whose range stays constant?
2) For N odd, is (1,1,1,...,1,0) the only sequence whose range stays constant?
3) Can Range(a) decrease to 0 in more than 2^N-1 steps?

It's not much, but it's a step in the right direction, I think.

The answer to question 1 is yes. For N=2(2k+1) for k>0, that is, twice an odd number at least 3, start with 2k+1 0's and 2k+1 1's. For example, for k=1, N=6. Start with 000111,001001,011011. This third element is the cycle, consisting of a pair of 2k-1 0's followed by 2 1's.

N=10: 0000011111,0000100001,0001100011. The cycle has a period of 2k+1, ignoring left/right shifts.

Also, N=14 works too, so the formula is not 2(2^k+1) as I thought at first. Also, N=12 works, starting with 000000111111. The cycle is different though, so I am not sure how to generalize. I have a feeling that this starting position works for all N except 2^k, but I am hesitant to conjecture that yet, as none of this I have been able to prove yet. Besides, the smallest number of the form 8(2k+1) is 24, pushing the limits/patience of hand calculations.