BRC Problem of the Month - February 2001

How many distances can you find?

(a) In a 4 by 4 lattice like the one below, there are 25 points.  How many different distances (using Euclidean distance, not the taxicab distance!) are there between pairs of distinct points?  Explain.

(b) How many different distances are there between pairs of distinct points in a 5 by 5 lattice?  A 6 by 6 lattice?  A n by n lattice?  Explain, and prove your claim in the general case is correct.