Counting rectangles
Martin DeMello
By counting all the rectangles on an n by n chessboard in two different
ways, demonstrate that (1+2+3+....+n)^2 = (1^2 + 2^3 + .... + n^3)
--
Martin DeMello
Martin DeMello
> (From Martin Gardner)
> By counting all the rectangles on an n by n chessboard in two different
> ways, demonstrate that (1+2+3+....+n)^2 = (1^2 + 2^3 + .... + n^3)
Hm - no takers? Gardner didn't provide a solution, and I've not been able to
come up with a natural way of getting the n^3 sum yet, but I'd hoped someone
here would.
--
Martin DeMello
Mark J. Tilford
Let k = n+1-m
Subproblem: A set of n consecutive items, how many ways are there to choose at
least m+1 of them which are consecutive?
Answer: Remove the first m of the chosen ones. After that, any set of consecutive
items of length at least one is generated by a unique consecutive set of >m, and
each set of >m generates a unique reduced set, so the sizes of those two sets are
equal. The number of ways to choose one endpoint is (k), the number of ways to
choose the other endpoint is (k-1), but that counts every set twice.
Therefore, the answer is k*(k-1)/2
Getting the n^3 side:
Number of rectangles with smaller side m:
Let k=n+1-m
mxm: k ways to choose which rows are used, k ways to choose which columns
k * k
mx(m+?): k ways to choose rows, (k^2-k)/2 ways to choose columns
(k^3-k^2)/2
(m+?)xm: similarly,
(k^3-k^2)/2
Total: k^2 + (k^3-k^2)/2 + (k^3-k^2)/2 == k^3
--
------------------------
Mark Jeffrey Tilford
til...@ugcs.caltech.edu
Nick Wedd
<martin...@yahoo.com> writes
>Martin DeMello <martin...@yahoo.com> wrote:
>> (From Martin Gardner)
>
>> By counting all the rectangles on an n by n chessboard in two different
>> ways, demonstrate that (1+2+3+....+n)^2 = (1^2 + 2^3 + .... + n^3)
It is not obvious to me what the .... means in (1^2 + 2^3 + .... + n^3).
Nick
--
Nick Wedd ni...@maproom.co.uk
Mark J. Tilford
[ sum (k=1 to n, k) ]^2 == sum (k=1 to n, k^3)
Martin DeMello
Sorry, 1^2 was a typo for 1^3 (prolly should have used sigma notation in the
first place).
--
Martin DeMello
Martin DeMello
<snip>
> Getting the n^3 side:
> Number of rectangles with smaller side m:
> Let k=n+1-m
> mxm: k ways to choose which rows are used, k ways to choose which columns
> k * k
> mx(m+?): k ways to choose rows, (k^2-k)/2 ways to choose columns
> (k^3-k^2)/2
> (m+?)xm: similarly,
> (k^3-k^2)/2
> Total: k^2 + (k^3-k^2)/2 + (k^3-k^2)/2 == k^3
Ah, very nice.
Just for completeness's sake, the other side is trivially obtained by
considering the x and y dimensions of the rectangle separately - there is 1
way to pick a side of size n, 2 ways to pick a side of size n-1, etc.
--
Martin DeMello
Mark J. Tilford
It does the job, but I don't feel its very elegant. Can anyone give a simpler
way to show the result.
Martin DeMello
> On 15 May 2002 15:21:56 GMT, Martin DeMello <martin...@yahoo.com> wrote:
>> Mark J. Tilford <til...@ralph.caltech.edu> wrote:
>>
>><snip>
>>
>>> Getting the n^3 side:
>>
>>> Number of rectangles with smaller side m:
>>> Let k=n+1-m
>>
>>> mxm: k ways to choose which rows are used, k ways to choose which columns
>>> k * k
>>
>>> mx(m+?): k ways to choose rows, (k^2-k)/2 ways to choose columns
>>> (k^3-k^2)/2
>>
>>> (m+?)xm: similarly,
>>> (k^3-k^2)/2
>>
>>> Total: k^2 + (k^3-k^2)/2 + (k^3-k^2)/2 == k^3
>>
>> Ah, very nice.
>>
>> Just for completeness's sake, the other side is trivially obtained by
>> considering the x and y dimensions of the rectangle separately - there is 1
>> way to pick a side of size n, 2 ways to pick a side of size n-1, etc.
> It does the job, but I don't feel its very elegant. Can anyone give a
> simpler way to show the result.
Gotit. Consider, as before, mx(m+r) rectangles, and k defined as (n-m+1).
Then, there are k(k-r) rectangles each of size mx(m+r) and (m+r)xm, r going
from 0 to k-1. Consider a k-cube. Then, one layer of k^2 cells can be
covered with a rectangle of size k(k-r) and one of size kr. Since r goes
from 0 to k-1, we can neatly tile the k cube as shown.
*++++++ <--- mx(n-1) and (m+1)xm
. |
. } r goes from 1 to k
. |
*****++ <--- mx(m+2) and (n-1)xm
******+ <--- mx(m+1) and nxm
******* <--- mxm
(Uniform cross section, depth of k into the screen)
So we have k*k^2 = k^3 rectangles with smaller side m, and we are done.
--
Martin DeMello
Anand Srinivasan
Right hand side can be obtained by counting the number of rectangles that
include some square of the kth row or kth column in a k by k square.
Number of rectangles that include some square of kth column
= sum_{b = 1 to k} kb = k^2(k+1)/2 = k^3/2 + k^2/2
Number of rectangles that include some square of kth row and that dont
include any square of kth column
= sum_{a = 1 to k-1} ka = k^2(k-1)/2 = k^3/2 - k^2/2
Therefore, total number = k^3.
(Clearly, the total number of rectangles in an n by n square is then just
sum_{k=1 to n} k^3.)
-Anand