7
$\begingroup$

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:

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?
$\endgroup$
4
  • 1
    $\begingroup$ Before anyone else wastes their time on the same argument as I tried: The Kepler conjecture only tells us that $29$ points can not be placed in the cube. Very unfortunately barely not good enough. $\endgroup$
    – SmileyCraft
    Commented Dec 18, 2018 at 23:31
  • $\begingroup$ You can get at place 15 points. Move each point on the center of each face about $0.634$ to the right, so it is still further than $\sqrt{3}$ from each edge, but now its distance from the center is greater than $\sqrt{3}$, so you can add a point to the center. $\endgroup$
    – user477805
    Commented Dec 18, 2018 at 23:51
  • $\begingroup$ An idea which will give some bound is to enlarge the cube by adding a cubical shell of thickness $3^{1/2}/2$, then note that the $3^{1/2}/2$ radius balls around each point will be disjoint, and contained in the cube. This isn't good enough for 27, but taking into account the inefficiency of filling the outer shell might be good enough. $\endgroup$
    – Chris H
    Commented Dec 19, 2018 at 0:02
  • $\begingroup$ @user477805 I'm having trouble with your construction. I have graphed a square with vertices at $(0, 0), (3, 0), (3, 3), (0, 3)$ and drawn four circles of radius $\sqrt{3}$ with centers at each vertex. The point you describe (at $(1.5 + 0.634, 1.5)$) is just barely inside two of the circles. $\endgroup$
    – jarhill0
    Commented Dec 19, 2018 at 1:01

1 Answer 1

Reset to default
7
$\begingroup$

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

18 0.18768...
19 0.18318...
20 0.17840...

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

enter image description here

The coordinates are available at http://hydra.nat.uni-magdeburg.de/packing/scu/txt/scu19.txt

$\endgroup$
2
  • $\begingroup$ Very nice! I was looking for a source like this. By myself, I found a sphere packing with $18$ spheres, which was looking very optimal, so I am a little shocked that $19$ is possible :) I was pretty close apparently. $\endgroup$
    – SmileyCraft
    Commented Dec 19, 2018 at 0:16
  • $\begingroup$ Brilliant! I considered phrasing the question in this way (since I realized it was equivalent), but I figured I would keep the original phrasing. If I had pursued the problem more from a sphere packing perspective, I might have looked into best known sphere packings. $\endgroup$
    – jarhill0
    Commented Dec 19, 2018 at 0:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .