sum of ten squares You are given an unlimited supply of $1\times 1,2\times 2,3\times 3,4\times 4,5\times 5,6\times 6$ squares.Find a set of ten squares whose areas add up to $48$.If not the whole solution,even a little prod in the right direction would help.
 A: One solution is obvious:
8 squares of 1x1
1 square of 2x2
1 square of 6x6
$$ Area = (8 \times 1) + (2 \times 2) + (6 \times 6) = 48$$
A: Here is another, more sophisticated answer: $23=1+4+9+9$ is the sum of four non-zero squares and so $48=23+23+1+1=4\times 1 + 2\times 4 + 4\times 9$ is the sum of ten squares.
The relevant result is Lagrange's four-square theorem: Every number is a sum of four squares; every number not of the form $4^k(8m + 7)$ is a sum of four non-zero squares.
I chose $23$ because it is of the correct form and is near $48/2$. I was lucky.
A: These are all the solutions:
1       2       3       4       5       6
-----------------------------------------
3       5       1       1       0       0
4       2       4       0       0       0
6       2       1       0       1       0
7       0       1       2       0       0
8       1       0       0       0       1

If you only want one solution, you can try the greedy approach of trying to find a solution with one $6 \times 6$ piece. You're then left with the problem of expressing $12=48-36$ with nine pieces, which leads you to the answer by alex23 (the last row in the table).
This combination of greedy and dynamic programming finds all the solutions, but there is probably a lot of book keeping to do. (I just wrote a simple program :-)
