This problem comes from a math test which I've already completed. I'll give the problem and my attempt at a solution.
Part A: Given a $3\times3\times3$ cube $C$ containing $28$ points. Prove that some pair of points is within $\sqrt{3}$ of each other.
Part B: Describe a distribution of $27$ points in $C$ such that every point is more than $\sqrt{3}$ from each other point.
Part A was simple: Begin by partitioning $C$ into $27\;1\times1\times1$ cubes. Picture a Rubik's cube:
Then, by the pigeonhole principle, one small cube must contain $2$ points. The distance between these two points is at most $\sqrt{3}$ (since the largest Euclidean distance in the small cube is between opposite vertices, which is $\sqrt{1^2+1^2+1^2} = \sqrt{3}$). Therefore, some pair of points is within $\sqrt{3}$ of each other.
Part B was less simple. On the test, I claimed that $14$ is the greatest number of points which can be packed into $C$ while satisfying the condition:
Put one point on each of the vertices of $C$ for a total of $8$ points.
If you draw a $3\times3$ square with circles of radius $\sqrt{3}$ coming off each vertex, you will see that there is only a small area not within any circle. This region includes the center of the square. This picture represents a view of any face of $C$ so far.
Then, put one point on the center of each face of $C$ for $6$ more points. These points are legal.
Based on our previous diagram, each face of $C$ cannot hold any more points. But can the very center? No. The distance from the center of $C$ to the center of any of its faces is $1.5$.
We have now placed $14$ points. I believe we placed them with an optimal strategy, so I think that $15$ (and everything greater) is impossible.
My attempt at Part B does not rigorously prove that $14$ is the maximum, so my questions are:
- Is this task possible with $27$ points?
- If so, how?
- If not, what is the maximum, and how can you prove it?
Best Answer
I don't have a proof, but here's a reasonable answer.
Your task is equivalent to packing spheres of radius $\frac{\sqrt3}{2}\approx0.866$ in a cube of side length $3+\sqrt3\approx4.732$. Scaling down, this is equivalent to packing spheres of radius $\frac{\sqrt3}{6+2\sqrt3}\approx0.18301$ in a cube of side length $1$. So we consult a handy list of best known sphere packings for an $N$ with radius greater than $0.18301$:
http://hydra.nat.uni-magdeburg.de/packing/scu/scu.html
It looks like we can just barely do it with $19$ spheres! Let's see what that looks like:
http://hydra.nat.uni-magdeburg.de/packing/scu/scu19.html
The coordinates are available at http://hydra.nat.uni-magdeburg.de/packing/scu/txt/scu19.txt