Re: [math-fun] Database of math problems
"Keith F. Lynch" <kfl@KeithLynch.net> wrote:
Meta-problem: Find a problem that doesn't generate anything searchable. Not sequences, not large integers, not unusual real numbers, not even unusual keywords. Bonus points if it's not obvious what, if any, existing branch of math it belongs to.
I think I found one. Ironically, it's the very example I used of what ought to be *easy* to look up!
How large a subset of the N^2 points on an N-by-N square grid can there be with none of the distances between the points in the subset being equal?
Thanks to Sloane, there's also a way to look it up: I could "solve" it, by brute force, for the first few N, then look up the resulting sequence in OEIS. If anyone has a general solution, that will point me at it.
I went ahead and tried exactly that, with a simple but slow and inefficient program. The solutions for N=0 through 6 are all equal to N. I'm not going to bother to look up 0,1,2,3,4,5,6 in OEIS. Any suggestions on how to solve this problem? Or rather, on how to search for some previous solution? (This is not a Costas array, lest anyone suggest it is.) I did prove that the solution for N can never exceed N. The number of possible distinct distances in an N by N grid is at best only slightly more than N-choose-2, the number of pairwise distances between N points. For N=15, it's equal, and for N>15 it's less, meaning that for N>15 the solution can be at most N-1. Similarly, for N>23 the solution can be at most N-2. (Both numbers look like they grow quadratically, but the number of possible distances actually grows more slowly due to collisions from pythagorean triples and other coincidences (e.g. 1^2 + 7^2 equals 5^2 + 5^2).) And of course the solution for N+1 can never be less than the solution for N, since you can simply reuse the previous solution, leaving the new row and new column empty. Other than that, I've gotten nowhere. Here's a sample solution for N=6. Observe that the 15 pairwise distances between the 6 points are all different. There are just 19 different distances possible in a grid this size, so just 4 aren't used in this solution. A 7th point would result in 21 pairwise distances, so no 7th point is possible. * - - - - - - - - - * * - - - * - - * - - - - - - - - - - - * - - - - -
I don't have the answer to your question, but I have some suggestions. Entries A193555 and A193839 in the OEIS are almost what you want ------------------------------ Searching in the OEIS for "distances" and "distinct" led to these lines (internal OEIS format, but you can see the A-numbers): %C A047800 a(n-1) is the number of distinct distances on an n X n pegboard. What is its asymptotic growth? Can it be efficiently computed for large n? - _Charles R Greathouse IV_, Jun 13 2013 %C A131628 A set of points in the plane is called an n-distance set if there are precisely n different distances between pairs of distinct points. %C A160663 a(n-1) is the number of distinct positive distances on an n X n pegboard. What is its asymptotic growth? Can it be efficiently computed for large n? - _Charles R Greathouse IV_, Jun 13 2013 %N A186704 The minimum number of distinct distances determined by n points in the Euclidean plane. %e A186704 a(4) = a(5) = 2 from the 2 distinct distances between vertices of a square and a regular pentagon. %H A193555 Hanno Lefmann and Torsten Thiele, <a href=" http://www.inf.fu-berlin.de/~thiele/texte/LF_TechR.ps.gz">Point sets with distinct distances.</a> (1995) %N A193556 Denominators of the squared radii of the smallest enclosing circles of n points with integer coordinates and distinct mutual distances, arranged such that the radius of their enclosing circle is minimized. Numerators are given in A193555. %N A193838 Size k of smallest square of k X k lattice points from which n points with distinct mutual distances can be chosen. %H A193838 P. Erdős and R. K. Guy, <a href=" http://dx.doi.org/10.5169/seals-27359">Distinct distances between lattice points</a>, Elemente der Mathematik 25 (1970), 121-123. %e A193838 a(3)=3: The points ((1,2),(3,1),(3,2)) have distinct mutual squared distances 1, 4, 5. %N A193839 Smallest possible value of the maximum of squared distances between any two out of n points with integer coordinates and distinct mutual distances. %N A193840 Minimum required size j*k of a rectangle of lattice points such that it is possible to choose n points out of the j*k rectangle points with distinct mutual distances. A193841 gives max(j,k). %N A047808 a(n) counts different values of i^2 + j^2 <= n^2 or number of distances from the origin to all integer points inside a circle of radius n. ------------------- Chapter F "Finite Sets" in the book H. T. Croft, K. J. Falconer and R. K. Guy, Unsolved Problems in Geometry, is worth looking at - section F1 is about distinct differences. It also contains references to several related surveys. Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Mon, Apr 4, 2016 at 8:41 PM, Keith F. Lynch <kfl@keithlynch.net> wrote:
"Keith F. Lynch" <kfl@KeithLynch.net> wrote:
Meta-problem: Find a problem that doesn't generate anything searchable. Not sequences, not large integers, not unusual real numbers, not even unusual keywords. Bonus points if it's not obvious what, if any, existing branch of math it belongs to.
I think I found one. Ironically, it's the very example I used of what ought to be *easy* to look up!
How large a subset of the N^2 points on an N-by-N square grid can there be with none of the distances between the points in the subset being equal?
Thanks to Sloane, there's also a way to look it up: I could "solve" it, by brute force, for the first few N, then look up the resulting sequence in OEIS. If anyone has a general solution, that will point me at it.
I went ahead and tried exactly that, with a simple but slow and inefficient program. The solutions for N=0 through 6 are all equal to N. I'm not going to bother to look up 0,1,2,3,4,5,6 in OEIS. Any suggestions on how to solve this problem? Or rather, on how to search for some previous solution? (This is not a Costas array, lest anyone suggest it is.)
I did prove that the solution for N can never exceed N. The number of possible distinct distances in an N by N grid is at best only slightly more than N-choose-2, the number of pairwise distances between N points. For N=15, it's equal, and for N>15 it's less, meaning that for N>15 the solution can be at most N-1. Similarly, for N>23 the solution can be at most N-2. (Both numbers look like they grow quadratically, but the number of possible distances actually grows more slowly due to collisions from pythagorean triples and other coincidences (e.g. 1^2 + 7^2 equals 5^2 + 5^2).)
And of course the solution for N+1 can never be less than the solution for N, since you can simply reuse the previous solution, leaving the new row and new column empty.
Other than that, I've gotten nowhere.
Here's a sample solution for N=6. Observe that the 15 pairwise distances between the 6 points are all different. There are just 19 different distances possible in a grid this size, so just 4 aren't used in this solution. A 7th point would result in 21 pairwise distances, so no 7th point is possible.
* - - - - - - - - - * * - - - * - - * - - - - - - - - - - - * - - - - -
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Keith F. Lynch -
Neil Sloane