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.
Asked
Active
Viewed 317 times
4
-
2Do they need to tile a particular rectangle? – vadim123 May 16 '13 at 13:01
3 Answers
13
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 :-)
lhf
- 216,483
-
1
-
-
Hmm,that wasn't methodical,now,was it?But thanks for 'the whole solution'. – rahul May 16 '13 at 13:35
-
2
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.
lhf
- 216,483