wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Distances with multiplicities
        
(Message started by: Michael Dagg on Sep 27^th, 2009, 10:00am)

Title: Distances with multiplicities
Post by Michael Dagg on Sep 27^th, 2009, 10:00am

Can anyone find n points in the plane (no three on a line,
no four on a circle) so that for every k, k=1,2,..., n-1,
there is a distance determined by these points that occurs
exactly k times?

Title: Re: Distances with multiplicities
Post by R on Sep 27^th, 2009, 3:04pm

Do you mean for n=5, we have to find 5 such points that there should be
The distance 1 between exactly 1 pair of points,
The distance 2 between exactly 2 pairs of points,
The distance 3 between exactly 3 pairs of points,
The distance 4 between exactly 4 pairs of points, and
The distance 5 between exactly 5 pairs of points??

Title: Re: Distances with multiplicities
Post by Obob on Sep 27^th, 2009, 4:07pm

on 09/27/09 at 15:04:24, R wrote:

Do you mean for n=5, we have to find 5 such points that there should be
The distance x between exactly 1 pair of points,
The distance y between exactly 2 pairs of points,
The distance z between exactly 3 pairs of points,
The distance w between exactly 4 pairs of points,

Fixed. I.e. the distances can be anything, and you only go up to n-1 pairs of points (note that in case n=5, there are only 10 pairs of points total).

Title: Re: Distances with multiplicities
Post by Grimbal on Sep 28^th, 2009, 12:47am

One obvious solution would have been n points at equal distance on a straight line, or on a circle, but that is explicitly forbidden.

Still searching.

Title: Re: Distances with multiplicities
Post by R on Sep 28^th, 2009, 3:39am

Still having doubt in the question.
Can we find a general solution for this problem? Does some structure exist for every possible value of n?

If yes, then with a given structure for some n, if we remove one set of all edges of same length and the corresponding point, then we will get the structure for n-1 points and the reverse will also work.
Following the above argument, for n = 3, an Isosceles triangle fits in the definition. I don't see where do I put the fourth point to have k=3 sides of same length. Only possibility is using the 3rd Dimension. put the fourth point on the 4th vertice of a tetrahedron. What is the dimension of the points to be found out.

Title: Re: Distances with multiplicities
Post by towr on Sep 28^th, 2009, 4:38am

on 09/28/09 at 03:39:03, R wrote:

If yes, then with a given structure for some n, if we remove one set of all edges of same length and the corresponding point, then we will get the structure for n-1 points and the reverse will also work.

That sounds about right to me.

Quote:

Following the above argument, for n = 3, an Isosceles triangle fits in the definition. I don't see where do I put the fourth point to have k=3 sides of same length.

Two issues here; you're working in the other direction, so you need to establish that an isosceles triangle is the only possible solution for n=3; but that is fairly simple.
And two, the new point doesn't necessarily need to have 3 times a distance of the same length to the other points; e.g. the distance that occurred twice could occur once more with the new point, with twice another new distance.
However, if you put the fourth point in the middle of the circle on which the earlier three points lie, then it does in fact create the same new distance three times.
But there are now multiple possible configurations to extend with a fifth point, in multiple possible ways.

Title: Re: Distances with multiplicities
Post by R on Sep 28^th, 2009, 4:57am

on 09/28/09 at 04:38:48, towr wrote:

so you need to establish that an isosceles triangle is the only possible solution for n=3; but that is fairly simple.

Whatever you make with 3 points following the condition, I'll call it an isosceles triangle.

Quote:

And two, the new point doesn't necessarily need to have 3 times a distance of the same length to the other points; e.g. the distance that occurred twice could occur once more with the new point, with twice another new distance.

How will the order matter, Either You add distance occurring twice first or you add distance occurring thrice first.

Quote:

However, if you put the fourth point in the middle of the circle on which the earlier three points lie, then it does in fact create the same new distance three times.

Okay.

Quote:

But there are now multiple possible configurations to extend with a fifth point, in multiple possible ways.

Like one is???

Title: Re: Distances with multiplicities
Post by towr on Sep 28^th, 2009, 5:36am

on 09/28/09 at 04:57:50, R wrote:

Whatever you make with 3 points following the condition, I'll call it an isosceles triangle.

You can call it whatever you like, but if you only say it's "a" solution, then all your following steps are invalid. Because they only apply if it's the only solution. And that becomes particularly important in later steps, because there there actually are different solutions.

Quote:

How will the order matter, Either You add distance occurring twice first or you add distance occurring thrice first.

I don't know what you're trying to say here

Quote:

Like one is

Just because I only gave a counter-example to your claim there isn't a solution which adds 3 times teh same distance, doesn't mean there aren't other ones. For example, you can also extend you isosceles triangle in such a way that you add a new k=1 distance, and add twice the previous k=1 value (which thus becomes the k=3 distance).

If you look at the attached picture, you'll see there are (at least) two ways to extend an isosceles triangle with another point, such that one distance occurs once, one twice, and one three times.
They may or may not both be extendable to 5 points. But it has to fail for all possible configurations before you can see it's impossible to get a valid configuration for 5 points.

Title: Re: Distances with multiplicities
Post by R on Sep 28^th, 2009, 6:13am

on 09/28/09 at 05:36:34, towr wrote:

You can call it whatever you like, but if you only say it's "a" solution, then all your following steps are invalid. because they only apply if it's the only solution. And that becomes particularly important in later steps, because there there actually are different solutions.

I don't know what you're trying to say here

Just because I only gave a counter-example to your claim there isn't a solution which adds 3 times teh same distance, doesn't mean there aren't other ones. For example, example, you can also extend you isoceles triangle in such a way that you add a new k=1 distance, and add twice the previous k=1 value (which thus becomes the k=3 distance).

I misunderstood your previous post, but got it later after replying. It's clear to me now what you are saying. :) Excuse me for the trouble.

Title: Re: Distances with multiplicities
Post by R on Sep 28^th, 2009, 6:18am

One thing you haven't replied to is, what should be the dimension of these n points?
Do we have to find these points in a 2D plane or 3D space?

Title: Re: Distances with multiplicities
Post by Grimbal on Sep 28^th, 2009, 6:38am

Michael said "n points in the plane", which means 2D.

I think if you are dealing in n dimensions, it is easy.

Title: Re: Distances with multiplicities
Post by towr on Sep 28^th, 2009, 6:44am

on 09/28/09 at 06:18:31, R wrote:

One thing you haven't replied to is, what should be the dimension of these n points?
Do we have to find these points in a 2D place or 3D space?

Well, the question says "plane", so 2D.

I've found 5 configurations for 4 points so far, see attachment.
[e]Hmm, I just noticed I at least missed a sixth, as variant of the fourth; but there's probably even more.[/e]

Title: Re: Distances with multiplicities
Post by R on Sep 28^th, 2009, 7:18am

on 09/27/09 at 10:00:55, Michael Dagg wrote:

Can anyone find n points in the plane (no three on a line,
no four on a circle) so that for every k, k=1,2,..., n-1,
there is a distance determined by these points that occurs
exactly k times?

What do we say in the reply? Just Yes?

Title: Re: Distances with multiplicities
Post by towr on Sep 28^th, 2009, 7:36am

on 09/28/09 at 07:18:17, R wrote:

What do we say in the reply? Just Yes?

I think a proof might be nice. But bare in mind the question is implicitly "can you do it for every n" not "does there exist such an n".
If I had to guess, I'd say the answer is probably no in general.

Title: Re: Distances with multiplicities
Post by R on Sep 28^th, 2009, 11:29am

on 09/28/09 at 07:36:19, towr wrote:

I think a proof might be nice.

I was thinking induction might help. But couldn't proceed after a few arguments.
For n = 2 and 3 we can easily prove, so the base case is proved.
Assuming the condition to be true for n points, i.e. there are distances
x₁ exactly 1 times
x₂ exactly 2 times
x₃ exactly 3 times
...
x_n-1 exactly n-1 times

If we add a new point to this structure, it will add n-distances to the set. What can we possibly say about those distances?
If we can prove that the new point adds atleast 2 new distances x_a and x_b then we have disproved the assertion. But if it adds some certain combination of distances from the existing set (like n-1 times some new distance x_a and one distance = x_n-1), then only the condition can be proved to be true for the case of n+1 points.