wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> medium >> Anti-magic Matrix
(Message started by: THUDandBLUNDER on Aug 29th, 2004, 1:51pm)

Title: Anti-magic Matrix
Post by THUDandBLUNDER on Aug 29th, 2004, 1:51pm
For which values of n does there exist an nxn matrix A such that:

1) All entries of A are from {-1,0,1}
2) The row sums and the column sums are all pairwise distinct?


Title: Re: Anti-magic Matrix
Post by Grimbal on Aug 29th, 2004, 3:55pm
can a row sum equal a column sum?

probably not, or it would be too easy.

Title: Re: Anti-magic Matrix
Post by THUDandBLUNDER on Aug 29th, 2004, 8:46pm

on 08/29/04 at 15:55:18, Grimbal wrote:
can a row sum equal a column sum?

No, there are 2n different row and column sums.


Title: Re: Anti-magic Matrix
Post by Grimbal on Aug 30th, 2004, 4:26am
For an even n, I found a pattern:
::[hide]
+ + + + + +
+ + + + 0 -
+ + + + - -
+ + 0 - - -
+ + - - - -
0 - - - - -
[/hide]::

Title: Re: Anti-magic Matrix
Post by Aryabhatta on Aug 31st, 2004, 10:57am
Only for even n can we have anti-magic squares:

[hide]
Let p be the missing sum. Then it is clear the the total of the entries of the matrix is -p/2 and p must be even.

We can assume p [le] 0. So the sums 1,2,...n appear in the matrix.

Now consider the rows and columns whose sums are 1,2,...n.
rearrange these rows and columns so that the rows are pushed to left and columns to the top.

Suppose there are r rows and c columns.

The matrix looks like

Code:
[ ][ ]
[ B1 ][ B2 ]
---------------------
[ ][ ]
[ ][ ]
[ B3 ][ B4 ]
[ ][ ]


B1 is the intersection of the r rows (B1 and B3) and c columns (B1 and B2).

So we have that sum of the r rows + c columns
= n(n+1)/2.
Let |Bi| be the sum of entries of block Bi.
Then we have

n(n+1)/2 - |B1| + |B4| = total = -p/2

Now r + c = n. So B1 and B4 are blocks of size rc.
therefore we have that

-p/2 = n(n+1)/2 - |B1| + |B4| [ge] n(n+1)/2 - 2rc
Now rc [le] (r+c)[sup2]/4= n[sup2]/4.
So we have
-p/2 [ge] n(n+1)/2 - n[sup2]/2 = n/2.

This means that p [le] -n.
Which is possible only if p = -n. (as p is one of -n,...,0,1,...n)
Since p is even, we must have that n is even too.

Grimbal's pattern completes the proof that for even n it is possible to do it.

[/hide]



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board