For $n\ge 6$, can we partition the set $\{1 , 4 , 9 , ...,n^2\}$ into two subsets whose sums are equal or differ by one?

250 Views Asked by At

For $n\ge 6$, can we partition the set $\{1 , 4 , 9 , ...,n^2\}$ into two subsets such that the sums of the elements in the two subsets are equal or differ by one?

For example : for $n = 10$, we can form the subsets $S_1 = \{100 , 64 , 25 , 4\}$ and $S2 = \{1 , 9 , 16, 36, 49, 81\}$. $S_1$ adds up to $193$ and $S_2$ adds up to $192$.

Can we also identify the elements that we can assign to individual subsets that satisfies this property?

2

There are 2 best solutions below

3
On

The difference of sums is of the from $S:=\sum_{k=1}^n s_kk^2$ where each $s_k=\pm1$. Our task is to find $s_k$ such that the sum is $0$ or $1$.

Observe that $$\tag1a^2-(a+1)^2-(a+2)^2+(a+3)^2=4.$$ Therefore, we can pick four consecutive signs such that they contribute either $+4$ or $-4$. Hence with $8$ consecutive signs, we can achieve zero contribution. Here are the smallest non-negative sums we can achieve for some small $n$ with the eight distinct residues $\bmod 8$: $$ \begin{align}S_0&=0&=0\\ S_1&=1^2&=1\\ S_6 &= 1^2-2^2{+3^2-4^2-5^2+6^2}&=1\\ S_7 &= 1^2+2^2-3^2{+4^2-5^2-6^2+7^2}&=0\\ S_{10}&=-1^2+2^2-3^2-4^2{+5^2-6^2-7^2+8^2}-9^2+10^2&=1\\ S_{11}&=-1^2+2^2-3^2-4^2-5^2+6^2+7^2+8^2-9^2+10^2-11^2&=0\\ S_{12}&=-1^2-2^2-3^2-4^2-5^2-6^2-7^2-8^2+9^2+10^2-11^2+12^2&=0\\ S_{13}&=-1^2-2^2-3^2-4^2-5^2-6^2-7^2+8^2+9^2-10^2+11^2+12^2-13^2&=1 \end{align}$$ We conclude that we can reach sum $=0$ or $=1$ at least when $n$ si one of $0,1,6,7,10,11,12,13$ plus a multiple of $8$. In particular, this covers all $n\ge 6$.

0
On

Hagen von Eitzen's analysis can be extended to find subsets whose sums differ by exactly $1$, simply by noticing that $2^2 - 1^2 = 3.$

Thus, for example $1^2 + (3^2 + 6^2)$ must differ from
$2^2 + (4^2 + 5^2)$ by exactly $1$.

Having constructed this baseline example, in a manner (again) very similar to Hagen von Eitzen's analysis, you can (for example) construct
$\{1,3,6,7,10,12,13\}$ and $\{2,4,5,8,9,11,14\}.$