9.5. Find all natural $n$ such that for any partition of the set of all natural numbers from 1 to $n$ inclusive into two subsets, there will be two distinct numbers in one of the subsets whose sum is a square of a natural number.
Answer. $n \geq 15$.

Solution. Let's give the process a scientific flavor. We will construct a graph where the vertices are the numbers from 1 to $n$, and vertices $a$ and $b$ are connected by an edge if and only if the sum of these numbers is a perfect square of a natural number. For any partition of the numbers from 1 to $n$ into two subsets, we will color the numbers of one of them white and the other black. If the graph does not contain cycles of odd length, then by coloring the vertices of the graph "alternately" in black and white, we will obtain a partition of the set of numbers from 1 to $n$ into subsets of black and white numbers, in which there are no pairs of numbers that sum to a perfect square. Otherwise, in any coloring of the vertices of an odd-length cycle in two colors, there will be two adjacent vertices of the same color, corresponding to numbers that lie in the same subset of the partition and sum to a perfect square.

We will call partitions good if there are no pairs of numbers of the same color that sum to a perfect square. It is clear that a good partition of the numbers from 1 to $n$ immediately gives a good partition for the numbers from 1 to $m$ for all $m \leq n$.

For $n=15$, it is not difficult to notice an odd-length cycle 1-3-6-10-15-1, so for $n \geq 15$, a good partition of the numbers from 1 to $n$ is impossible.

Let $n=14$, and let's verify that there are no cycles in the graph and construct a good partition of all numbers from 1 to 14. The possible perfect squares for $n=14$ can only be $4=1+3$, $9=1+8=2+7=3+6=4+5$, $16=2+14=3+13=4+12=5+11=6+10=7+9$, and $25=11+14=12+13$. Note that the numbers $1,2,4,5,6,7,11,12,13$ appear in the sums twice, the numbers $8,9,10,14$ appear once, and the number 3 appears three times, with a total of 13 sums.

Let's start coloring the numbers according to the rule - two numbers in the same sum are colored in opposite colors. Take a number that appears in the sums once, say 8, it will be white, then 1 is black, 3 is white, 13 and 6 are black, 12 and 10 are white, 4 is black, 5 is white, 11 is black, 14 is white, 2 is black, 6 is white, and 9 is black. All sums are used. All numbers are colored in a good way. To put it scientifically, the corresponding graph is a tree on 14 vertices, with pendant vertices $8,9,10$, and 14 and a unique vertex of degree $3-3$. Let's write down the partition separately: $\{8,3,10,12,5,14,6\}$ and $\{1,6,13,4,11,2,9\}$.

Criterion. Impossibility of partition for $n \geq 15: 3$ points.

Partition for all $n \leq 14: 4$ points.

## Each problem is worth 7 points for 10th grade