The Tree Planting Problem on a Sphere
Stephen J. Ruberg · Mathematics Magazine · 1980
The tree planting problem has been a popular recreational pastime for many years. It has the following simple statement: How can n points in the plane be arranged in rows, each containing exactly k points, to produce a maximum number of rows? In the latter half of the 19th century, the famous mathematician J. J. Sylvester occupied much of his time with this question and related problems. Although this puzzle has been around for many years, only in some particular cases has limited progress been made, with virtually no progress toward a general solution. Even for small values of k such as three and four, only a handful of results is known [1]. Here we consider the tree planting question on a sphere, where a line is defined to be a great circle and trees are in a row if they lie on a single line. Thus, in general, two points determine a unique line. However, if the two points are the endpoints of a diameter of the sphere, henceforth called antipodal points, then there exists an infinite number of lines through the two points. Clearly, any two distinct lines intersect at exactly two antipodal points. We offer no complete solution but we do present some plausible conjectures. Let us represent the points of a plane by a (gnomonic) projection to the center of a sphere tangent to the plane. Since any line in the plane will produce half a great circle on the sphere, the patterns of lines which are the solutions for the problem in the plane may be projected onto the sphere to help form the pattern of great circles which are' the solutions there. Obviously, for the spherical problem the case k = 2 is trivial. Then k = 3 and n = 3 or 4, the values of r, the maximum number of rows, are one and two, respectively. To find the value of r for n = 5, we will begin by projecting a single line containing three points, A, B and C, onto the sphere. Now by adding two antipodal points to the sphere, say D' and E', which are not in the great circle determined by A', B' and C', three new rows are introduced (see Figure 1). These antipodal points form great circles with each point projected on the sphere. Hence, five points produce four rows. This example illustrates certain important aspects of this projection procedure. First, the straight line containing three points is the solution to the problem in the plane. Second, the addition of antipodal points on the sphere is the best way to include these points in the pattern since they form a new row of three with every point already there. Consequently, there can be