Author 
Topic: Antimagic Matrix (Read 1023 times) 

ThudnBlunder
wu::riddles Moderator Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489


Antimagic Matrix
« on: Aug 29^{th}, 2004, 1:51pm » 
Quote 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 29^{th}, 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:
Posts: 7499


Re: Antimagic Matrix
« Reply #1 on: Aug 29^{th}, 2004, 3:55pm » 
Quote Modify

can a row sum equal a column sum? probably not, or it would be too easy.

« Last Edit: Aug 29^{th}, 2004, 3:57pm by Grimbal » 
IP Logged 



ThudnBlunder
wu::riddles Moderator Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489


Re: Antimagic Matrix
« Reply #2 on: Aug 29^{th}, 2004, 8:46pm » 
Quote Modify

on Aug 29^{th}, 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:
Posts: 7499


Re: Antimagic Matrix
« Reply #3 on: Aug 30^{th}, 2004, 4:26am » 
Quote Modify

For an even n, I found a pattern: :: + + + + + + + + + + 0  + + + +   + + 0    + +     0      ::

« Last Edit: Aug 30^{th}, 2004, 4:26am by Grimbal » 
IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Antimagic Matrix
« Reply #4 on: Aug 31^{st}, 2004, 10:57am » 
Quote Modify

Only for even n can we have antimagic 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 31^{st}, 2004, 11:00am by Aryabhatta » 
IP Logged 



