wu :: forums
« wu :: forums - Anti-magic Matrix »

Welcome, Guest. Please Login or Register.
Mar 19th, 2024, 12:09am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium
(Moderators: Grimbal, SMQ, william wu, towr, Eigenray, Icarus, ThudnBlunder)
   Anti-magic Matrix
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Anti-magic Matrix  (Read 1279 times)
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Anti-magic Matrix  
« on: Aug 29th, 2004, 1:51pm »
Quote Quote Modify Modify

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?
 
« Last Edit: Aug 29th, 2004, 8:46pm by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: Anti-magic Matrix  
« Reply #1 on: Aug 29th, 2004, 3:55pm »
Quote Quote Modify Modify

can a row sum equal a column sum?
 
probably not, or it would be too easy.
« Last Edit: Aug 29th, 2004, 3:57pm by Grimbal » IP Logged
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Anti-magic Matrix  
« Reply #2 on: Aug 29th, 2004, 8:46pm »
Quote Quote Modify Modify

on Aug 29th, 2004, 3:55pm, Grimbal wrote:
can a row sum equal a column sum?

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

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: Anti-magic Matrix  
« Reply #3 on: Aug 30th, 2004, 4:26am »
Quote Quote Modify Modify

For an even n, I found a pattern:
::
+ + + + + +
+ + + + 0 -
+ + + + - -
+ + 0 - - -
+ + - - - -
0 - - - - -
::
« Last Edit: Aug 30th, 2004, 4:26am by Grimbal » IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Anti-magic Matrix  
« Reply #4 on: Aug 31st, 2004, 10:57am »
Quote Quote Modify Modify

Only for even n can we have anti-magic squares:
 

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.
 

« Last Edit: Aug 31st, 2004, 11:00am by Aryabhatta » IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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