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.

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

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.

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)?

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$.

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?

You can also prove that it's true for 100 distinct distances

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?