Page 1 of 2 12 LastLast
Results 1 to 15 of 28

Math Help - Regular Square Questions

  1. #1
    Banned
    Joined
    Apr 2009
    Posts
    96

    Regular Square Questions

    Hello All,

    This is my second thread with regards to squares, my first one was about Magic Squares, this one is about "Regular Squares". I was reading through my textbook and I compiled a few questions on how these things work, and I'm hoping some of you might be able to help me!

    Q1: Let's create another square called Y. Y is a 4x4 square that we would like to make "regular". (Regular indicates that each of the integers from 0 to (n^2)-1 appear in exactly one cell which contains only one integer and that when expressed in a base-n form has each base-n digit occur exactly once in the unit position and exactly one in the n position.)

    My book gives example for the 3 dimensional square, but does not give one for 4. Can someone help me find a 4x4 that is regular? I would like to try expressing it in BOTH regular decimal and base-n forms, and for the sake of consistency, I'd like to use a base-4 form. (I can give my example from the book upon request).

    Q2: My book notates that all regular squares have to be magic. How is this so? Can it be proven? If so, how?

    Q3: (I asked a similar question about Magic Squares): Using the same square Y, lets analyze the first two rows or columns, r1 and r2 or c1 and c2, respectively. Should we swap the contents of r1 with r2, or c1 with c2's, we can form a new Square called Z. How is it that Z is also a regular square?

    Any help is appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200
    Sorry, my screenname was apparently illegal. Now that it is changed, please feel free to respond as normal. Thanks!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by 1337h4x View Post
    (Regular indicates that each of the integers from 0 to (n^2)-1 appear in exactly one cell which contains only one integer and that when expressed in a base-n form has each base-n digit occur exactly once in the unit position and exactly one in the n position.)
    This was not very clear, but after re-reading a bunch of times I understood what it was. Of course we are using leading zeros, so we would write 1 as 01.

    But I don't think the "exactly once" condition can apply to both diagonals, at least for n = 3. So does the condition just apply to rows and columns?

    Quote Originally Posted by 1337h4x View Post
    (I can give my example from the book upon request)
    This wouldn't hurt.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200
    Quote Originally Posted by undefined View Post
    This was not very clear, but after re-reading a bunch of times I understood what it was. Of course we are using leading zeros, so we would write 1 as 01.

    But I don't think the "exactly once" condition can apply to both diagonals, at least for n = 3. So does the condition just apply to rows and columns?



    This wouldn't hurt.
    Well here is the example from the book (hopefully that will answer the question you asked me):

    Original = \begin{pmatrix}<br />
7 & 3 & 2\\ <br />
5 & 1 & 6\\ <br />
0 & 8 & 4<br />
\end{pmatrix} and in Base 3 = \begin{pmatrix}<br />
21 & 10 & 02\\ <br />
12 & 01 & 20\\ <br />
00 & 22 & 11<br />
\end{pmatrix}

    The book notes the following as well: "The square is regular because each of the ternary digits [0,1,2] appears exactly one time in units' and the 3's position in each row and each column."
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Samson View Post
    Well here is the example from the book (hopefully that will answer the question you asked me):

    Original = \begin{pmatrix}<br />
7 & 3 & 2\\ <br />
5 & 1 & 6\\ <br />
0 & 8 & 4<br />
\end{pmatrix} and in Base 3 = \begin{pmatrix}<br />
21 & 10 & 02\\ <br />
12 & 01 & 20\\ <br />
00 & 22 & 11<br />
\end{pmatrix}

    The book notes the following as well: "The square is regular because each of the ternary digits [0,1,2] appears exactly one time in units' and the 3's position in each row and each column."
    Yup, that answered my question. I have a method that I think is fast enough and can either find a regular 4 by 4 square, or prove that none exists, but I won't be able to get to it for another 12 hrs or so (and I'm not sure how long it will take to implement).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200
    Quote Originally Posted by undefined View Post
    Yup, that answered my question. I have a method that I think is fast enough and can either find a regular 4 by 4 square, or prove that none exists, but I won't be able to get to it for another 12 hrs or so (and I'm not sure how long it will take to implement).
    Do you think that your method can answer all three questions ?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Samson View Post
    Do you think that your method can answer all three questions ?
    Well I was working one at a time and just dealing with Q1 first, but: the answer to Q3 is exactly the reasoning in this thread. If we were considering diagonals, this reasoning would not work, but we don't care about diagonals, so it does work. Think about it: say you have a row that satisfies the condition for a regular square (it has exactly one of ... etc.). If you permute the row, the condition is still satisfied.

    For Q2, consider that the above 3 by 3 regular square is not a magic square if diagonals are considered. So we will only consider rows and columns.

    Consider a 2-digit number in base n (leading zeroes allowed), written as n = ab, meaning n = na + b. Now we have n_1,n_2,\cdots,n_n, and the sum is n_1+\cdots+n_n=n(a_1+\cdots +a_n)+b_1+\cdots+ b_n. It shouldn't be too hard to see that a_1+\cdots +a_n = b_1+\cdots+ b_n = 0 + 1 + \cdots + (n-1) = \frac{n(n-1)}{2}. So the sum for each row and each column is the same.

    Although I won't do Q1 until 12 hrs or so, I can provide a sketch in the meantime. (Might be a bit hard to follow.) Consider just the most significant digits. We can fix the top row as (0, 1, 2, 3) without loss of generality. Then we can find all possible ways to fill in the square with just the most significant digit, leaving the least significant digit empty. Then for each of these combinations, we can try each way to fill in the top row with least significant digits. This will restrict the possible ways to fill in the least significant digits in the rest of the squares; each other square will have two possibilities. From work on paper, I believe that choosing just one value for just one cell will have a cascade effect, such that all the other least significant digits have only one possibility. The only problem is that we can get duplicate numbers (and thus not a regular square).

    I can clarify more later when I've worked on implementation. It will be easier to follow if I make some pictures.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200
    Quote Originally Posted by undefined View Post
    Well I was working one at a time and just dealing with Q1 first, but: the answer to Q3 is exactly the reasoning in this thread. If we were considering diagonals, this reasoning would not work, but we don't care about diagonals, so it does work. Think about it: say you have a row that satisfies the condition for a regular square (it has exactly one of ... etc.). If you permute the row, the condition is still satisfied.

    For Q2, consider that the above 3 by 3 regular square is not a magic square if diagonals are considered. So we will only consider rows and columns.

    Consider a 2-digit number in base n (leading zeroes allowed), written as n = ab, meaning n = na + b. Now we have n_1,n_2,\cdots,n_n, and the sum is n_1+\cdots+n_n=n(a_1+\cdots +a_n)+b_1+\cdots+ b_n. It shouldn't be too hard to see that a_1+\cdots +a_n = b_1+\cdots+ b_n = 0 + 1 + \cdots + (n-1) = \frac{n(n-1)}{2}. So the sum for each row and each column is the same.

    Although I won't do Q1 until 12 hrs or so, I can provide a sketch in the meantime. (Might be a bit hard to follow.) Consider just the most significant digits. We can fix the top row as (0, 1, 2, 3) without loss of generality. Then we can find all possible ways to fill in the square with just the most significant digit, leaving the least significant digit empty. Then for each of these combinations, we can try each way to fill in the top row with least significant digits. This will restrict the possible ways to fill in the least significant digits in the rest of the squares; each other square will have two possibilities. From work on paper, I believe that choosing just one value for just one cell will have a cascade effect, such that all the other least significant digits have only one possibility. The only problem is that we can get duplicate numbers (and thus not a regular square).

    I can clarify more later when I've worked on implementation. It will be easier to follow if I make some pictures.
    Okay, I totally understand your reasoning for Q3 and for Q2, and thank you for making that adaptation to Q3 like you did.

    As far as Q1 goes, I kind of follow where you're going with it, but like you had said, I think I would understand it alot better once you have the result and can provide an image of such. I definitely look forward to seeing that later! Thank you so much for your time, effort, and help thus far!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200
    Hey undefined, I was wondering if you got around to Q1 yet. I'm just checking in! Thank you for all your help thus far :-)
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Samson View Post
    Hey undefined, I was wondering if you got around to Q1 yet. I'm just checking in! Thank you for all your help thus far :-)
    Yeah sorry, I started on it, got distracted, and fell asleep. But I'll let you know in the next few hours now, for sure.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200
    Quote Originally Posted by undefined View Post
    Yeah sorry, I started on it, got distracted, and fell asleep. But I'll let you know in the next few hours now, for sure.

    Thank you! I greatly appreciate it and I look forward to seeing what you come up with!
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Samson View Post
    Thank you! I greatly appreciate it and I look forward to seeing what you come up with!
    All right, so I wrote most of the program whose algorithm I described above, but I didn't actually need to complete the program because the partial output allowed me to find one on paper.

    Here is the square I found:

    Code:
    00 11 22 33
    12 03 30 21
    23 32 01 10
    31 20 13 02
    
    00 05 10 15
    06 03 12 09
    11 14 01 04
    13 08 07 02
    And here is the Java code I used:

    Code:
    import java.util.ArrayList;
    
    public class RegularSquares {
        public static void main(String[] args) {
            int[][] square = new int[4][4];
            for (int i = 1; i < 4; i++)
                square[0][i] = 4*i;
            ArrayList<Integer> rowRemaining = fullRowRemaining1();
            recurse1(square, 1, 0, rowRemaining);
        }
        public static void recurse1(int[][] square, int ind1, int ind2, ArrayList<Integer> rowRemaining) {
            if (ind1 == 4) {
                recurse2(square, 0, fullRowRemaining2());
                return;
            }
            int nextInd1 = (ind2 == 3) ? ind1 + 1 : ind1;
            int nextInd2 = (ind2 == 3) ? 0 : ind2 + 1;
            for (int i = 0; i < rowRemaining.size(); i++) {
                int num = rowRemaining.get(i);
                boolean possible = true;
                for (int j = 0; j < ind1; j++)
                    if (num == square[j][ind2]) {
                        possible = false;
                        break;
                    }
                if (possible)
                    for (int j = 0; j < ind2; j++)
                        if (num == square[ind1][j]) {
                            possible = false;
                            break;
                        }
                if (possible) {
                    int[][] nextSquare = deepCopy(square);
                    nextSquare[ind1][ind2] = num;
                    ArrayList<Integer> nextRowRemaining;
                    if (ind2 < 3) {
                        nextRowRemaining = new ArrayList<Integer>(rowRemaining);
                        nextRowRemaining.remove(i);
                    }
                    else nextRowRemaining = fullRowRemaining1();
                    recurse1(nextSquare, nextInd1, nextInd2, nextRowRemaining);
                }
            }
        }
        public static void recurse2(int[][] square, int ind, ArrayList<Integer> rowRemaining) {
            if (ind == 4) {
                fillInBlanks(square);
                return;
            }
            for (int i = 0; i < rowRemaining.size(); i++) {
                int num = rowRemaining.get(i);
                int[][] nextSquare = deepCopy(square);
                nextSquare[0][ind] += num;
                ArrayList<Integer> nextRowRemaining = new ArrayList<Integer>(rowRemaining);
                nextRowRemaining.remove(i);
                recurse2(nextSquare, ind + 1, nextRowRemaining);
            }
        }
        static int test = 0;
        public static void fillInBlanks(int[][] square) {
            ArrayList<ArrayList<Integer>> options = new ArrayList<ArrayList<Integer>>();
            for (int i = 0; i < 4; i++)
                options.add(new ArrayList<Integer>());
            int[] taken = new int[4];
            for (int i = 0; i < 4; i++)
                taken[square[0][i] / 4] = square[0][i] % 4;
            for (int i = 1; i < 4; i++)
                for (int j = 0; j < 4; j++) {
                    ArrayList<Integer> currOptions = new ArrayList<Integer>();
                    int mostSigDig = square[i][j] / 4;
                    int takenByFirstRow = square[0][j] % 4;
                    for (int k = 0; k < 4; k++)
                        if (k != takenByFirstRow && k != taken[mostSigDig])
                            currOptions.add(k);
                    options.add(currOptions);
                }
            if (test < 2) {
                printSquare(square, 4);
                System.out.println();
                System.out.println(options);
                System.out.println();
            }
            test++;
        }
        public static int getX(int n) {
            return n / 4;
        }
        public static int getY(int n) {
            return n % 4;
        }
        public static int encode(int x, int y) {
            return 4*x + y;
        }
        public static boolean hasAllNums(int[][] square) {
            ArrayList<Integer> allNums = getAllNums();
            for (int i = 0; i < 4; i++)
                for (int j = 0; j < 4; j++) {
                    if (!allNums.contains(square[i][j])) return false;
                    allNums.remove(allNums.indexOf(square[i][j]));
                }
            return true;
        }
        public static ArrayList<Integer> getAllNums() {
            ArrayList<Integer> allNums = new ArrayList<Integer>();
            for (int i = 0; i < 16; i++)
                allNums.add(i);
            return allNums;
        }
        public static ArrayList<Integer> fullRowRemaining1() {
            ArrayList<Integer> rowRemaining = new ArrayList<Integer>();
            for (int i = 0; i < 4; i++)
                rowRemaining.add(4*i);
            return rowRemaining;
        }
        public static ArrayList<Integer> fullRowRemaining2() {
            ArrayList<Integer> rowRemaining = new ArrayList<Integer>();
            for (int i = 0; i < 4; i++)
                rowRemaining.add(i);
            return rowRemaining;
        }
        public static int[][] deepCopy(int[][] square) {
            int[][] copy = new int[4][4];
            for (int i = 0; i < 4; i++)
                copy[i] = square[i].clone();
            return copy;
        }
        public static void printSquare(int[][] square, int base) {
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    System.out.print(addLeadingZeroes(Integer.toString(square[i][j], base), 2));
                    if (j != 3) System.out.print(" ");
                }
                System.out.println();
            }
        }
        public static String addLeadingZeroes(String s, int x) {
            if (s.length() >= x) return s;
            return addLeadingZeroes("0" + s, x);
        }
    }
    Here is the partially finished program's output:
    Code:
    00 11 22 33
    10 00 30 20
    20 30 00 10
    30 20 10 00
    
    [[], [], [], [], [2, 3], [2, 3], [0, 1], [0, 1], [1, 3], [0, 2], [1, 3], [0, 2], [1, 2], [0, 3], [0, 3], [1, 2]]
    
    00 11 23 32
    10 00 30 20
    20 30 00 10
    30 20 10 00
    
    [[], [], [], [], [2, 3], [2, 3], [0, 1], [0, 1], [1, 2], [0, 3], [1, 2], [0, 3], [1, 3], [0, 2], [0, 2], [1, 3]]
    I'll make an image to describe the algorithm a bit more.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200
    So I take it that the first output is the decimal form output whereas the second is the base 4 output?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Samson View Post
    So I take it that the first output is the decimal form output whereas the second is the base 4 output?
    The program output given above is only base 4.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Okay so I'm still making images, but I have a couple to share so far.

    So, considering just the most significant digit (or least significant digit, it doesn't matter), notice that this arrangement:

    Regular Square Questions-regsq1.png

    is equivalent to this arrangement:

    Regular Square Questions-regsq2.png

    up to permutations of {0,1,2,3}. All I did was switch all 2's with 3's. That's why I said above, that we can fix the top row as (0, 1, 2, 3) without loss of generality.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 27th 2011, 02:42 PM
  2. Magic Square Questions
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: June 3rd 2010, 04:19 PM
  3. Distinct Square Questions
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: June 2nd 2010, 09:07 AM
  4. Square Root questions!
    Posted in the Algebra Forum
    Replies: 1
    Last Post: May 6th 2010, 07:48 PM
  5. A couple questions with chi square
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: March 28th 2010, 08:29 PM

Search Tags


/mathhelpforum @mathhelpforum