Results 1 to 3 of 3

Math Help - Number Squares Game

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    2

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    Range

    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 (a_1,a_2,...,a_n)\to(b_1,b_2,...,b_n). 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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    Counterexample

    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.
    Last edited by Media_Man; November 22nd 2009 at 08:32 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: January 9th 2012, 11:48 AM
  2. Replies: 5
    Last Post: January 4th 2012, 01:49 AM
  3. Number of Squares and Rectangles in a Grid
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: March 10th 2010, 05:03 AM
  4. Replies: 0
    Last Post: March 10th 2008, 10:27 PM
  5. 3 digit number game - PLEASE HELP
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: October 3rd 2005, 11:10 AM

Search Tags


/mathhelpforum @mathhelpforum