19. The 16 small squares shown in the diagram each have a side length of 1 unit.
How many pairs of vertices are there in the diagram whose distance apart is an integer number of units?
A 40
B 64
C 108
D 132
E 16
Solution
C Each pair of distinct vertices taken from the same row or from the same column is an integer number of units ( $1,2,3$ or 4 units) apart. There are 5 vertices in each row and each column, and so 2 vertices may be chosen from the same row or the same column in $\binom{5}{2}=10$ ways. Since there are 5 rows and 5 columns this gives $50+50=100$ pairs of vertices that are an integer number of units apart.
In addition, since $3^{2}+4^{2}=5^{2}$, it follows from Pythagoras' theorem that the opposite vertices of a $3 \times 4$ rectangle are 5 units apart. This gives a further 8 pairs of vertices (forming the end points of the 8 diagonals shown in the diagrams) which are an integer number of units apart.
There are no other Pythagorean triples, that is, positive integers $m, n, q$ such that $m^{2}+n^{2}=q^{2}$, where $m$ and $n$ are both less than 5 . So we have found all the pairs of vertices that are an integer number of units apart. So there are altogether $100+8=108$ pairs of such vertices.