# How many unique distances are there in a 5 x 5 grid?

I cannot figure this out:

I have a square in the plane with side length $5$. $A$ and $B$ are points in the square. The coordinates of $A$ and $B$ are always integers.

I want to know how many unique Euclidean distances are possible between $A$ and $B$.

I thought $15$?

Editor note The original ambiguous phrasing of this question and the consequent edits to clarify resulted in conflicting solutions. Please take this into consideration as you vote on the answers.

-
You're not alone, I can't figure out what you're saying either. Distances between what? "Plane of integers?" What does the matrix have to do with this? Please clarify, and include your work on why you think "15". –  rschwieb Aug 10 '12 at 12:44
ok the matrix is not the best describtio, but i couldnt come up with a more appropriate tage –  jorrebor Aug 10 '12 at 12:46
Do you mean we are looking at the lattice of integer coordinates in a five by five square in the plane? Say, a square with vertices $(0,0),(5,0),(0,5)$ and $(5,5)$? And you want to know what the potential Euclidean distances are between points in this square? –  rschwieb Aug 10 '12 at 14:03
yes that is exactly what i mean –  jorrebor Aug 10 '12 at 14:13
@joriki I'm sorry it turned out that way, but I don't accept the entire blame for this. The original question was incomprehensibly phrased, and I really don't know how you could even venture a solution. At the time I asked for clarification your solution was not up, and by the time I received clarification, your solution was up. I'll do my best to fix the problem, though. –  rschwieb Aug 11 '12 at 12:52

Edit: Apparantly, I've misjudged the number of duplicates, e.g. d((0,0),(0,5) = d((0,0),(3,4)), so the following answer's wrong! Thx to Erick Wong for pointing that out.

It's 21 (or 20, depending on whether you count 0 as a distance or not). You have to consider only distances from the point $(0,0)$, since your metric is translation invariant, i.e. $d((a,b),(c,d)) =d((0,0),(c-a,d-b))$ and $d((0,0),(a,b))$ is symmetric with respect reflection among the coordinate axes, i.e.

$$d((0,0),(a,b)) = d((0,0),(a,-b)) = d((0,0),(-a,b)$$

Moreover, you have to take in account that $d((0,0),(a,b)) = d((0,0),(b,a))$. So what you have to count is the number of tupels (a,b) with $0\le a\le b\le 5$, which is

$$\sum_{a=0}^5 \sum_{b=0}^a 1 = \sum_{j=1}^6 j = 21$$

-
Are you sure your sum adds up to $15$? Also, $d([0,0],[3,4]) = d([0,0],[0,5])$? –  Erick Wong Aug 10 '12 at 16:23
@ErickWong I don't know how people are getting 15... did you agree with 20 in my solution? –  rschwieb Aug 10 '12 at 17:01
@rschwieb I agree with your solution entirely and confirmed $20$ by a one-line Octave calculation, just to be sure. –  Erick Wong Aug 10 '12 at 18:12
I'm sure this is the first time I've seen an accepted answer with a negative vote total :-) (and perhaps also the first time an answer of mine had a vote total of $-2$). Interestingly, your answer interprets the question the same way that rschwieb did, but you've got an error in the last equation; the double sum on the left adds up to $21$ -- the sum over $j$ should sum $j+1$ instead of $n$. –  joriki Aug 11 '12 at 10:34
@joriki Oh yeah, you're right. Corrected the answer accordingly. –  roman Aug 12 '12 at 14:32

The problem seems to be solved if you count the number of right triangles with integer length short legs (including length 0 legs) which fit into the square, and then check to see if any of the hypotenuse lengths happen to coincide.

I count 21 such triangles (including degenerate ones), which yield 20 distinct values for the hypotenuse.

The only duplicate distance occured was 5: for example, between (0,0) and (0,5), or else between (0,4) and (3,0).

This is all done with the understanding that we are allowed to pick any integer coordinate point in the square $(0,0), (5,0),(0,5),(5,5)$, so I may be interpreting it differently from other people.

-
Note that for very large grid sizes the duplicates actually dominate: for an $n \times n$ grid there are only about $cn^2 / \sqrt{\log n}$ distances. –  Erick Wong Aug 10 '12 at 16:39

If you count vertical or horizontal distances the values are 0,1,2,3,4,5;

If the horizontal (or vertical) has length 1 and the vertical has length 1, 2, 3, 4, 5 then the distances are $\sqrt{1^2+1^2}=\sqrt{2}, \sqrt{1^2+2^2}=\sqrt{5}, \sqrt{1^2+3^2}=\sqrt{10}, \sqrt{1^2+4^2}=\sqrt{17}, \sqrt{1^2+5^2}=\sqrt{26}$,

If the horizontal (or vertical) has length 2 and the vertical has length 2, 3, 4, 5 then the distances are $\sqrt{2^2+2^2}=\sqrt{8}, \sqrt{2^2+3^2}=\sqrt{13}, \sqrt{2^2+4^2}=\sqrt{20}, \sqrt{2^2+5^2}=\sqrt{29}$,

If the horizontal (or vertical) has length 3 and the vertical has length 3, 4, 5 then the distances are $\sqrt{3^2+3^2}=\sqrt{18}, \sqrt{3^2+4^2}=\sqrt{25}=5, \sqrt{3^2+5^2}=\sqrt{34}$.

If the horizontal (or vertical) has length 4 and the vertical has length 4, 5 then the distances are $\sqrt{4^2+4^2}=\sqrt{32}, \sqrt{4^2+5^2}=\sqrt{41}$.

If the horizontal (or vertical) has length 5 and the vertical has length 5 then the distances are $\sqrt{5^2+5^2}=\sqrt{50}$.

So there are 20 distinct values for the distances between two points.

-
To the downvoters: This answer was in response to the original question, which asked about a "$5$ by $5$ matrix". The answer was invalidated by an edit that affected the meaning of the question and wasn't marked as such.
I count $15$, too. What makes you think that's wrong?