9
$\begingroup$

Let $T(n) = 1 + 2 + 3 + \text{...} + n$ be the $n$th triangular number.

For which $n>1$, if any, is it possible to split the first $\frac{n(n+1)}{2}$ positive integers into $n$ sets, all of different sizes, and each of them with elements adding to a perfect square?

What if the squares must all be different?

$\endgroup$
2
  • 3
    $\begingroup$ n = 1 trivially solves both problems. I win. $\endgroup$
    – Bubbler
    Commented Feb 2, 2021 at 22:51
  • 1
    $\begingroup$ @Bubbler You are right. I shall edit accordingly to disregard that trivial case.Sorry! $\endgroup$ Commented Feb 2, 2021 at 23:00

2 Answers 2

9
$\begingroup$

Other than n = 1, it is easy to see that too small n's do not have such sets:

n = 2: sum is 6, which does not have two-squares decomposition.

n = 3: sum is 21, whose only three-squares decomposition is 16 + 4 + 1, but it is impossible because 6 + 5 + 4 < 16, or alternatively, 1 + 2 + 3 > 1 + 4.

n = 4: sum is 55, which has only three distinct four-squares decomposition (25 + 25 + 4 + 1), (36 + 9 + 9 + 1), (49 + 4 + 1 + 1), none of which can solve the problem due to a similar argument.

The first n that has a solution in both parts is

n = 5

which can be solved as follows:

1 = 1
9 = 3 + 6
25 = 2 + 10 + 13
36 = 4 + 5 + 12 + 15
49 = 7 + 8 + 9 + 11 + 14

Given this, I conjecture that

all numbers n >= 5 permit such set partitions (even with the restriction of distinct squares), with at most a small finite number of exceptions

because

1) It is known that every positive integer has one or more four-square decompositions, and n-square decompositions (with n >= 5) will give more and more freedom in the choice of square numbers in the decomposition.

2) Sum of first T(n) numbers is quartic in n, which grows asymptotically faster than the sum of first n squares (which is cubic in n), supporting 1) further.

3) For any given n-square decomposition, having more numbers to choose from for each set means it is more likely to find a set partition fitting the given sums.

$\endgroup$
3
$\begingroup$

I have found the following solutions:

n=6:
9 = 9
16 = 1 + 15
25 = 2 + 3 + 7 + 13
36 = 5 + 12 + 19
64 = 6 + 10 + 14 + 16 + 18
81 = 4 + 8 + 11 + 17 + 20 + 21

n=7:
4 = 4
9 = 1 + 8
36 = 7 + 11 + 18
49 = 5 + 9 + 10 + 25
64 = 3 + 13 + 14 + 15 + 19
100 = 2 + 6 + 16 + 21 + 27 + 28
144 = 12 + 17 + 20 + 22 + 23 + 24 + 26

n=8:
1 = 1
25 = 10 + 15
49 = 6 + 20 + 23
64 = 4 + 7 + 12 + 13 + 28
81 = 3 + 16 + 30 + 32
100 = 5 + 9 + 11 + 14 + 17 + 18 + 26
121 = 2 + 8 + 19 + 24 + 33 + 35
225 = 21 + 22 + 25 + 27 + 29 + 31 + 34 + 36

n=9:
9 = 9
25 = 5 + 7 + 13
49 = 6 + 43
81 = 3 + 19 + 24 + 35
100 = 1 + 10 + 16 + 33 + 40
121 = 2 + 4 + 14 + 15 + 21 + 26 + 39
169 = 12 + 23 + 25 + 30 + 37 + 42
225 = 11 + 17 + 27 + 28 + 29 + 32 + 36 + 45
256 = 8 + 18 + 20 + 22 + 31 + 34 + 38 + 41 + 44

n=10:
36 = 36
49 = 4 + 8 + 15 + 22
64 = 19 + 45
100 = 21 + 31 + 48
121 = 7 + 12 + 16 + 32 + 54
169 = 3 + 5 + 10 + 33 + 34 + 37 + 47
196 = 11 + 14 + 27 + 39 + 52 + 53
225 = 1 + 17 + 18 + 20 + 24 + 29 + 35 + 38 + 43
256 = 9 + 13 + 23 + 25 + 40 + 46 + 49 + 51
324 = 2 + 6 + 26 + 28 + 30 + 41 + 42 + 44 + 50 + 55

I have found solutions for higher $n$ (up to 15), they just take more time. I agree with Bubbler - solutions should exist for all $n \geq 5$, but I don't know how to prove it.

$\endgroup$
1
  • 2
    $\begingroup$ This is insanely interesting, makes me think about how can you prove that there is a solution existing for all $n \geq 5$? $\endgroup$
    – Anonymous
    Commented Feb 3, 2021 at 5:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.