Date: Sun, 27 Apr 1997 09:11:16 -0400
From: Alexander Bogomolny
When you say an mxn grid, do you mean m squares by n squares or m grid lines by n grid lines? I will adopt the former interpretation. Make corrections if necessary.
First solve a simpler problem: a one dimensional analogue. On a line, you are given (n+1) points. How many intervals exist with endpoints at the given set?
Solution:
The left end is chosen arbitrarily from n points (you can't select the rightmost point as the left end.) The right end is selected arbitrarily from the remaining points.
If k is the coordinate of the left end, for
k = 0, there are (n+1 - 1) candidates for the right point
k = 1, there are (n+1 - 2) candidates for the right point
...
k = n-1, there are (n+1 - n) candidates for the right point
The total is the sum: n+(n-1)+(n-2)+...+2+1 = n(n+1)/2.
If the number of points were (m+1), the answer would obviously be m(m+1)/2.
Now return to your 2D problem. On an mxn grid, in order to select a rectangle, you have to independently select its sides to the total of n(n+1)/2 times m(m+1)/2.
These solves 2 out of your four problems. There are fewer squares of course. Let n <= m. For every choice of a side out of n(n+1)/2 possibilities only sides of equal length are allowed in the second dimension.
Let's try to get the 1D result in a different way. Now by fixing the side. In which case the left end defines the right one. If the side of the interval is K, then the left end may be in any of (n+1 - K) positions. K changes from 1 through n. We again get n(n+1)/2.
To count squares, assume n<=m. For every side K, there are (m+1 - K) possible positions for the other side. Thus we get the sum
nm + (n-1)(m-1) + (n-2)(m-2) + ... + 1(m-n+1).
By carrying out multiplications and using the same formula as in 1D, you can get a closed-form formula.
If I were you, I would go an extra mile and establish a formula for the number of triangles in a triangular grid. Look into the simplest case of equilateral triangles.
Best regards,
Alexander Bogomolny
| 40615979 |
