Solution at http://www.kalva.demon.co.uk/imo/isoln/isoln926.html (a) Let $ N = n^2$. Suppose we could express N as a sum of N - 13 squares. Let the number of 4s be a, the number of 9s be b and so on. Then we have 13 = 3a + 8b + 15c + ... . Hence c, d, ... must all be zero. But neither 13 nor 8 is a multiple of 3, so there are no solutions. Hence S(n) ≤ N - 14. A little experimentation shows that the problem is getting started. Most squares cannot be expressed as a sum of two squares. For $ N = 13^2 = 169$, we find: 169 = 9 + 4 + 4 + 152 1s, a sum of 155 = N - 14 squares. By grouping four 1s into a 4 repeatedly, we obtain all multiples of 3 plus 2 down to 41 (169 = 9 + 40 4s). Then grouping four 4s into a 16 gives us 38, 35, ... , 11 (169 = 10 16s + 9). Grouping four 16s into a 64 gives us 8 and 5. We obtain the last number congruent to 2 mod 3 by the decomposition: $ 169 = 12^2 + 5^2$. For the numbers congruent to 1 mod 3, we start with N - 15 = 154 squares: 169 = 5 4s + 149 1s. Grouping as before gives us all 3m + 1 down to 7: 169 = 64 + 64 + 16 + 16 + 4 + 4 + 1. We may use $ 169 = 10^2 + 8^2 + 2^2 + 1^2$ for 4. For multiples of 3, we start with N - 16 = 153 squares: 169 = 9 + 9 + 151 1s. Grouping as before gives us all multiples of 3 down to 9: 169 = 64 + 64 + 16 + 9 + 9 + 4 + 1 + 1 + 1. Finally, we may take $ 169 = 12^2 + 4^2 + 3^2$ for 3 and split the $ 4^2$ to get $ 169 = 12^2 + 3^2 + 2^2 + 2^2 + 2^2 + 2^2$ for 6. That completes the demonstration that we can write $ 13^2$ as a sum of k positive squares for all k <= $ S(13) = 13^2 - 14$. We now show how to use the expressions for $ 13^2$ to derive further N. For any N, the grouping technique gives us the high k. Simply grouping 1s into 4s takes us down: from 9 + 4 + 4 + (N-17) 1s to (N-14)/4 + 6 < N/2 or below; from 4 + 4 + 4 + 4 + 4 + (N-20) 1s to (N-23)/4 + 8 < N/2 or below; from 9 + 9 + (N-18) 1s to (N-21)/4 + 5 < N/2 or below. So we can certainly get all k in the range (N/2 to N-14) by this approach. Now suppose that we already have a complete set of expressions for $ N_1$ and for $ N_2$ (where we may have $ N_1 = N_2$). Consider $ N_3 = N_1N_2$. Writing $ N_3 = N_1$( an expression for $ N_2$ as a sum of k squares) gives $ N_3$ as a sum of 1 thru k_2 squares, where $ k_2 = N_2 - 14$ squares (since $ N_1$ is a square). Now express $ N_1$ as a sum of two squares: $ n_1^2 + n_2^2$. We have $ N_3 = n_1^2$(a sum of k_2 squares) + $ n_2^2$(a sum of k squares). This gives N_3 as a sum of $ k_2 + 1$ thru $ 2k_2$ squares. Continuing in this way gives N_3 as a sum of 1 thru $ k_1k_2$ squares. But $ k_i = N_i - 14 > 2/3 N_i$, so $ k_1k_2 > N_3/2$. So when combined with the top down grouping we get a complete set of expressions for N3. This shows that there are infinitely many squares N with a complete set of expressions, for example we may take N = the squares of $ 13, 13^2, 13^3, ... .$

Solved c here, I believe the others are not that hard.