Make It Count!

First we count the rectangles for a complete $20\times 20$ grid. Then we subtract those rectangles which intersect the cut-out square on in one corner; and the same for the other corner. Finally, we add in all rectangles which intersect both squares, because we subtracted them twice.

A rectangle is the intersection of a horizontal strip and a vertical strip. In each case, we can count the possible horizontal strips and vertical strips separate, and multiply.

For the full $20\times 20$ grid, there are

• 20 possible ways to choose a horizontal strip of height 1,

• 19 possible ways to choose a horizontal strip of height 2,

• and so on, to 1 possible way to choose a horizontal strip of height 20.

That gives $1 + 2 + \cdots + 20 = 210$ horizontal strips, and likewise 210 vertical strips, for a total of $N_1 = 210^2 = 44100\ \ \text{rectangles in the large square}.$

We pick one corner square and ask how many rectangles intersect it. There are

• 7 horizontal strips of height 1 that intersect it,

• 7 horizontal strips of height 2 that intersect it,

• etc. to 7 possible strips of height 14 that intersect it,

• 6 possible strips of height 15 the intersect it,

• 5 possible strips of height 16 that intersect it, etc.

That gives $7 + 7 + \cdots + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 20\cdot 7 - (1 + 2 + 3 + 4 + 5 + 6) = 140 - 21 = 119$ horizontal strips that intersect the chosen corner square, and we find the same count for vertical strips. Thus there are $N_2 = 119^2 = 14161\ \ \text{rectangles intersecting a specific corner square}.$

How many rectangles intersect both corner squares? There are

• 1 horizontal strip of height 8 that intersect both,

• 2 horizontal strips of height 9,

• etc. to 7 horizontal strips of height 14,

• 6 horizontal strips of height 15,

• 5 horizontal strips of height 16, etc.

Since $1 + 2 + \cdots + 6 + 7 + 6 + \cdots + 2 + 1 = 49$ , this makes for $N_3 = 49^2 = 2401\ \ \text{rectangles intersecting both corner squares}.$

To finish up, the number of rectangles in the grid is $N_1 - 2N_2 + N_3 = 44100 - 2\cdot 14161 + 2401 = \boxed{18\:179}.$