wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> How Many Squares
        
(Message started by: Virgilijus on Jan 2^nd, 2015, 10:54am)

Title: How Many Squares
Post by Virgilijus on Jan 2^nd, 2015, 10:54am

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?

Title: Re: How Many Squares
Post by rmsgrey on Jan 4^th, 2015, 4:25pm

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...

Title: Re: How Many Squares
Post by Virgilijus on Jan 4^th, 2015, 4:46pm

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

Title: Re: How Many Squares
Post by rloginunix on Jan 11^th, 2015, 10:19pm

Eliminating rotations mentioned by rmsgrey and counting only the squares with integral side lengths 1xK where K runs from 1 to n we get:

http://www.ocf.berkeley.edu/~wwu/YaBBAttachments/rlu_sqsq.png

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)² 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 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifⁿ_K=1K²

You can look up that sum or you can deduce it by observing that:

(n + 1)³ = n³ + 3n² + 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)³ = n³ + 3n² + 3n + 1
n³ = (n - 1)³ + 3(n - 1)² + 3(n - 1) + 1
(n - 1)³ = (n - 2)³ + 3(n - 2)² + 3(n - 2) + 1
(n - 2)³ = (n - 3)³ + 3(n - 3)² + 3(n - 3) + 1
...
2³ = 1³ + 3*1² + 3*1 + 1

Observe that when you sum these equations n³ in the first equation on the right side of the equal sign will cancel out with n³ in the second equation on the left side of the equal sign. And so will (n - 1)³ and (n - 2)³ and so on. In other words diagonally nearest "upper right" and "lower left" terms will cancel out. What will remain is:

(n + 1)³ = 1³ + 3S₂ + 3S₁ + n

where S₁ - 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₂ (the sum of second powers sought after) we get:

N = S₂ = n(n + 1)(2n + 1)/6

Title: Re: How Many Squares
Post by Virgilijus on Jan 12^th, 2015, 3:17am

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.