9.5 What is the largest number of non-overlapping groups into which all integers from 1 to 20 can be divided so that the sum of the numbers in each group is a perfect square?
Solution: A group consisting of a single number can only be formed by 4 squares. The remaining 16 numbers must be divided into groups of at least two. Therefore, there will be no more than 12 groups in total. Let's check that exactly 12 groups are not possible. Indeed, in such a case, the numbers 1, 4, 9, 16 would form separate groups, and the remaining numbers would be divided into pairs. Then, the number 8 can only be paired with 17, and the number 19 can only be paired with 6, so the number 10 can only be paired with 15. The number 12 can only be paired with 13, the number 18 only with 7, the number 20 only with 5, and then the number 11 can only be paired with 14. Thus, for all non-squares except 2 and 3, we have uniquely restored the pairs, but 2 and 3 cannot form a group because their sum is not a square. Contradiction.

An example of a partition into 11 groups is the specified partition of non-squares into pairs, and the numbers 2 and 3 are combined into a group with 4.

## Criteria:

- Only proved that there are no more than 11 groups, no example provided - 4 points;
- Provided an example, but did not prove that 12 groups are not possible - 2 points.