There is a grid of 20 squares by 10 squares. How many different rectangles are possible?
(Note that square is a rectangle).
(In reply to
Puzzle Answer by K Sengupta)
Let us consider a grid of M squares by N squares with M>N
Then, all the distinct shapes of the individual rectangles (including square) must correspond to:
1x1, 1x2, ....., 1xN, 2x1, 2x2, ......, 2xN, Mx1, Mx2, ......, MxN
Then, the total number of individual rectangles
= 1*1+ 1*2 + .......+ 1*N+ 2*1+2*2+.....+2*N+........+M*1+M*2+.....+M*N
= 1(1+2+......+N) +2(1+2+.....+N)+.....+M(1+2+.....+N).
= (1+2+.....+N)*(1+2+......+M)
= comb(N+1, 2) * comb(M+1, 2)
Substituting M=20 and N=10 in the general case, we have:
The required # rectangles:
= comb(11,2)*comb(21,2)
={(11*10)/2} * {(21*20)/2}
= 55 *210
= 11,550
General Case and Puzzle Solution
