Assume that you are provided an n * n grid as follows:


The grid must then be filled with the integers 1 through n, while adhering to the following rules:

• Boxes with matching x and y coordinates (box (a,a), box (b,b), etc.) must be filled with the integer "1". (The diagonal from the top left to the bottom right is filled with all 1s.)
  
• If box (m,n) is filled with a certain integer, box (n,m) must be filled with the same integer. (The entries are symmetrical across the diagonal of 1s.)
  
• No single row or column may contain two of the same integer.
  

One such valid solution is as follows:



The following questions are to be answered or solved:

1. Prove that if an n * n grid has a solution, then one of its solutions has the first row of boxes filled with the integers 1 through n in ascending order from left to right.
   
2. Find a generalized algorithm for producing a single solution to an n * n grid where n is even, or prove that at least one solution exists for all such n.
   
3. Find a generalized algorithm for producing a single solution to an n * n grid where n is odd, or prove that no solutions exist for all such n.
   
4. Find the number of unique solutions for each n > 0.
   

I have part 1 solved, but I have no idea where to go after that. How should I go about attacking this problem, SEN?

Here's my lead, I'm working off of the assumption the numbers are sequentially increasing.



It may not be the solution in the book, but meh.

----

The first thing I noticed when looking at aristocrat's board was a simple pattern:



Notice how along the lines all numbers are the same. I placed the grid in a Cartesian coordinate system and drew diagonal lines. In above picture, box (a, a) makes a negative slope, but in my picture I reversed it to easily obtain these equations:

Boxes filled with 1 contain the line y = x.
Boxes filled with 2 contain the line y = -x + a + b
Boxes filled with 3 contain the line y = x ± (a + b + c)

And so on. Keep in mind that although you may replace 1, 2, and 3 with any number, the ideal algorithm will solve this for 1, 2, 3 ... n. And since the question only asks for a general algorithm that will have solved any grid where n is even for only one solution, we have succeeded.

Post has been edited 4 time(s), last time on Jul 25 2011, 3:03 am by Sacrieur.

Sacrieur, I don't know if your algorithm is completely generalized to the even-n case. Doesn't look like it. Though maybe I'm just not reading it through carefully enough.

Some key features about n*n matrices:

Since each row and column has exactly n positions, each row and column must contain exactly 1 of each number 1-n, and this automatically prevents you from having 2 of any of the same number in any row or column.

I'm surprised you're having problems with 2,3 and 4 if you have 1 already solved. To me it seems easier to use 2 and 3 to prove 1, since if 1 is true, then there exists at least 1 solution to all cases, whether n is odd or even, and since you've already proven it for all n, you can just say "By 1, 2 is true" and for 3, you know that you can't prove that there are no solutions for odd n, since there exists at least 1 solution for all n. Are you sure you've proven 1?

And don't give me any crap, because I do have an algorithm for both 2 and 3, though I haven't solved how many solutions there are to each case, but I have some ideas. As for the algorithms, what I did was look for symmetric solutions, just as a general rule, and then just place exactly n of each number.

Also, what counts as a unique solution?

And just as a side note for #3, right off the bat you should know you can't prove there are no solutions because for n=1, [1] is a solution, so it has solutions.

Post has been edited 2 time(s), last time on Jul 25 2011, 4:13 am by Vrael.

Yeah just thought of that. The question should read prove for solutions with n > 1. I'll clean up my mess of algorithm and see if I can't clear things up.

If an n * n matrix has a solution, then no numbers in the first row can be identical. Since there are n boxes in the first row, the set of numbers that appear in the first row must be the integers from 1 to n.

Assume box 2 contains number x, where 1 < x <= n. Without loss of generality, replace all instances of the number x on the board with 2, and all instances of the number 2 on the board with x. This does not break any rules as the positions of the number sets remain unchanged, ensuring no column or row contains two of x or two of 2; since each row contained at most one 2 and one x, after swapping it will still contain at most one x and one 2.

Repeat the above step until the entire first row is sorted.


"Unique solution" would most likely mean a solution that cannot be obtained from any other solution by swapping the numbers around while keeping the relative positions the same.

[1, 3, 2, 4]
[3, 1, 4, 2]
[2, 4, 1, 3]
[4, 2, 3, 1]

would be considered the "same" solution as

[1, 4, 3, 2]
[4, 1, 2, 3]
[3, 2, 1, 4]
[2, 3, 4, 1]

I'm fairly sure n * n grids have no solutions for odd n > 1, because:

A general algorithm for any even n * n grid is as follows...

Orientate the grid on Cartesian coordinates such that box (a, a) contains the point (0, 0) in its perimeter.

Boxes filled with 1 contain the line y = x
Boxes filled with α contain the line y = -x + 2
Boxes filled with β contain the line y = x ± 2
Boxes filled with γ contain the line y = -x + 3
...
Boxes filled with ω contain the line y = -x + m.

The lines are therefore constructed using one general formula:

y_n = (-1)⁽ⁿ⁺¹⁾(x) + n

Where n is all positive integers between 1 and m.

There is at least 1 unique solution for all n-odd, with (n-2)! non-unique permutations of the same solution. Non-unique by your definition of uniqueness. This solution has exactly n instances of each of the numbers 1 through n, so your steps 2 and 3 are wrong.

Just as a hint for this particular solution, try considering what happens about the other diagonal. Matrices can have symmetry in more than one direction.

I stopped there when I was looking for the solution, there may be others or there may not be, I don't know. And yeah your proof for 1 makes sense, I didn't realize you were allowed to assume there was a solution, but thats what I get for not reading the problem correctly.

Edit: didn't read the problem correctly again, all that above is wrong.

Post has been edited 3 time(s), last time on Jul 25 2011, 6:13 pm by Vrael.

We can prove it using the general formula for the even grid.

Edit: no free handouts here ;D.

Post has been edited 1 time(s), last time on Jul 25 2011, 6:14 pm by Sacrieur.

Edit: I was wrong, I completely missed one of the elements of the problem.

Post has been edited 1 time(s), last time on Jul 25 2011, 6:10 pm by Vrael.

As I said above, use my general formula to prove that the odd doesn't work.

For number four, try different combinations of even grids. You'll quickly see the only possibility is a predictable pattern:

For n ≥ 2, the number of unique solutions is equal to (n-1)!.

For n = 1, the number of unique solutions is one.

I'll leave it up to you to figure out why.

So... For n >= 1, the number of unique solutions is equal to (n-1)!. I don't see why you split these up.

This seems like a lot of unique solutions.

Edit: Oh, I see. Your first statement for n >= 2 is for even values of n only, whereas n = 1 is a special case. Thanks for explaining

Post has been edited 2 time(s), last time on Jul 27 2011, 5:12 am by Roy.

A 1x1 grid is exempt from the rule for odd grids since it satisfies all the rules. Thus there is only one solution:
--a
a[1]

You can't get more simple than that. With a 2x2 grid we get:

--a--b
a[1][2]
b[2][1]

Again there is only one unique solution because:

[2][1]
[1][2]

1) violates the rules
2) isn't a unique solution, it's simply a rotation of the above.

Now if we try it with four:

[1][2][3][4]
[2][1][4][3]
[3][4][1][2]
[4][3][2][1]

That's the first permutation, but notice what happens when you try to swap only the top numbers around. You can't, because that would violate the rules, so you must switch both of the numbers around and their corresponding patterns.

[1][3][2][4]
[3][1][4][2]
[2][4][1][3]
[4][2][3][1]

[1][4][3][2]
[4][1][2][3]
[3][2][1][4]
[2][3][4][1]

And so on. We have 3 numbers to swap, and n = 4. If you do it for all of the combinations you'll find you have 6 solutions, or 3!. This is well understood, so a 6x6 grid has 5! solutions.

---

And fuck it, I'll finish 3 too:

So take my general formula for even numbers:

y_n = (-1)⁽ⁿ⁺¹⁾(x) + n

Now let's plug in a general odd number:

y_n = x + n

This has a positive slope, but above we need a negative slope to make this work. Try using a 3x3 grid:

[1][2][3]
[2][1][-]
[3][-][1]

It violates the rules. We can't place anything in those blank spots. This is because to make it work we must do this:

[1][2][3]
[2][1][-][3]
[3][-][1][2]
==[3][2]

And that sure as hell doesn't work.

Post has been edited 4 time(s), last time on Jul 27 2011, 5:36 am by Sacrieur.

the 6-grid has more than one solution which isn't just a permutation of the normal solution with n on each element of the other diagonal though.

For example:
123456
214635
341562
465123
536214
652341

and

123456
215364
351642
436125
564213
642531

are not permutations of each other, and they're both solutions. I don't think they're governed by your equations either. Maybe they are, but I don't see it. Maybe you could explain your grid better?

Also, Aristocrat was saying the permutations don't count as unique solutions. There will be (n-1)! permutations of each unique solution.

Post has been edited 2 time(s), last time on Jul 28 2011, 12:50 am by Vrael.

I suppose this makes Sacrieur's solution for part 4 invalid; after all, he never proved that his method exhausted all possibilities.

/rage

Just an idea, but I think it would be easier to work with half the matrix at a time

1xxx
-1xx
--1x
---1

fill in the x's instead of the entire matrix. Essentially, if you have a number on an x by symmetry it cancels out both its own row/column and its reflection across the diagonal.

for example

1x3x
-1[x]x
--[1][x]
---1

the 3 at (1,3) means there is a 3 at (3,1), so all the numbers in brackets cannot contain a 3, its sort of a perpendicular relfection across the diagonal, but this lets you work with 1/2 the matrix instead of the whole thing. The only thing I've noticed so far with this idea is if you have something like

1xxxxxxx
-1xxxxxx
--1xxxxx
---1xxxx
----1xxx
-----1xx
------1x
-------1
and you choose 2 through n to fill in in those x's, you might be able to count how many choices you have, sum them up to get your number of unique solutions. I haven't tried it though. If you can prove something like, say you place exactly 1 of each 2 through n in those x's, that you can solve it, then there are (sum of x's) choose (n-1) unique solutions**.

Edit: ** at most that many.

Post has been edited 1 time(s), last time on Jul 30 2011, 8:42 pm by Vrael.

How about using derangement algorithm for the first two horizontal lines?