# UVa 10775

## 10775 - Mystical Matrix[edit]

## Summary[edit]

There are many ways to do this problem. One method is to write a naive solution for small *N* and then figure out a pattern.

## Explanation[edit]

There are no solutions for even *N*. Why? Try to figure out row/column sums. The *N* = 3, the 3x3 matrix is simply the given magic square. You can use a brute force way to generate it, and find the patterns.

Another way is the following analytical method. Given *N*, we can first put the 3x3 magic square and the subsequent magic squares side by side:
(Shown for *N* = 9)

8 3 4 17 12 13 26 21 22 1 5 9 10 14 18 19 23 27 6 7 2 15 16 11 24 25 20

Note that the column sums are not the same, but the row sums already is. This observation allow us to swap elements of the same row freely - the row sum will remain the same.

Since we will try to match block to block, we can visualize it as such:

1 2 3 1 2 3 1 2 3

and thus, trying to get the balanced:

1 2 3 2 3 1 3 1 2

## Notes[edit]

- There are more than one solution for each input.

## Input[edit]

3 6 9 12 15 0

## Output[edit]

8 3 4 1 5 9 6 7 2 IMPOSSIBLE 8 3 4 17 12 13 26 21 22 10 14 18 19 23 27 1 5 9 24 25 20 6 7 2 15 16 11 IMPOSSIBLE 8 3 4 17 12 13 26 21 22 35 30 31 44 39 40 19 23 27 28 32 36 37 41 45 1 5 9 10 14 18 42 43 38 24 25 20 6 7 2 33 34 29 15 16 11