Can you partition the numbers 1, 2, 3, ... nē in n separate subsets, each with n numbers, all subsets having the same sum?

In the array below, each column represents one set :

       1                2                3           .....       n       

     2n             n + 1          n + 2        .....    2n - 1 

   3n - 1            3n           2n + 1         .....   3n - 2 

...........        ...........       ..........         .....    ..........

...........        ...........       ..........         ......   ..........

 (n-1)n + 2   (n-1)n + 3   (n-1)n + 4  ..... (n-1)n + 1 

The columns of the above array constitute the desired grouping.

To prove this, we write another array that is derived from the previous one in the following way : Subtract 0 from each element in the first row, subtract n from each element in the second row, subtract 2n from each element in the third row, ..., subtract (n-1)n from each element in the last (nth) row.

This gives :

     1           2           3          .....      n    

     n           1           2          .....      n-1 

    n-1         n           1          .....      n-2 

..........    .........   .........       ......  ............

..........    .........   .........       ......   ............

     2           3           4          ......        1    

Note that each column in the derived array is a permutation of the numbers 1, 2, ..., n. Hence the sum of the elements in each column of the original array is :

S = (1 + 2 + 3 + ... + n) + (0 + n + 2n + ... + (n-1)n) =  n(n + 1)/2  + n * n(n - 1)/2 = n(n^2 + 1)/2.

 

Posted by pcbouhid on 2005-08-29 03:06:53