5
$\begingroup$

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):-enter image description here

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

$\endgroup$
6
  • 1
    $\begingroup$ +1 for just being the most interesting question I've read today. $\endgroup$
    – Zach466920
    Mar 26 '15 at 21:40
  • 1
    $\begingroup$ 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. $\endgroup$
    – pjs36
    Mar 26 '15 at 22:21
  • 1
    $\begingroup$ 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. (?) $\endgroup$
    – r.e.s.
    Apr 1 '15 at 15:22
  • $\begingroup$ @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 $\endgroup$
    – henry
    Apr 1 '15 at 15:25
  • $\begingroup$ 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.) $\endgroup$
    – r.e.s.
    Apr 1 '15 at 15:32
3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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)$. $\endgroup$
    – mjqxxxx
    Apr 1 '15 at 17:43
  • $\begingroup$ 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? $\endgroup$
    – r.e.s.
    Apr 1 '15 at 17:58
  • $\begingroup$ @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. $\endgroup$
    – mjqxxxx
    Apr 1 '15 at 19:29
  • $\begingroup$ @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 $\endgroup$
    – henry
    Apr 2 '15 at 1:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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