Here's a sketch: Suppose $ n^2$ can be expressed as the sum of $ n^2-t$ squares, where $ m^2 \leq m \leq (m+1)^2-2$. Then the largest square that can occur in such a representation is $ m^2$, so if the square $ j^2$ occurs $ a_{j}$ times in the representation, then we seek non-negative solutions to the system: $ \sum_{1 \leq j \leq m} j^2 a_{j} = n^2$ ... (1), and $ \sum_{1 \leq j \leq m} a_{j} = n^2 - t$ ... (2). Subtracting (2) from (1): $ \sum_{2 \leq j \leq m} (j^2-1) a_{j} = t$ ... (3), where $ \sum_{2 \leq j \leq m} a_{j} \leq n^2 - t$, or alternatively: $ t + \sum_{2 \leq j \leq m} a_{j} \leq n^2$ ... (4). Clearly, we can find non-negative integer solutions to (3) and (4), iff we can express $ n^2$ as a sum of $ n^2-t$ squares. (a) To show that $ S(n) \leq n^2-14$, it suffices to prove $ n^2-13$ is impossible, i.e. $ t=13$ doesn't work, i.e. the equation $ 3a_{2} + 8a_{3} = 13$ has no solutions, which is clearly true. Now to find solutions to (3) and (4), for a specific value of $ t$, where $ m^2 \leq t \leq (m+1)^2 - 2$: let $ a_{m} = 1$, and let's try to express the remaining value, $ t-m^2$, as multiples of $ 3$ and $ 8$. Since any number that is at least $ 13$ can be expressed as $ 3a_{2} + 8a_{3}$ for some values of $ a_{2}$ and $ a_{3}$, this is possible when $ t - m^2 \geq 14$. If $ t - m^2 \leq 13$, let's instead let $ a_{m-1}=1$, and express the remainder $ t - (m-1)^2$ in the form $ 3a_{2} + 8a_{3}$. We need to find out for what values of $ t$ this construction works and satisfies the equation (4): $ t + \sum_{2 \leq j \leq m} a_{j} \leq n^2$. Let's do some computations: For any $ x \geq 14$, we can express $ x = 3a_{2} + 8a_{3}$, where $ a_{2} \leq 7$, so then $ a_{2} + a_{3} \leq 7 + \frac {x-21}{8} = \frac {x+35}{8}$. If $ t - (n-1)^2 \leq 13$, and $ m^2 \leq t \leq (m+1)^2 - 2$, we let $ a_{m-1} = 1$, and then we can find suitable $ a_{2}, a_{3}$ so that $ a_{2} + a_{3} \leq \frac {t - (m-1)^2 + 35}{8} \leq \frac {(m+1)^2 - 2 - (m-1)^2 + 35)}{8} = \frac {4m+33}{8} \leq \frac {4n+33}{8}$. Then, $ \sum_{2 \leq j \leq m} a_{j} = 1 + a_{2} + a_{3} < \frac {4n+41}{8}$, and so $ t+ \sum_{2 \leq j \leq m} a_{j} \leq (n-1)^2 + 13 + \frac {4n+41}{8} < n^2$ for $ n \geq 13$. That means, for $ 14 \leq t \leq (n-1)^2 + 13$, we have taken care of all cases. Let's see what we can do with the same strategy for $ (n-1)^2 + 13 < t < n^2$: here let $ a_{n-1} = 1$, and we can express $ t - (n-1)^2 = 3a_{2} + 8a_{3}$, so that $ \sum_{2 \leq j \leq n} a_{j} = 1+ a_{2} + a_{3} < 1 + \frac { t - (n-1)^2 + 35 }{8} < 1 + \frac { n^2 - (n-1)^2 + 35}{8} < \frac {n}{4} + 6$. That means, when $ t < n^2 - \frac {n}{4} - 6$, then $ t + \sum_{2 \leq j \leq n-1} a_{j} < n^2$, so we have taken care of these cases as well. So what remains is: $ t > n^2 - \frac {n}{4} - 6$, so we need to express $ n^2$ as $ k$ squares for $ k \leq \frac {n}{4} + 6$. (b) A little experimentation suggests $ n=13$ works. In light of previous results, we only need to check that $ 13^2$ can be expressed as sum of $ k$ squares for $ k \leq \frac {n}{4} + 6 = 8$ squares. We can compute these constructions: $ 169 = 144 + 25 = 144 + 9 + 16 = 121 + 16 + 16 + 16 = 100 + 36 + 16 + 16 + 1 = 144 + 9 + 4 + 4 + 4 + 4 = 144 + 9 + 9 + 4 + 1 + 1 + 1 = 144 + 4 + 4 + 4 + 4 + 4 + 4 + 1$. Thus $ n=13$ does work. (c) Suppose $ N = k$ works. Then if $ k$ is odd, $ N = \frac {k^2 + 1}{2}$ works, since: $ ( \frac {k^2 + 1}{2} )^2 = k^2 + ( \frac {k^2 - 1}{2} )^2$, and we can express $ k^2$ as the sum of $ r$ non-zero squares for $ r = 0, 1, 2 ... k^2 - 14$. Thus, by tagging along $ ( \frac {k^2 - 1}{2} )^2$ to the representation of $ k^2$ as $ r$ squares, for $ r < k^2 - 14$, we can express $ (\frac {k^2 + 1}{2})^2$ as the sum of $ r$ squares, for $ r = 0, 1, 2 ... k^2 - 13$. By using above results, we only need to make sure that it is the sum of $ r$ squares for $ r < \frac {k^2 + 1}{8} + 6$, which follows from what we have just done. Using similar method, if $ k$ is even $ N = \frac {k^2 + 4}{4}$ works, since $ (\frac {k^2+4}{4})^2 = (\frac {k^2-4}{4})^2 + k^2$. Thus starting from $ n=13$, we can keep constructing larger values of $ n$ which work ($ \frac {13^2 + 1}{2}$ and so on).

$\bullet$ Representing $n^2$ as a sum of $n^2-13$ squares is equivalent to represent $13$ as sum of numbers of the form $x^2-1$, and that's impossible. $\bullet$ Define $\mathcal{S}:=\{n\in \mathbb{N}:S(n)=n^2-14\}$. Let's prove that $13 \in \mathcal{S}$: first, consider the following identities $13^2=8^2+8^2+4^2+4^2+3^2$ $13^2=8^2+8^2+4^2+4^2+2^2+2^2+1^2$ $13^2=8^2+8^2+4^2+3^2+3^2+2^2+1^2+1^2+1^2$ Now, if a representation of $n^2$ has $k$ positive squares and one of them is even, then $n^2$ can be represented also by $k+3$ squares, indeed $(2m)^2=m^2+m^2+m^2+m^2$. We have only to show that $13^2$ is really representable as sum of $2,3,4,6$ positive squares, and that's true indeed $13^2=12^2+5^2=12^2+4^2+3^2=11^2+4^2+4^2+4^2$ and $13^2=12^2+3^2+2^2+2^2+2^2+2^2$. $\bullet$ We claim that if $n \in \mathcal{S}$ and $n\ge 13$ then also $2n \in \mathcal{S}$. We notice that if $n^2=\sum_{i=1}^r{x_i^2}$ then also $(2n)^2=\sum_{i=1}^r{(2x_i)^2}$. Replacing $(2x_i)^2$ with $4\cdot x_i^2$. This gives a representation of $(2n)^2$ as sum of $k$ squares for any $k\le 4n^2-62$. Further, we observe that each number $m\ge 14$ can be written as sum of $k\ge m$ numbers of the form $x^2-1$. Therefore if $k\le 4n^2-14$, it follows that $4n^2-k$ is a sum of $k$ numbers of the form $x^2-1$, and consequently $4n^2$ is a sum of $k$ squares.

This is a terribly worded solution, but I believe it works... a I prove that $S(n)=n^2-13$ is absurd proving the rest of this part by definition of $S(n)$. Start with the set with $n^2-13$ elements $\{1^2, 1^2, \cdots, 1^2\}$. We are going to have to add some to some elements to get to the desired value. Changing $1^2$ to $4^2$ gives us a change of $15$, so we are above our upper bound. Changing $1^2$ to $3^2$ gives us a desire of adding in $5$ more. However, changing another $1$ to $3$ doesn't work and another $1$ to $2$ is going to give us $3$ more, which done twice doesn't work. Therefore, no such operation works which will increase $n^2-13$ to $n^2$, and we are done. $\Box$ b Okay so dinoboy told me $13$ worked and gave me some ideas on how to prove it, let's use that here... Okay so $13^2=13^2$, $13^2=5^2+12^2$, $13^2=12^2+3^2+4^2$, $13^2=8^2+10^2+4^2+1^2$ Now, use the following factorization dinoboy found: $13^2=8^2+8^2+4^2+4^2+3^2$ Using this, we get $13^2=8^2+8^2+4^2+5^2$. I define any number $k$ such that $n^2$ can be expressed as the sum of to be a brilliant number base $n$. Therefore, we are going to get $8^2=64*1^2$ so we get $64$ there, and we have two of those so $128$. Then $4^2+4^2=32$ so we get $32$ more. Therefore, we get $161$, and the value we desired was $155$ so therefore this is more (the max bound doesn't mean larger values can't work, remember the definition). This is for the first value of $13^2$. Therefore, we have proved that $2\pmod{3}$ always gives a brilliant number base $n$. Now, we prove $1\pmod{3}$ always works. To do this, note that $13^2=8^2+8^2+4^2+5^2$. We are going to get $128+16+1=145$ brilliant numbers base $n$. We desire to have $169-14=154$ values brilliant numbers base $n$, so we have to prove the next few. $n^2-14$ works is as follows: have a set of $n^2-14$ ones, then change a $1$ to a $3$ giving us+8 and change 2 $1$'s to a $2$ giving us the desired. For remaining values, change a $1$ to a $2$ proving it works. For proving $0\pmod{3}$, note that $13^2=8^2+8^2+4^2+3^2+3^2+2^2+1^2+1^2+1^2$ This has $9$ numbers in it, so we have to prove for $6$ it works too, which is done by $13^2=12^2+3^2+4^2$ and use $12^2=6^2+6^2+6^2+6^2$. From this sum, we get $128+16+4+5=153$ from using basic decomposition. Therefore, we are happy because we wanted up to $154$, and we are finally done. So $\boxed{13}$ works yay. c I prove $n$ is a number that works implies $2n$ works also. I prove that $4n^2$ is expressible as the sum of squares for sets with sizes of $4n^2-56$ to $n^2-15$. Also sets with size $n^2-14$ to $1$ work because $n$ works. We prove that $4n^2-56$ works, then $4n^2-57$ and $4n^2-58$ also work. $n^2-14$ is $\{2,2,2,2,\cdots, 4,4,6)\}$ with $n^2-14$ elements ($n^2-17$ $2$'s), $n^2-15$ is going to be $\{2,2,2,2,\cdots, 8\}$ with $n^2-15$ elements $(n^2-16)$ $2's$ (this means that when you square these numbers it has the desired number of elements I will continue using this notation ), and $n^2-16$ is $\{2,2,2,2,2,\cdots, 6,6)\}$ with $n^2-16$ elements and $n^2-18$ $2's$ Therefore $4n^2-56$ is going to be a set with $8$ $2's$, $4$ $3$'s, and $4n^2-68$ $1$'s which has $4n^2-56$ elements, $4n^2-60$ is going to be a set with $4n^2-64$ 1's and an $4$, and $4n^2-64$ is going to be a set with $8$ $3$'s and $4n^2-72$ $12$'s (essentially 4 times of everything in the above sets) We desire to turn these into the respective sets with $n^2-14, n^2-15, n^2-16$ element sets with sum $4n^2$, decreasing it by $3$ each time proving it works for $0,1,2$ $\pmod{3}$. We decrease the number of elements by changing every group of $4$ into one group. Therefore, changing a $2$ to a $1$ changes it by $3$, then do this enough time to be able to switch a $4$ to a $2$ without missing any numbers, and continue doing this and we are done $\Box$. We therefore have to prove it works for $4n^2-55$ to $4n^2-14$. For $4n^2-14$, we are going to use $\{1,1,1,1,\cdots, 2,2,3\}$ with $4n^2-14$ elements. The operation decreasing set size by $3$ works here ($1$ to $4$ then remove three $1$'s), so we just prove that $4n^2-14, 4n^2-15, 4n^2-16$ work and use this decreasing function thing (and use $n\ge 13$ so we have enough $1$'s). For $4n^2-15$, we get $\{1,1,1,1,\cdots, 4\}$, and for $4n^2-16$ we get $\{1,1,1,1,\cdots, 3,3\}$ therefore we are done $\Box$

d) Prove that if $S(n)\ge n^2/4$ then $n\in\mathcal{S}$.

not a good problem tbh

HarvardMit wrote: not a good problem tbh not a good opinion tbh

Another solution for part (c): First we observe that Lemma. Suppose $n\geq 6$ and $11\leq k\leq n^2-14$. Then, $n^2$ can be written as a sum of $k$ positive squares. Proof. We wish to find positive integers $a_1,a_2,\ldots,a_{\ell}$ ($\ell\leq k$) such that $$ (a_1^2 - 1) + (a_2^2 - 1) + \cdots + (a_{\ell}^2-1) = n^2 - k. $$If $11\leq k\leq n^2-17$, then we can find an integer $0\leq r\leq 7$ such that $n^2-k-3r\equiv 3\pmod{8}$ and $n^2-k-3r\geq -4$, so if we take $a_1 = a_2 = \cdots = a_r = 2$, then the equation becomes $$ (a_{r+1}^2 - 1) + \cdots + (a_{\ell}^2-1) = n^2 - k - 3r, $$Now we have $n^2-k-3r+4\geq 0$. By Lagrange's four-square theorem, we can find non-negative integers $a_{r+1},\ldots,a_{r+4}$ such that $$ (a_{r+1}^2 - 1) + \cdots + (a_{r+4}^2-1) = n^2 - k - 3r, $$but these four numbers must be non-zero because $n^2-k-3r\equiv 3\pmod{8}$, so we are done with the cases $11\leq k\leq n^2-17$. For the case $k = n^2-16$, take $a_1 = a_2 = 3$; for the case $k = n^2-15$, take $a_1 = 4$; for the case $n=k^2-14$, take $a_1 = 2$, $a_2 = 3$. Q.E.D. In view of the lemma, it suffices to find integers $n\geq 6$ so that $n^2$ can be written as a sum of $k$ positive squares for all $k\leq 10$, but this is easy: define a sequence $\{a_i\}$ of odd positive integers and a sequence $\{b_i\}$ of even positive integers as follows: $a_1 = 3$, and, for $i=1,2,3,\ldots$, $b_i = \frac{a_i^2-1}{2}$ and $a_{i+1} = b_i+1$. It is easy to check that $a_{i+1}^2 = a_i^2 + b_i^2$, and hence for $i\geq 10$, $$ a_i^2 = a_{i-1}^2 + b_{i-1}^2 = a_{i-2}^2+b_{i-2}^2 + b_{i-1}^2 = \cdots = a_{i-9}^2+b_{i-9}^2 + \cdots + b_{i-1}^2, $$so $n$ be any of the numbers $a_{10},a_{11},a_{12},\ldots$.

Here's $c.$ If $$n^2=x_1^2+\dots +x_r^2,$$it follows that $$(2n)^2=(2x_1)^2+\dots+(2x_r)^2.$$Replacing $(2x_i)^2$ with $x^2_i+x^2_i+x^2_i+x^2_i$ as long as it is possible we can obtain representations of $(2n)^2$ consisting of $r, r+3,\dots, 4r$ squares. This gives representations of $(2n)^3$ into $k$ squares for any $k\leq 4n^2-62.$ Also notice that every number $m\geq 14$ can be expressed as a sum of $k\geq m$ numbers of the form $x^2-1: x\in \mathbb{N},$ which is clear to see. It follows that if $k\leq 4n^2-14,$ then $4n^2-k$ is a sum of $k$ numbers of the form $x^2-1,$ which implies that $4n^2$ is a sum of $k$ squares. So when $s(n)=n^2-14,$ for any $n\geq 13,$ we have $s(2n)=(2n)^2-14.$ And Q.E.D.