How about this:

  Assume we have a rectangular grid consisting of m vertical lines and n
horizontal lines. All the vertical lines are of equal length and
arranged horizontally, at equal distances from each other. Likewise
all the horizontal lines are of equal length and arranged vertically,
at equal distances from each other. The length of the vertical lines
is the distance between the outermost horizontal lines, and
vice-versa. The two sets of lines is superimposed so that the four
outermost lines coincide at their endpoints, and thus they form a
large rectangle (with all the other lines inside it). No line goes
outside of this rectangle.

  In other words, the grid contains m x n line intersections (and
consequently there are (m-1) x (n-1) small empty rectangles inside the
grid). For example, a standard Go board has a 19 x 19 grid (19
vertical lines and 19 horizontal lines, totaling 361 intersections).

  (While the idea is quite simple, I tried to be as unambiguous as I
could above, which is why the description became somewhat lengthy.)

  Let's define the smallest possible grid to be 2 x 2 (because it's the
smallest that can be formed with lines of non-zero length).

  Such a grid forms many rectangles. A 2 x 2, rather obviously, forms
only one rectangle. However, a 3 x 2 forms 3 rectangles (the two small
rectangles and a third one, which is formed by the outermost lines). A
4 x 2 grid forms 6 rectangles (3 small rectangles, 2 medium-sized and
1 encompassing the whole grid). Likewise a 3 x 3 grid forms 9
rectangles and a 4 x 4 grid forms 36 rectangles. And so on.

  So the task is simple: Write a function f(m,n) which tells how many
rectangles can be found in an m x n grid. (Explain how you came up
with the function).

-- 
                                                          - Warp

Post a reply to this message