Regular Square Questions

Printable View

Show 40 post(s) from this thread on one page

June 2nd 2010, 03:48 AM
1337h4x

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!
June 2nd 2010, 04:58 AM
Samson

Sorry, my screenname was apparently illegal. Now that it is changed, please feel free to respond as normal. Thanks!
June 2nd 2010, 08:47 AM
undefined

Quote:

Originally Posted by 1337h4x

(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

(I can give my example from the book upon request)

This wouldn't hurt.
June 2nd 2010, 09:01 AM
Samson

Quote:

Originally Posted by undefined

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} 7 & 3 & 2\\ 5 & 1 & 6\\ 0 & 8 & 4 \end{pmatrix}$ and in Base 3 = $\begin{pmatrix} 21 & 10 & 02\\ 12 & 01 & 20\\ 00 & 22 & 11 \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."
June 2nd 2010, 09:36 AM
undefined

Quote:

Originally Posted by Samson

Well here is the example from the book (hopefully that will answer the question you asked me):

Original = $\begin{pmatrix} 7 & 3 & 2\\ 5 & 1 & 6\\ 0 & 8 & 4 \end{pmatrix}$ and in Base 3 = $\begin{pmatrix} 21 & 10 & 02\\ 12 & 01 & 20\\ 00 & 22 & 11 \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).
June 2nd 2010, 09:43 AM
Samson

Quote:

Originally Posted by undefined

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 ?
June 2nd 2010, 10:13 AM
undefined

Quote:

Originally Posted by Samson

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.
June 2nd 2010, 10:20 AM
Samson

Quote:

Originally Posted by undefined

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!
June 3rd 2010, 03:21 AM
Samson

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 :-)
June 3rd 2010, 05:49 AM
undefined

Quote:

Originally Posted by Samson

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.
June 3rd 2010, 05:57 AM
Samson

Quote:

Originally Posted by undefined

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!
June 3rd 2010, 07:53 AM
undefined

Quote:

Originally Posted by Samson

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.
June 3rd 2010, 08:15 AM
Samson

So I take it that the first output is the decimal form output whereas the second is the base 4 output?
June 3rd 2010, 08:19 AM
undefined

Quote:

Originally Posted by Samson

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.
June 3rd 2010, 08:26 AM
undefined

2 Attachment(s)

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:

Attachment 17113

is equivalent to this arrangement:

Attachment 17114

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.

Show 40 post(s) from this thread on one page