"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. * - - - - - - - - - * * - - - * - - * - - - - - - - - - - - * - - - - -