Question

we have over a million point in 3D space. prove that there are at least 79 different length among the distances between the points.

Answer 1

It looks like an IIT question to me.

Answer 2

sorry i don't get ya .what do you mean?

Answer 3

I mean its seems to be a tough question to me.

Answer 4

yup . it's so hard to me too

Answer 5

distance id defined as: \(d(x,y)=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2+(x_3-y_3)^2}\)
as we know from elementary arithmetics, \(x-y\) in \(R\) is well defined operation. It means for differents values \(x\) and \(y\) there is a unic value \(z=x-y\). So since there are infinite points in \(R^3\), there will be infinite \((z_1,z_2,z_3)\) so you van find infinite lengths

Answer 6

it said over a million point not infinite points

Answer 7

it doesn't matter

Answer 8

first i thought like you but it someone told me it's wrong

Answer 9

think like this:
Take one point as a reference. Then take sphere with radius 1 centered at it. All the points that lie on the sphere will have distance equal 1. Next take a sphere with radius 2. All the points that lie on the sphere will have distance 2 from reference. And continue till 79.

Answer 10

it's just a mental solution that mathematics don't accept that

Answer 11

mathematics is this

Answer 12

we should use Pigeonhole principle but i'm stuck in the middle of it's proof

Answer 13

check this , it's about Pigeonhole principle:
http://en.wikipedia.org/wiki/Pigeonhole_principle

Answer 14

Take 2 points. There is only one distance between them
Take 3 points. The COULD be only one single distance between ever two out of three (they lie on a equilateral triangle).

4 points: there must be at least two different distances (when the points are in the plane).
In 3D space, there still could be one distance between every two points (they lie on a regular tetrahedron).

5: points in 3D: at least 2 distances.

We could try to reason along in this way, while adding points...

Answer 15

I'd say the Pigeonhole Principle only holds if distances between points are discrete, not continuous.

Answer 16

@ZeHanz it's just giving example . we should prove it

Answer 17

@ZeHanz they are discrete

Answer 18

Then shouldn't we know the size of the 3D space?

Answer 19

@ZeHanz by saying over a million points in space i didn't mean infinite points i meant they have given us some point's that is over a million ( for example we can prove for a million points) and the size of 3D space is not important

Answer 20

So we have a million different points with 3 discrete coordinates \((x_i, y_i, z_i)\) each.
The (square of) the distance of two such points is \((x_i-x_j)^2+(y_i-y_j)^2+(z_i-z_j)^2\).
Because all the points are different, always at least one of the numbers \((x_i-x_j)^2\), \((y_i-y_j)^2\) and \((z_i-z_j)^2\) must be greater than zero.
We now have to prove that there are at least 79 different of these numbers.

Answer 21

i'm using Reductio ad absurdum and Pigeonhole principle to prove that but i don't where am i wrong?!!!

Answer 22

@myko do you have any idea?

Answer 23

thinking...

Answer 24

Maybe consider the worst case: when this points are vertices of some n-gone. So the number of distances will be the number of n-gon diagonals of different lengths +1

Answer 25

@myko i used that but again .it was wrong 'cause there's no worst case .it's not accepted

Answer 26

If you have to give a general proof, it is not a bad idea to consider a worst case. If it holds in that case, it will always hold.

Answer 27

@ZeHanz i know that but the worst case is just what you think about it maybe some one else think differnt

Answer 28

@ZeHanz if you do that to solve a problem they won't give you even 0 point

Answer 29

did you try by finding some injective function from distances to points?

Answer 30

what do you mean?

Answer 31

by this pgeon principle: if f:n->m injective then n<=m

Answer 32

i just used proof by contradiction and pigeonhole principle

Answer 33

for any configuration of 5 points on a sphere, any two of them determine a great circle on the sphere (a circle whose center is the center of the sphere), and that great circle divides the sphere into 2 hemispheres. Considering the remaining 3 points, the pigeonhole principle says that one of the hemispheres must contain at least 2 of those 3 points. Together with the 2 points on the great circle, that hemisphere contains at least 4 points.
It's from here:
http://www.math.hmc.edu/funfacts/ffiles/10001.4.shtml

Answer 34

I think this is the way

Answer 35

i'm using this way but what you said is wrong .'cause we don't know that the point are on a sphere

Answer 36

here's my incompleted solution help me prove it
but wait for me to write it

Answer 37

ok. Got to go now. I will try to do it later. But anyway, the points beying on the sphere is an extreem case. If they not on the same sphere equaly spaced, is better for our porpose, because number of distances will be greater

Answer 38

first we take a point's and label it A .if problem is wrong then we have max 78 different sphere with center A. so if we use pigeonhole principle then atleast one of the sphere contains 12821 points
\[\lceil \frac{1000000}{78} \rceil=12821\]
now we took one those 12821 points and label it B . the rest of 12820 point are on the max 78 different sphere with center B and so by pigeonhole principle one of those sphere contains 165 point of that 12820 points
\[\lceil \frac{12820}{78} \rceil=165\]
and now these 165 point are on the Intersection of the two sphere one with center A and the other with center B that is circle

this is my halfproof right now
and don't know how yo prove that in circle by 165 points on it .atleast how many different length we have.
but i noticed you talked about use the half of the sphere and sth poped up in my mind

the continue of my proof:
after that we can half the circle so we have atleast 83 point in one of the half
\[\lceil \frac{165}{2} \rceil=83\]
that mean we have atleast 83 different length
here we use contradiction proof that mean our proof contradict itself 'cause in the start we thought that the problem is wrong and we have atleast 78 different length but here it says atleast 83
so the problem is right

Answer 39

@myko tnx myko for ur help