k can't be 1. If k=2, we can devided the set M into 2 subsets A,B that satisfy the requirement above. We can suppose 1 is in A, so 3 is in B, so 6 is in A, so 10 is in B ,so 15 is in A. We now have contrast: 1 and 15 are in A. so, k is larger or equal to 3. We can easily observe that : that set M can be devided into 3 subsets that satisfy the requirement above: M1= {1,2,4,6,11,13,16,17,18,22,26,28,29} M2={3,5,7,8,10,12,14,19,21,23,25,27} M3={9,15,20,24,30} Conclude: min k=3.

Let me expand this problem: find the least value of k that: for each subset of M that consists k elements ,there are always a,b that: a>b and a+b is not a perfect square number. M1 shows that k larger or equal to 14.

i have another solution to show that the min is 3 look at the three numbers 6,19,30 if with k=2 it is possible then two numbers are in the same subset .

My solution was the same, to show it is not possible for $k=2$ and give and example for $k=3$

Another example for 3 sets: M1= {1, 2, 4, 6, 9, 11, 13, 17, 18, 20, 22, 28} M2={3, 5, 7, 8, 10, 12, 14, 16, 19, 21, 23, 25, 27} M3={15, 24, 26, 29, 30} Am I right?

Yes.Belarus math olympiad 2005