# The Universe and Spaceships

It is given that there are infinite planets in the universe and every planet has exactly one spaceship on it. (Thus there are infinite spaceships too.) The distance between planets is unknown.

As commander of the universe, you are bored, and you decide to command all spaceships to move to the next-nearest planet.

What is the the maximum possible number of spaceships on a planet after all ships have moved to the next-nearest planet?

Conditions:

• You may assume the planets are points for simplicity.
• You are in 3D space.
• There are infinite planets and spaceships.
• Are we assuming 2D space? 3D? – Dennis Meng Dec 2 '16 at 8:03
• @DennisMeng Universe is 2D? :) – Oray Dec 2 '16 at 8:04
• do planets have a non-zero volume, or should we assume they are points? – elias Dec 2 '16 at 8:11
• @elias it would not matter but you may assume they are points. – Oray Dec 2 '16 at 8:20
• I think it does matter. Imagine a large planet surrounded by small ones. The larger the inner one, the more small ones can have it as their nearest neighbour. – elias Dec 2 '16 at 8:30

I believe the answer is exactly

$12$.

If there are a set of planets that by happenstance are arranged as

a regular icosahedron - that is, 12 planets located at the vertices of this polyhedron - and a 13th planet at the center, with no other planets in the nearby vicinity,

Then it follows that

if the length between edges - that is, the distance between any two planets - is $\mathbf{a}$, then the distance from any of those planets (vertices) to the center (of their circumscribing sphere) is $\mathbf{a \sin \frac{2\pi}{5}}$ or roughly $\mathbf{0.951 \times a}$ — so the center planet is closer than any of the others in the isocahedron.

This means that

All twelve planets surrounding the center planet will send their ships to the center, leaving it with 12.

Why this is probably maximal:

You want an arrangement of planets such that there is a central point equidistant from a number of vertices which, in turn, are (separately) equidistant from each other. You want such an arrangement as it provides a single upper bound on the distance the vertices can be from their central point: namely, the uniform distance between any two adjacent vertices. You want this distance to be uniform so no adjacent vertices in the arrangement can be closer (nor farther apart) than this distance, so you only need compare the vertex-to-vertex distance to the distance from any vertex to the center of the arrangement, and find the largest such arrangement where the latter is smaller than the former.

3D shapes with equidistant vertices are regular polyhedra, and if we want those vertices to be colocated on a single sphere so that they are all the same distance from the center of the arrangement then we want a regular convex polyhedron, or a Platonic solid. We want a Platonic solid where the vertex-to-vertex distance (the edge length) is larger than the distance from any vertex to the center of the arrangement (the radius of the circumscribing sphere).

Of the 5 regular Platonic solids, the icosahedron has the largest number of vertices (at 20), but its circumscribed radius is larger than its edge distance. The dodecahedron however has both the second-largest number of vertices (at 12) as well as the desired latter property.
I do not believe a higher number of planets can be found where all are farther from each other than from a single other planet, as only a Platonic solid will maximize the minimum distance between any two vertices while keeping all vertices equidistant from their mutual center.

• "3D shapes with equidistant vertices are regular polyhedra". Regular is far stricter than that, and not really what you are looking for anyway. I does not matter what the distance between the points on the sphere are, as long as their minimum distance is at least the sphere radius. What this is really about is packing points (or circles) on the surface of a sphere. Lots of research has been done on this (for example by Neil Sloane of OEIS fame). The answer is still 12, and the arrangement is an icosahedron (though you have leeway to disturb the points slightly) – Jaap Scherphuis Dec 2 '16 at 12:31
• @JaapScherphuis: In fact, as shown by the existence of the FCC and HCP lattices, there's enough room to twist the points from an icosahedron (almost) into a cuboctahedron or a triangular orthobicupola. – Ilmari Karonen Dec 2 '16 at 17:08

In a 3D-space you can have

at least 12 spaceships on a planet.

See:

In the image above you have 12 unit spheres all touching the central unit sphere, so the distance between all spheres is at least 1. Now if you reduce the radius of these spheres then they can model a configuration of 13 planets. You also need the "luck" that all outer spaceships choose their nearest neigbour to be the central one, as the outer spheres could touch each other too.

See Kissing number.

It might need some thoughts why this is actually an upper bound too.

• This result can be arrived at without resorting to "luck"; see my answer. – Rubio Dec 2 '16 at 8:40
• If you look at your own picture, you will see that the outer spheres are not touching. – Stig Hemmer Dec 2 '16 at 11:23
• @StigHemmer - touching is not needed for optimality. "Locally optimal" only requires that not enough room remains to insert another sphere. Though to be truly optimal, one must also assure that no other locally optimal arrangement beats it. – Paul Sinclair Dec 2 '16 at 17:40

Actually

Since the size of the planets are not mentioned. The amount is infinite.
Imagine planet X with a circumference of 1000.... meters surrounded by planets of a size of 0.0000....1 millimeters.

• "You may assume the planets are points for the simplicity" – oleslaw Dec 2 '16 at 9:30
• One very big planet surrounded by many very small planets. – Jamal Senjaya Dec 2 '16 at 9:50
• @JamalSenjaya Did I miss something or generally "point" has no size. So if the planet is a point it can't be very big. – oleslaw Dec 2 '16 at 9:58
• In this situation the small planets are one another's nearest neighbours. – Gareth McCaughan Dec 2 '16 at 10:03
• Ah. I was taking distances to be measured centre-to-centre rather than surface-to-surface. I am pretty sure that's what the question intends. – Gareth McCaughan Dec 2 '16 at 13:43

I believe that the answer is actually 3.

Planets have to form orbits around their sun. They have to be on the same plane. You can't have them all equally distant around a center point in some form of polyhedron. Not only that, even if you could, one planet would have to be on one side of the sun --not in the center -- therefore much closer to some planets than others.

You can get 3 planets nearly equidistant with a fourth far flung planet. That way, two ships will go to the center planet, the center planet will go to one of the other two, and the far flung one will also go to the center (green below).

If you add any other planets, they are going to be closer to the edges than the center and you'll wind up with 2 ships on the same planet instead of three.

12 is definitely wrong.

• Well, while it might be correct what you claim here, please remember that this is a site for recreational puzzles, and not at all for hard science. In OP the spaceship flavor is to make the puzzle appealing, so that it does not look like some dry mathematical question. It is not too realistic to expect an infinite number of spaceships to fly around, right? So this is a... fictional puzzle. Also, it would be nice if you would back up your claims with references, e.g. "Stable planetary systems have to be planar", etc. – Matsmath Dec 2 '16 at 18:43
• "They have to be on the same plane" - that's not even the case for our solar system, let alone some crazy puzzleverse with a commander commanding infinitely many spaceships. – user2357112 supports Monica Dec 2 '16 at 18:54
• @Matsmath Normally, yes. Fictional. But the OP commented that it operates like a real universe. – Shane Dec 2 '16 at 19:04
• @Matsmath And besides, what fun is a puzzle that takes the obvious answer? – Shane Dec 2 '16 at 19:11
• You assume that the planets are contained within a single solar system. I can have 13 solar systems each with one planet, such that at the time the command to move is ordered, the regular icosahedron is perfectly formed by the planets. – greenturtle3141 Dec 2 '16 at 19:38