Partition the positive integers from $1$ to $30$ inclusive into $k$ pairwise disjoint groups such that the sum of two distinct elements in a group is never the square of an integer. What is the minimum value of $k$?
if $n$ is one of those positive then integers then
Sum of two numbers that do result in a square can only be one of the following $4,9,16,25,36,49$
$n+i=s^2$ for some integer $7\ge{s}\ge1$ and $n,i\le30$
This yield a different number of solution depending on $n$
Let $m$ be the number of solutions for $i$ for each possible $n$
if $n\lt{4}$ then $m=4$
If$4\le{n}\lt{9}$ then $m=3$
If $9\le{n}\lt{16}$ then $m=2$
If $16\le{n}\lt{19}$ then $m=2$
If $19\le{n}\lt{25}$ then $m=3$
If $25\le{n}\le{30}$ then $m=2$
This gives us $37$ pairs of numbers that result in a square
But I don’t know what to do next, hints and solutions would be appreciated.
Taken from the 2006 IWYMIC
Best Answer
This is following the general advice from quarague. Note that this solution tries to show how you actually can solve the problem with heuristics and experience. That differs somehwat from what you would need to write down in the competition.
A 'greedy' algorithm seems to work here; the $1$ must belong to one group, and repeatedly we try and add the next unused number to the group, unless that would give a square sum.
That means we add $2$ to the group, then $3$ can't be added, as $1+3=4$ would produce a square number. $4$ can be added a.s.o., that gives as first group
$$A_1=\{1,2,4,6,9,11,13,17,18,20,22,26,28\}$$
That's 13 of 30 numbers, a good start.
From the remaining numbers I realized that lots of 'large' numbers are not a big problem, as their sum can only be $49$. Since $30$ and $19$ are both not in a group $A_1$ and their sum is $49$, I looked at all the remaining numbers $> 19$, and among them only $24,25$ are a problem. So I just made a snap decision to leave $24$ out so we have
$$A_2=\{21,23,25,27,29,30\} \cup \{\text{some small numbers}\}$$
where the small numbers are chosen just as for $A_1$: We start with the smallest number not yet in a group and add it to $A_2$ as long as that doesn't produce a square sum. This results in
$$A_2=\{3,5,8,10,12,14,21,23,25,27,29,30\}.$$
That's 12 numbers, which leaves us with just 5 numbers not yet in a group:
$$7,15,16,19,24$$
And we are lucky, the sum of any 2 of those is not a square number, so we got our last group:
$$A_3 = \{7,15,16,19,24\}$$
In the competition you just need to present the 3 groups and say that it's easily checked that in each group the sum of 2 different numbers is not a square.
Now the question is if maybe it works with 2 groups $A_1,A_2$? quarague gave the idea: If $1$ is in $A_1$, then $3,8,15,24$ must be in $A_2$. With $3$ in $A_2$, that means $6,13,22$ must be in $A_1$. You get an expanding list of numbers that must belong to each group, and each new number means other numbers must belong to the other group, a.s.o. At this moment we know
$$A_1=\{1,6,13,22,\ldots\}; A_2=\{3,8,15,24,\ldots\}$$
and we have already 'used up' $1$ and $3$ to place numbers in the other group. We continue with $6 \in A_1$, which means $10,19,30$ must be in $A_2$. But since we already know that $15 \in A_2$, that is a contradiction, as $10+15=25$.
In the competition, you don't need to mention all the numbers that haven't been used. You could just write down that $1$ must be in some group, let's call it $A_1$, and then
$$1 \in A_1 \Rightarrow 3,15 \in A_2 \Rightarrow 6 \in A_1 \Rightarrow 10 \in A_2$$
and $10,15 \in A_2$ is a contradiction.