Prove that for every integer $k$, there exists a integer $n$ which can be expressed in at least $k$ different ways as the sum of a number of squares of integers (regardless of the order of additions) where the additions are all in different pairs.
Problem
Source: 2007 Estonia Open Olympiad Junior p10
Tags: combinatorics, Sum, number theory, Perfect Square