In one galaxy, there exist more than one million stars. Let $M$ be the set of the distances between any $2$ of them. Prove that, in every moment, $M$ has at least $79$ members. (Suppose each star as a point.)
Problem
Source:
Tags: geometry, 3D geometry, sphere, combinatorics proposed, combinatorics
22.09.2010 12:39
Let $M=\{a_1,\ldots,a_k\}$. If all the stars are collinear, obviously $k\ge 1000000>79$, hence assume not all of them are collinear. Consider three non-collinear stars $s_1,s_2,s_3$. For $i=1,2,3$, construct $k$ spheres centered at $s_i$ with radii $a_1,\ldots,a_k$, denote them by $bi_1,\ldots,bi_k$. Each of the other stars lies on $b1_m,b2_p,b3_q$ for some $1\le m,p,q\le k$. It is easy to see that any three spheres $b1_m,b2_p,b3_q$ have at most two common points because the centers are not collinear. Therefore the number of stars is at most $2\cdot k\cdot k\cdot k+3$, which gives $2k^3+3>1000000$ and $k\ge79$, as desired.
09.01.2013 10:11
jgnr wrote: Let $M=\{a_1,\ldots,a_k\}$. If all the stars are collinear, obviously $k\ge 1000000>79$, hence assume not all of them are collinear. Consider three non-collinear stars $s_1,s_2,s_3$. For $i=1,2,3$, construct $k$ spheres centered at $s_i$ with radii $a_1,\ldots,a_k$, denote them by $bi_1,\ldots,bi_k$. Each of the other stars lies on $b1_m,b2_p,b3_q$ for some $1\le m,p,q\le k$. It is easy to see that any three spheres $b1_m,b2_p,b3_q$ have at most two common points because the centers are not collinear. Therefore the number of stars is at most $2\cdot k\cdot k\cdot k+3$, which gives $2k^3+3>1000000$ and $k\ge79$, as desired. I don't understand! You can give to example by figure
12.02.2014 07:10
I will explain the idea of the problem: for any 3 points $X,Y,Z$ in the space and distance $d$ there exist at most two points $P$ such that $PX=PY=PZ=d$. Now by double counting method it is easy to get $2k^3+3>1000000$. Edit XYZ is in the space not in plane.
12.02.2014 07:55
hal9v4ik wrote: there exist at most two points $P$ such that $PX=PY=PZ=d$. The first such point is the circumcentre of triangle $ XYZ $. What is the second point(if there is any)?
12.02.2014 10:20
In that case, there is only one, namely the circumcentre. But consider larger values for $d$. The locus of the points in space, equally distanced from $X,Y,Z$, is the perpendicular line on the plane determined by $X,Y,Z$, at the circumcentre of $\triangle XYZ$. Now, taking a fixed value for that common distance, how many points there are? Two only, one on each side of the plane determined by $X,Y,Z$.
01.03.2014 20:20
hal9v4ik wrote: Now by double counting method it is easy to get $2k^3+3>1000000$. Edit XYZ is in the space not in plane. I don't understand where does this $k^3$ come from and how is the double-counting done... Can someone explain a little bit, please?
06.09.2019 09:51
You can also prove that it's true for 100 distinct distances
09.02.2024 22:06
Mparsa2002MI6 wrote: You can also prove that it's true for 100 distinct distances Hello, Would you please explain how it is done? with a similar method as above we can show \[\mid{M}\mid\geq80\]. But how is it for 100?