Find a configuration of ten (twelve) points on a sphere such that the smallest distance between two of these points is as large as possible.

THE CONTRIBUTIONS OF THE CONTESTANTS IN THE COMPETITION

Let me begin with the smaller contributions, communicated as casual remarks and small notes. I give the remarks with a little asterisk, my comment follows immediately with a little 'plus'.

* Did someone ever find an optimal solution for ten pirates? (director of a school in Limburg).
+ Yes, K.Schütte did in 1950. The proof of optimality has been given in 1963 by Ludwig Danzer.

* We are not smart enough for this problem (a father and his son, both are teacher of mathematics).
+ The problem is so difficult that dr Danzer needed more than sixty pages in that time, to write down the solution in concise form.

* I place ten points on Mark's playball, and then I puzzle and shove around. (Roy Kneefel)
+ Don't give up, Roy.

* I buy a balloon and make a network of little strings and knots. (Ing. Karel Hendriks)
+ I am curious to see the result.

* I draw a spiral on a sphere, from pole to pole. Then I first place the points on the edge of a front view of the sphere, at equal distances from any one to the next. Thereafter I move the points alternatingly forward and backward over the sphere, until they arrive at the spiral. (my wife Marian)
+ You thought well, Marian.

* I think I have to use the sine, cosine and tangent rules. Can you send them to me? It is already clear to me that all points have to be at equal distances from each other. (my brother Jacques)
+ That is correct for twelve pirates, but it cannot be realised with ten.

* I place five pirates at the north pole and five at the south pole. Four of these five walk southward (resp. northward), in four directions with ninety degrees differences at every turn. They walk until there is an equilibrium. (my son Michiel)
+ You thought very well.

* I had not much time for the problem in the holidays. The distances between the points and the angles between the edges have to be equal. The distance between two points is: (t/360) times 2 times pi times radius, where t is the angle between the points, seen from the center of the sphere. (Floris Courtens)
+ The first conclusion is right for twelve pirates, but for ten it cannot be realised. The distance formula is correct.

* Do you have a real proof that your configuration is optimal? We only see a configuration for which we are hoping to prove that it gives a local maximum. (Two mathematicians at the Nijmegen Radboud University)
+ The problem turned out to be more difficult than I first thought. My proof is only correct under the assumption that the configuration has a north pole and a south pole.

* The radius of the sphere is 1 megameter.
Let a be the smallest geodetic distance between two distinct points. If we draw a circle with geodetic radius a/2 around each of the points, then we get 10 (12) circular regions that are disjoint or touching.
Denote with b the area of the part of the sphere that lies inside such a circular region. Then the sum of these areas is at most equal to the area of the sphere. Thus n times b is at most 4 times pi, with n=10 or n=12 respectively.
A simple calculation learns that b = 2.pi.(1-cos(a/2)) .
It follows that cos(a/2) is at least 4/5 for ten pirates, and at least 5/6 for twelve.
We find the necessary condition that a is at most 1.287002218 for ten pirates, and at most 1.171371087 for twelve.
But are these conditions sufficient?
A beautiful problem! (professor dr A.H.M.Levelt, Nijmegen)
+ Thank you for this short but important note, professor!
You calculated b via integration over a circular region of the sphere with the help of spherical coordinates.
The conditions are not sufficient, because the 10 or 12 circles don't cover up the sphere (for 10 they are not even always touching).

Now here follow the contributions of the contestants who really intended to compete for the prizes.

We begin with a fine contribution of mister Martien Luijcks from Haarlem.

Solution for 10 pirates:

I think that the solution for 10 pirates is as follows:
One at the north pole, one at the south pole. Partition the planet into eight vertical slices. Place alternatingly a pirate north and south at the points of intersection of the tropics and the meridians that originate from the partitioning. When you connect these points, going around the earth, there comes a zigzag pattern.

Solution for 12 pirates

I think that the solution for twelve pirates is less elegant:
One at the north pole, one at the south pole. Distribute the pirates alternatingly north and south, but now at the new meridians at one-third and two-thirds of the heigth of the sphere. We get a zigzag pattern again, but with greater amplitude.

Analytic supplement:

I risk a great miscarriage with an analytic supplement. I think that we get equilateral triangles. A tropic lays at 23 degrees from the equator, one-third is at 30 degrees. A tropic seems most appropriate because of its divine exactness.

My comments:

Thank you for this good contribution. Your approach is the same as mine.
The distances between the points are not exactly correct, but you made a good estimate. In fact we must not have 23 and 30 degrees, but roughly 24.5 and 26.5.
For 10 pirates the distances (from any pirate to the nearest other one) cannot be all equal, for 12 they can.

Mister Peter Janssen from Lanaken (Belgium) sent the following contribution.

Solution for 12 pirates

I know that there is a regular polyhedron with twelve vertices, thirty edges and twenty faces (every face is an equilateral triangle).
The vertices are lying on the sphere as follows (the sphere has radius 1 times 1000 km):
1 at the top in (0,0,1), 1 at the bottom in (0,0,-1), 5 in a plane z=c and 5 in a plane z=-c (in both planes, those 5 points form a regular pentagon).
The points in z=c lie on the circle x²+y²=r²=1-c².
I calculate c as follows: the distance through space between (r*cos(72),r*sin(72),c) and (r,0,c) has to be equal to that between (r,0,c) en (0,0,1), so
r²(2-2*cos(72)) = r²+(c-1)² = 2-2*c.
Thus r² = 1-c² = (2-2*c)/(4*sin²(36)).
The distance over the sphere between (0,0,1) and (r,0,c) is the angle s such that cos(s)=c, so it is arccos(c).
With a pocket calculator I find s=1.107148718.
The pentagon in z=-c is rotated over 36 degrees with respect to the one in z=c.

Solution for 10 pirates

For the problem with ten pirates, I replace the 2 times 5 points on z=c and z=-c by 2 times 4 points on z=d and z=-d.
The points in z=d form a square, those in z=-d another square, but the second square is rotated over 45 degrees with respect to the first one.
Now I require that the distance through space between (0,0,1) and (R,0,d) is equal to the distance between (R,0,d) and (R*cos(45),R*sin(45),-d) (the distance between two neighbour points in z=d is greater).
I calculate d as follows: R²+(d-1)² = R²(2-2^(1/2))+4*d², dus
2-2*d = 2-2^(1/2) + d²(2+2^(1/2)).
the smallest distance over the sphere is now arccos(d) = 1.14371774.

My comments:

Your presentation is very clear. The outcomes are the same as mine. For 10 pirates, your configuration is not optimal.

I was glad to receive the following very original contribution of Harrie Schreuders from Sittard. I give his account in a concise form.

Solution for 10 pirates:

I find that I only have to consider the following most promising cases:
1) One point at the bottom of the sphere, then five points in a plane more aloft, then four points in a third plane at a highest level. The planes are not necessarily parallel. The five points form a regular pentagon, the four form a rhomb.
2) One point at the bottom, then three times three points in three horizontal planes. Three points in a horizontal plane form an equilateral triangle, with varying side lengths. The triangles in the first and third planes have the same orientation, the triangle in the second plane is rotated over sixty degrees with respect to the other two.
3) One point at the bottom , then two times four points in two horizontal planes, at last one point at the top. Four points in a horizontal plane form a square. The second square is rotated over 45 degrees with respect to the first one.

To consider these cases, I make Cabri constructions in front views, side views and views from above. I strive for as much symmetry in the configuration as possible and as many equal distances between neighbour points as possible. I vary the lengths of the chords, and the radius of the sphere varies with it. I investigate at which moment the ratio of the minimal chord length and the radius of the sphere is maximal.
In case 1) I get maximal ratio 1.08810. The distance over the sphere then becomes 1150.51 .
In case 2) I get maximal ratio 1.09053. The distance over the sphere then becomes 1153.41 km.
In case 2) I get maximal ratio 1.08239. The distance over the sphere then becomes 1143.72 km.

Solution for 12 pirates:

An icosaeder is a platonic polyhedron with 12 vertices, so that is the best solution. The distance over the sphere then becomes 1107.15 km.

My comments:

The constructions that you sent as appendices demonstrate that you work with much creativity, sensitivity and insight in stereometry as well as in planimetry.
You make use of all great possibilities of Cabri. With Cabri, we can vary elements of a construction together with other ones in mutual dependence. And Cabri measures very accurately.
Your outcomes in case 3) are the same as mine. You also mentioned the exact outcome 1000*sqrt(4-sqrt(8)).
Your outcomes in case 2) approach those of professor Danzer even closer. I verified them with a Pascal program, for which I gave spherical coordinates to the vertices of the three triangles (see the picture). At the optimal elevations, I found your outcome 1.09053 . I congratulate you with this configuration.
I didn't verify your outcomes in case 1) as yet. This configuration seems rather similar to the optimal one of professor Danzer.
Your distances over the sphere agree with the formula that gives the relation between a chord and the corresponding arc:
arc = 2*arctan(k/sqrt(4-k²)).

I sent an e-mail to professor Danzer, asking whether he would like to submit a contribution for this Christmas prize problem. He sent a reprint of the Habilitationsschrift that he wrote in 1963. You yourself can find this in Discrete Mathematics 60 (1986), p.3-66 .
I extract from this booklet the following ideas.

Solution for 10 pirates:

We can try to improve a given configuration by moving a single point. If there is a geodetic pentagon within the configuration, we can flip one vertex inward and obtain a pentagon with sides which are as long as before the flipping, but taking less room.
By starting such a traject of improvements with distinct kinds of configurations, we hope that we don't get only local maximums, but the global maximum as well.
To see whether we can still enlarge the smallest distance in a given class of configurations or not, we can try to estimate the sum of the areas of the geodetic polygons in it, and compare them with the total area of the sphere.
With these methods we eventually found an optimal configuration, and we could prove that it is optimal at the same time.
Danzer's configuration looks like this.
The smallest distance is about 1.091426 megameter through space, and about 1.15448 megameter over the sphere.

In the proof there are also combinatoric arguments. For instance, we can easily prove for five points on the sphere that four of them lie in the same hemisphere (with a suitable choice of the poles). And we have to count the number of triangles in the configuration: 16 for ten pirates.
We have to consider the angles between the edges. The sum of the angles at a given vertex cannot be greater or smaller than 360 degrees. On the sphere, the sum of the angles in a polygon has an excess that is equal to its area (when measured in radians). Consider for example the triangle with as sides the equator and the meridians at 0 and 90 degrees eastern length. This triangle has three right angles and therefore an excess of 90 degrees. The area is pi/2.

Solution for 12 pirates:

It is 'almost trivial' that the platonic solid with twenty faces (icosaeder) gives the optimal configuration for twelve pirates. Because the icosaeder consists of equilateral triangles. It is important that the distance between two points inside an equilateral triangle is less than the length of a side. This doesn't hold for regular pentagons. The regular polygon with twelve sides (dodecaeder) doesn't give the optimal configuration for twenty pirates, because it consists of pentagons and can be improved by flipping and moving points.

My comments:

It is now clear how you found the optimal configuration for ten pirates.
I did something similar with a Pascal program:
First I searched for a good configuration with one point at the north pole, five in a horizontal plane in a regular pentagon, and four in a horizontal plane in a square, the square rotated over 9 degrees with respect to the pentagon.
Then I repeatedly searched two points at minimum distance, and placed them at an arc distance 0.0001 further apart.
In this way I found a configuration with a minimum distance which is almost 1.0912 megameter through space and a bit more than 1.154 megameter over the sphere.

I made also a little proof that this is almost optimal. If we would have sixteen equilateral triangles that cover the sphere, then each of those triangles would have area pi/4. Spherical geometry learns that the angles are 75 degrees, and the side length is 1.214 megameter. But this ideal situation doesn't occur, so the maximal minimum distance is somewhat smaller.

The awarding of the prizes:

I didn't consider any contestant as an amateur, unless he indicated that he wished to be considered as such.
Consequently, Martien Luijcks receives the main prize in the category of the amateurs, because he is the only one of this kind among the four serious contestants.
Of course, professor Danzer has the very best configurations, but it is clear that he forms a category on his own. We offer him a newly created prize.
Then there remain two contestants in the category of the professionals. I found Harrie Schreuders the best of these two (see my comments on his contribution above). So he has the main prize of the professionals.
We offer mister Peter Janssen a prize of encouragement.

POSTSCRIPT

After delivering the prizes, I studied a bit more in the little book of Danzer.
First see above, my comments on Danzer.
Danzer proves that, in the optimal configuration with minimum distance d, for each point P there are three, four, five or zero other points at distance d. If there are zero, he calls P isolated. Between any two non-isolated points there is a path that runs via non-isolated points only. Inside a regular pentagon with side length d, there is an isolated point if and only if the angle of the pentagon is greater than 72 degrees.

After searching in his list of literature, the following ideas came to my mind. They are quite distinct from those of Danzer.
For twelve pirates, every angle between two geodetic lines in the configuration is 72 degrees.
The case of ten pirates is far more complex.
My proof that there are sixteen triangles is as follows. Suppose there are n triangles. The sum of the areas of these triangles is 4*pi, so the sum of the angular excesses is 4*pi. Therefore the sum of all angles in the configuration is (n+4)*pi. But this sum is also 10 times 2*pi, that is 20*pi. So n=16.
There are three important sets of configurations, much the same as Harrie Schreuders described them. We can denote them briefly as 1-5-4, 1-3-3-3 and 1-4-4-1. The optimal one is in the set 1-5-4.
In every vertex, the sum of the angles is 2*pi. This yields (for each of the three sets) ten linear equations with 16*3=48 variables.
For each triangle there are three equations that give the relation between the angle-measures and the side-lengths. So this yields 48 more (non-linear) equations with 72 variables. (72 = 48 + 48/2)
These last equations have the form cos(a) = cos(b)*cos(c) + sin(b)*sin(c)*cos(A), where A is the measure of the angle supporting the side with length a.
Thus the problem can be described as finding the maximal minimum side-length under the restriction that these 72 variables satisfy these 58 equations.
I exchanged e-mails with professor Danzer about this. He remarks that the tangent of the minimal length in the optimal configuration is a zero of a polynomial with integral coefficients. This polynomial has a rather high degree. We can approach the length with numerical methods as well.

Here is a nice little problem for everybody. Consider an equilateral triangle in the plane. Find four points inside that triangle or on the sides, such that the smallest of the six distances between two of those points is maximal.
Hint: some quadrangles are convex, some are not convex.

Hennie Reuvers, Maastricht 2 februari 2004.

click here for a computer program that seeks configurations of distant points at random.

click here for my main page.