Let there be a cube with edge length of 9 units. Inside this cube there are 1981 points.
1. Prove that among these points there are at least 2 with the distance between them of less than 1 unit.
2. What's the biggest number of points that do not have the property stated at (1)?
2.1. How many points for the distance of 2 - 8 units?
Part 1:
If each point were at least a unit distance away from its nearest neighbor, then spheres of radius 1/2 could be made centered on each point without those spheres overlapping. The volume of a sphere of radius 1/2 is 4*pi*(1/2)^3 / 3 = pi/6. Multiplied by the 1981 points you've got, and the total volume is almost 1037, which is more than the cube's volume, which is 729. So even if spheres could completely fill space, there still would not be space enough in this cube.
Part 2:
It is almost certain that the densest packing of spheres fills pi/sqrt(18) of space, so we can start off with an approximation that in a volume of 729, there would be room for a volume of 729*pi/sqrt(18) to be taken up by the volumes of the spheres, and since each sphere has a volume of pi/6, you'd get 729*6/sqrt(18) ~= 1031 spheres.
However, since we're really only considering the points, parts of the spheres can extend outside the box so long as the central point does not. As the radii are 1/2 a better approximation would involve a cube of size 10x10x10 with volume 1000. 1000*6/sqrt(18) ~= 1414, so that is a better estimate of how many points will fit into the 9x9x9 cube. Conditions near the surface would affect the exact number, as there has to be a perfect structure to reach the optimum packing.
Part 2.1:
The above approximation, if d is taken as the distance instead of 1, is based upon (9+d)^3*pi/sqrt(18) / ((pi/6)*d^3)
DEFDBL A-Z
CLS
pi = ATN(1) * 4
FOR d = 2 TO 8
n = (9 + d) ^ 3 * pi / SQR(18) / ((pi / 6) * d ^ 3)
PRINT d, INT(n + .5)
NEXT
finds these approximations:
2 235
3 91
4 49
5 31
6 22
7 17
8 14
As the distances get larger in relation to the size of the cube, surface restrictions interfere all the more and so 14 can understandably be a poor approximation for a distance of 8.
|
|
Posted by Charlie
on 2010-01-27 14:21:01 |
solution for part 1; approximation for part 2
