Author |
Topic: How Many Squares (Read 482 times) |
|
Virgilijus
Newbie
Gender: 
Posts: 11
|
 |
How Many Squares
« on: Jan 2nd, 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 4th, 2015, 4:46pm by Virgilijus » |
 IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: How Many Squares
« Reply #1 on: Jan 4th, 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 4th, 2015, 4:46pm » |
Quote Modify
|
Yes, you're right. Changed the wording to hopefully make it more clear.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: How Many Squares
« Reply #3 on: Jan 11th, 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 =  nK=1K2
You can look up that sum or you can deduce it by observing that:
(n + 1)3 = n3 + 3n2 + 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 = n3 + 3n2 + 3n + 1
n3 = (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
...
23 = 13 + 3*12 + 3*1 + 1
Observe that when you sum these equations n3 in the first equation on the right side of the equal sign will cancel out with n3 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 = 13 + 3S2 + 3S1 + n
where S1 - 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 S2 (the sum of second powers sought after) we get:
N = S2 = n(n + 1)(2n + 1)/6
|
|
IP Logged |
|
|
|
Virgilijus
Newbie
Gender:
Posts: 11
|
|
Re: How Many Squares
« Reply #4 on: Jan 12th, 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 [n-1]x[n-1] squares around it, etc.) but, of course, you still get to the same answer.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print