wu :: forums « wu :: forums - How Many Squares » Welcome, Guest. Please Login or Register. Nov 28th, 2023, 5:46pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register wu :: forums  riddles  medium (Moderators: Icarus, towr, ThudnBlunder, SMQ, Eigenray, william wu, Grimbal)  How Many Squares « Previous topic | Next topic » Author Topic: How Many Squares  (Read 453 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: 2865 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
Uberpuzzler      Posts: 1026 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

 Forum Jump: ----------------------------- riddles -----------------------------  - easy => medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »