Author 
Topic: How Many Squares (Read 453 times) 

Virgilijus
Newbie
Gender:
Posts: 11


How Many Squares
« on: Jan 2^{nd}, 2015, 10:54am » 
Quote Modify

Willy Wutang is trying to scrounge up some money for his alimony payments and has decided to sell the rights to some of his land. The land he has is boring (assuming the buyers don't dig too deep) and square, n x n meters. It is also already sectioned off into 1 x 1 meter squared plots. He knows he can sell n^2 parcels of these smallest, indivisible sections of land, but he's feeling devious and wants to push his luck with Johnny Law; he also wants to sell rights to all 2 x 2 plots, and 3 x 3 plots, and all possible unique square plots. If Willy does this, how many unique plots of land can he sell for his n x n meters squared of land? What if he has m x n meters squared?

« Last Edit: Jan 4^{th}, 2015, 4:46pm by Virgilijus » 
IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2865


Re: How Many Squares
« Reply #1 on: Jan 4^{th}, 2015, 4:25pm » 
Quote Modify

There are uncountably many 1x1 plots (orientations range over a quarter circle before symmetry catches up, and, for any given orientation, the northernmost corner of the plot can range over most of the land) unless the land itself is just 1x1. In other words, the problem might want to be rephrased...


IP Logged 



Virgilijus
Newbie
Gender:
Posts: 11


Re: How Many Squares
« Reply #2 on: Jan 4^{th}, 2015, 4:46pm » 
Quote Modify

Yes, you're right. Changed the wording to hopefully make it more clear.


IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: How Many Squares
« Reply #3 on: Jan 11^{th}, 2015, 10:19pm » 
Quote Modify

Eliminating rotations mentioned by rmsgrey and counting only the squares with integral side lengths 1xK where K runs from 1 to n we get: Say the land is 8x8. In the top row (enumerating left to right) there will fit 8 + 1  2 = 7 2x2 squares  their top left vertexes located at r1c1, r1c2, r1c3, etc. Since the land is square the same number applies to the number of 2x2 squares that will fit into the first column (enumerating top to bottom), the total number of 2x2 squares being 7x7 = 49. Though not shown above, in the top row there will fit 8 + 1  3 = 6 3x3 squares and the same number of 3x3 squares will fit into the first column for a total of 36 3x3 squares. Generalizing for K we get (8 + 1  K)^{2} KxK squares summed over K: 64 1x1 sq. + 49 2x2 sq. + 36 3x3 sq. + 25 4x4 sq. + ... + 1 8x8 sq. = 204 squares. Generalizing for an arbitrarily sized chunk of land we get: N = ^{n}_{K=1}K^{2} You can look up that sum or you can deduce it by observing that: (n + 1)^{3} = n^{3} + 3n^{2} + 3n + 1 Now in the expression above (n  1) times replace n with (n  1), (n  2), (n  3), etc. and write the results down (for a total of n equations): (n + 1)^{3} = n^{3} + 3n^{2} + 3n + 1 n^{3} = (n  1)^{3} + 3(n  1)^{2} + 3(n  1) + 1 (n  1)^{3} = (n  2)^{3} + 3(n  2)^{2} + 3(n  2) + 1 (n  2)^{3} = (n  3)^{3} + 3(n  3)^{2} + 3(n  3) + 1 ... 2^{3} = 1^{3} + 3*1^{2} + 3*1 + 1 Observe that when you sum these equations n^{3} in the first equation on the right side of the equal sign will cancel out with n^{3} in the second equation on the left side of the equal sign. And so will (n  1)^{3} and (n  2)^{3} and so on. In other words diagonally nearest "upper right" and "lower left" terms will cancel out. What will remain is: (n + 1)^{3} = 1^{3} + 3S_{2} + 3S_{1} + n where S_{1}  the sum of the first powers of the first n natural numbers is known (Karl Gauss or it too can be deduced via the method just described). Solving the above linear equation for S_{2} (the sum of second powers sought after) we get: N = S_{2} = n(n + 1)(2n + 1)/6


IP Logged 



Virgilijus
Newbie
Gender:
Posts: 11


Re: How Many Squares
« Reply #4 on: Jan 12^{th}, 2015, 3:17am » 
Quote Modify

And you are correct! I visualized the squares being filled in a little differently [you can only fit one nxn square in the very center, four [n1]x[n1] squares around it, etc.) but, of course, you still get to the same answer.


IP Logged 



