Proposed by Daniel Diaz
This problem consists in finding a partition of numbers 1..N into two sets A and B such that:
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.
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).