Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

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.

share|improve this question
1  
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
1  
@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
show 3 more comments

4 Answers

up vote 0 down vote accepted

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$$

share|improve this answer
2  
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
1  
@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
2  
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
up vote 2 down vote

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.

share|improve this answer
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
up vote 1 down vote

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.

share|improve this answer
up vote 0 down vote

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?

share|improve this answer
well nothing but i wanted a formal proof but i see it know. – jorrebor Aug 10 '12 at 12:52
1  
@jorrebor: Please take more care phrasing your question next time. Your question states twice that you want to know the number of unique distances, and nowhere that you wanted a formal proof. – joriki Aug 10 '12 at 12:54
yes you're right – jorrebor Aug 10 '12 at 13:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.