# Maximum number of points you can put on grid $n\times m$ with no equidistant?

Assume we have a grid of $n\times m$ points. and the distance between two rows or two columns is 1 ( unit ). I have a couple of questions related to this grid:-

1. What is the list of possible length between points?
2. What is the maximum number of points that they have no equidistant between any pairs?

• For question number one , I know if we have we have $n \times m$ so we have length of size $1,2 \dots \mbox{max}\{m,n\}$ in addiction of this we have $\sqrt{2},\sqrt{5}$ and some others. but I am interested in all of these distance.
• For question number 2 intuitionally it look like for $n\times n$ case we the maximum point with no equidistant is n.

I have feeling this has been studied in some books but I am not sure where or how to answer the general case of this problem. any hints and/or answers would be appreciated.

There are solution of $5 \times 4$ for example this is two of the solution of it ( there is 5 non-equidistant points):-

Reference:- I found this problem from the twitter and you can find it here.

• +1 for just being the most interesting question I've read today. Mar 26 '15 at 21:40
• It's not hard to describe the set of possible lengths: $\{\sqrt{i^2 + j^2}: i =0, 1, \ldots, n,\text{ and } j = 0, \ldots, m\}$, but its size in terms of $m$ and $n$ isn't obvious. Primarily due to the existence of Pythagorean triples; for example $5 = \sqrt{3^2 + 4^2}$. (We could get rid of a lot of repeats here by requiring $j > i$, but since it isn't good for counting as it is, I won't bother). It's not hard to bound the number of unique lengths above by $m(m+1)/2 + m(n - m)$, but that's all I've got. Mar 26 '15 at 22:21
• Perhaps I'm miscounting, but in a 5×5 grid I can't seem to find 5 points such that no two pairs of them are equidistant -- contrary to your intuition about Question 2 in case m=n. (?) Apr 1 '15 at 15:22
• @r.e.s. actually there is solution for $5 \times 4$ ( I know 2 of them but I hear there are 7) .. so of course there is solution for $5\times 5$.and about the Taxicab geometry I agree with you , this is the only related thing I founded which the relation to this problem but it is not so obvious to me. thanks Apr 1 '15 at 15:25
• OK, I must have overlooked something -- would you mind posting any one of those $5\times 4$ solutions? (Sorry, before I saw your reply I edited out my comment about Taxicab geometry as a variant.) Apr 1 '15 at 15:32

The squared lengths are of the form $i^2 + j^2$ for $i \in [0,n]$ and $j \in [0,m]$; assuming (with no loss of generality) that $n \ge m$, we can consider only the cases where $i \ge j$, of which there are $$(m+1)(n-m)+\frac{1}{2}(m+1)(m+2)=\frac{1}{2}(m+1)\left(m+2(n-m+1)\right).$$ On the other hand, placing $k$ points creates $k(k+1)/2$ pairs, so if all of these pairs must have distinct distances, $$k(k+1) \le (m+1)\left(m + 2(n-m+1)\right).$$ So for $n=m$ this implies $k \le m+1$, and more generally $$k \le \sqrt{(m+1)\left(m + 2(n-m+1)\right)}.$$
A tighter bound, at least in the limit of large $n$, will come from improving the estimate of the number of distinct distances on the grid. We know that the number of positive integers less than $2n^2+1$ that are the sum of two squares is $O\left(n^2 / \sqrt{\log n}\right)$ (cf. the Landau-Ramanujan constant); i.e., it grows more slowly than $n^2$. For $n=m$, then, the growth rate of $k$ is necessarily in $O\left(n / \sqrt[4]{\log n}\right)$. So $k=n$ is not correct: in fact, $k/n \rightarrow 0$ for large $n$.
• The paper "A note on distinct distance subsets" (Charalambides 2013) gives this same upper bound, and also gives the asymptotic lower bound $k \in \Omega\left(n^{2/3} / \sqrt[3]{\log n}\right)$. Apr 1 '15 at 17:43
• Your closing sentence naturally leads to the question: What is the least $n$ such that in an $n\times n$ grid, there is no set of $n$ points among which all point-to-point distances are distinct? Apr 1 '15 at 17:58
• @r.e.s.: Yes, it does :). Maybe you should ask that question separately... it may not be very large, but then again, $(\log n)^{1/4}$ grows pretty slowly. Apr 1 '15 at 19:29
• @mjqxxxx that was little surprised to me to see $k=n$ is not correct. thanks for your answer. Just wonder do you think there is a mechanism to know the location of these points ? thanks Apr 2 '15 at 1:23