Processing math: 100%

Proposed by Daniel Diaz

This problem consists in finding a partition of numbers 1..N into two sets A and B such that:

  1. A and B have the same cardinality
  2. sum of numbers in A = sum of numbers in B
  3. sum of squares of numbers in A = sum of squares of numbers in B

There is no solution for N<8.

Here is an example forN=8:A=(1,4,6,7) and B=(2,3,5,8)

Then from N>=8, there is no solution if N is not a multiple of 4.

Generalisation

More constraints can thus be added, e.g also impose the equality on the sum of cubes, …

Let Ck be the constraint about the power k defined as the equality :

ΣN/2i=1Aki=ΣN/2i=1Bki

Condition (a) corresponds to k=0. Condition (b) to k=1. Condition (c) to k=2.

This generalized problem can be seen as a conjunction of constraints Ck until a power P (C0/ C1/ / CP). The above problem corresponds to P=2.

Empirically, I played with P=0,1,2,3,4:

The sums of powers is known :

Recall in our case we need the half sums. The problem has no solution if the above sums are not even numbers. For P = 0 this implies N is a multiple of 2 (groups A and B have the same cardinality). For P = 1 (knowing N is multiple of 2 due to P = 0) then N * (N + 1) / 2 is even iff N is multiple of 4.

Here are the first solutions computed:

From these tests, it seems the smallest N for which a solution exists is 2P+1. Can this be proved ?

After that, it seems there are only solutions for N multiple of 2 (P= 0), 4 (P = 1 or 2), 8 (P = 3 or 4). Is this a constant depending on P ?

Another way to generalize this problem consists in increasing the numbers of groups (for instance consider 3 groups A, B, C).