For which n is it possible to split all the integers 1, 2, 3, ..., n into two non-empty disjoint sets such that the product of the sum of the elements in one set and that of those in the other is a perfect square?
2 Answers
It is easy to see that any two-way split S=A+B of the sum S=1+..+n=n(n+1)/2 can be achieved by forming two disjoint subsets. Let A=ac,B=bc with a,b relatively prime AB is a perfect square precisely if a and b are. Therefore
n has the desird property if and only if S has a divisor that is a sum of two squares.
By the
this will be the case
iff S has at least one prime factor that is not congruent 3 mod 4.
Technical subtlety:
The theorem doesn't rule out even powers of primes of the form 4k+3 but that is only because it allows sums where one term is zero.
-
$\begingroup$ I also come up with this solution but I'm still unsure about the first statement: why a and b must be relatively prime? Can c be any integer? $\endgroup$– athinOct 25, 2021 at 3:22
-
$\begingroup$ Precisely, rot13(jul F zhfg unir n snpgbe juvpu vf n fhz bs gjb fdhnerf) i.e. your first spoiler? Shouldn't it be "if" instead of "if and only if"? $\endgroup$– athinOct 25, 2021 at 3:26
-
1$\begingroup$ @athin c is chosen to be the GCD of A and B.other question: 'Orpnhfr F=p(n+o) naq n naq o ner fdhnerf.' $\endgroup$ Oct 25, 2021 at 3:41
Very partial answer:
It is possible for $n=3: [(1,2); (3)]$, for $n=4: [(1); (2,3,4)]$, for $n=5: [(1,2); (3,4,5)]$. I suspect it is possible for all $n \geq 3$, but cannot prove it.
-
2$\begingroup$ What about n = 6 or n = 18? $\endgroup$ Oct 25, 2021 at 2:23
-