construct large square using smaller squares

问题:

I have a large square of edge N. I want to calculate the number of small squares required to construct this large square using smaller squares with edge values from 1 to N-1. I have unlimited number of such small squares.The only restriction is that I have to use the minimum number of smaller squares.For example,if N=3, I can construct this square using 5 squares of size 1 and 1 square of size 2. How can I solve this problem for any given value of N?

回答1:

For even N, you can use 4 squares of side N/2, which is the minimum possible. For odd N, it's a bit more complicated. One possible solution for odd N is one square of (N+1)/2, 3 of (N-1)/2, and N-1 of size 1, but I'm not entirely sure that's minimal... For example, if N=9, this would give 12 squares, where a better solution of 9 3x3 squares exists. It might be the best solution for prime N, though.