home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / math / 17948 < prev    next >
Encoding:
Internet Message Format  |  1993-01-10  |  2.0 KB
  1. Path: sparky!uunet!spool.mu.edu!caen!uflorida!math.ufl.edu!shadrach.math.ufl.edu!squash
  2. From: squash@math.ufl.edu (Jonathan King)
  3. Newsgroups: sci.math
  4. Subject: Re: Constant-sum table algorithm
  5. Message-ID: <SQUASH.93Jan8163108@poincare.math.ufl.edu>
  6. Date: 8 Jan 93 21:31:08 GMT
  7. References: <79483@hydra.gatech.EDU>
  8. Sender: news@math.ufl.edu
  9. Organization: University of Florida Department of Mathematics
  10. Lines: 48
  11. In-Reply-To: np4@prism.gatech.EDU's message of 8 Jan 93 12:49:33 GMT
  12.  
  13. In article <79483@hydra.gatech.EDU> np4@prism.gatech.EDU (Nick Pomponio) writes:
  14.  
  15.    I would like to generate an NxN table of positive integers such that
  16.    any N entries chosen from the table, with the restriction that no
  17.    two in are in the same row or column, add up to the same value, S.
  18.    The only way I know to construct such a table is to choose 2N integers
  19.    which sum to S, arrange N along the top of the table (one above each
  20.    column), and N along the side (one beside each row), then fill in each
  21.    entry as the sum of it's corresponding row and column heading numbers.
  22.  
  23.    Question: Is there an algorithm for choosing the 2N integers such that
  24.    every resulting number in the NxN table is unique (no repetitions)?
  25.    For my particular case, N^2 << S.
  26.  
  27. Yes.  Call such a set of N entries a "diagonal".
  28. (NB.  Any board whose diagonal-sums are constant can be built by the
  29. algorithm Mr. Pomponio describes.)
  30.  
  31. Consider the board
  32.  
  33.     1        2     ...    N
  34.  
  35.     N+1        N+2        2N
  36.  
  37.     2N+1        2N+2    ...    3N
  38.  
  39.     ...
  40.  
  41.     (N-1)N+1    (N-1)N+2 ...    N^2 .
  42.  
  43.  
  44. Every diagonal of this board sums to  
  45.  
  46.     S' :=   N(N+1)/2  +  N*(N-1)N/2   
  47.         =   N(N^2 + 1) / 2.
  48.  
  49. Moreover, no distinct-entry board consisting of positive integers could have a
  50. smaller diagonal-sum.
  51.  
  52.     Now add a non-negative constant B to every entry in the bottommost row.
  53. Certainly the entries in this new table are distinct, and the diagonal-sum for
  54. this new table is
  55.  
  56.     S  :=   S' + B .
  57.  
  58. So using positive integers as entries, one can obtain a distinct-entry
  59. [diagonal-sum = S] board iff  S is an integer which is
  60. greater-equal  N(N^2 + 1) / 2.            -Jonathan
  61.