Lesson 6

Programming problem. One can prove that any positive integer \(n\) can be represented as a linear combination of the squares of the first \(k\) integers, in which all coefficients are \(-1\) and \(1\). In other words, for any integer \(n \ge 1\), there exists a positive integer \(k\) such that in the expression \[\pm 1^{2}\pm2^{2}\pm \dotsb\pm k^{2}\] one can choose the signs so that the result is \(n\). For example, for \(n=6\), the following representation is suitable: \[6=-1^{2}-2^{2}-3^{2}+4^{2}+5^{2}-6^{2}-7^{2}+8^{2} \ .\]

Prove this and implement a program that reads an integer \(1 \le n \le 500\) and outputs the corresponding string of pluses and minuses of length at most \(2n\).

1

+

6

---++--+