wu :: forums
wu :: forums - How Many Squares

Welcome, Guest. Please Login or Register.
Nov 28th, 2023, 5:46pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium
(Moderators: Icarus, towr, ThudnBlunder, SMQ, Eigenray, william wu, Grimbal)
   How Many Squares
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: How Many Squares  (Read 453 times)
Virgilijus
Newbie
*





   


Gender: male
Posts: 11
How Many Squares  
« on: Jan 2nd, 2015, 10:54am »
Quote Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2865
Re: How Many Squares  
« Reply #1 on: Jan 4th, 2015, 4:25pm »
Quote Quote Modify 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: male
Posts: 11
Re: How Many Squares  
« Reply #2 on: Jan 4th, 2015, 4:46pm »
Quote Quote Modify 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 11th, 2015, 10:19pm »
Quote Quote Modify 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: male
Posts: 11
Re: How Many Squares  
« Reply #4 on: Jan 12th, 2015, 3:17am »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board