Nội dung

Dense Packings of Equal Disks in an Equilateral Triangle: From 22 to 34 and Beyond R. L. Graham B. D. Lubachevsky AT&T Bell Laboratories, Murray Hill, New Jersey 07974 Submitted: August 11, 1994; Accepted: December 7, 1994 ABSTRACT Previously published packings of equal disks in an equilateral triangle have dealt with up to 21 disks. We use a new discrete-event simulation algorithm to produce packings for up to 34 disks. For each n in the range 22 ≤ n ≤ 34 we present what we believe to be the densest possible packing of n equal disks in an equilateral triangle. For these n we also list the second, often the third and sometimes the fourth best packings among those that we found. In each case, the structure of the packing implies that the minimum distance d(n) between disk centers is the root of polynomial Pn with integer coefficients. In most cases we do not explicitly compute Pn but in all cases we do compute and report d(n) to 15 significant decimal digits. Disk packings in equilateral triangles differ from those in squares or circles in that for triangles there are an infinite number of values of n for which the exact value of d(n) is known, namely, when n is of the form ∆(k) := k(k+1) . 2 It has also been conjectured that d(n−1) = d(n) in this case. Based on our computations, we present conjectured optimal packings for seven other infinite classes of n, namely n = ∆(2k) + 1, ∆(2k + 1) + 1, ∆(k + 2) − 2, ∆(2k + 3) − 3, ∆(3k + 1) + 2, 4∆(k), and 2∆(k + 1) + 2∆(k) − 1 . We also report the best packings we found for other values of n in these forms which are larger than 34, namely, n = 37, 40, 42, 43, 46, 49, 56, 57, 60, 63, 67, 71, 79, 84, 92, 93, 106, 112, 121, and 254, and also for n = 58, 95, 108, 175, 255, 256, 258, and 260. We say that an infinite class of packings of n disks, n = n(1), n(2), ...n(k), ..., is tight , if [1/d(n(k) + 1) − 1/d(n(k))] is bounded away from zero as k goes to infinity. We conjecture that some of our infinite classes are tight, others are not tight, and that there are infinitely many tight classes. the electronic journal of combinatorics 2 (1995), #A1 1 2 Introduction Geometrical packing problems have a long and distinguished history in combinatorial math- ematics. In particular, such problems are often surprisingly difficult. In this note, we describe a series of computer experiments designed to produce dense packings of equal nonoverlapping disks in an equilateral triangle. It was first shown by Oler in 1961 [O] that the densest packing of n = ∆(k) := k(k+1) 2 equal disks is the appropriate triangular subset of the regular hexagonal packing of the disks (well known to pool players in the case of n = 15). It has also been conjectured by Newman [N] (among others) that the optimal packing of ∆(k) − 1 disks is always obtained by removing a single disk from the best packing for ∆(k), although this statement has not yet been proved. The only other values of n (not equal to ∆(k)) for which optimal packings are known are n = 2, 4, 5, 7, 8, 9, 11 and 12 (see Melissen [M1], [M2] for a survey). As the number n of packed disks increases, it becomes not only more difficult to prove optimality of a packing but even to conjecture what the optimal packing might be. In this paper, we present a number of conjectured optimal packings. These packings are produced on a computer using a so-called “billiards” simulation algorithm. A detailed description of the philosophy, implementation and applications of this event-driven algorithm can be found in [L], [LS]. Essentially, the algorithm simulates a system of n perfectly elastic disks. In the absence of gravitation and friction, the disks move along straight lines, colliding with each other and the region walls according to the standard laws of mechanics, all the time maintaining a condition of no overlap. To form a packing, the disks are uniformly allowed to gradually increase in size, until no significant growth can occur. Not infrequently, it can happen at this point that there are disks which can still move, e.g., disk 3 in t7a13 (see Fig. 1.1). Every packing of n disks occurring in the literature for n different from ∆(k) and ∆(k) − 1 which has been conjectured or proved to be optimal was also found by our algorithm. These occur for n = 13, 16, 17, 18, and 19 (see [M1], [MS]). This increases our confidence that the new packings we obtain are also optimal. The new packings cover two “triangular periods”: 21 = ∆(6) to ∆(7) to ∆(8) = 36. In addition, we conjecture optimal packings for seven infinite classes of n, namely, n = ∆(2k)+1, ∆(2k+1)+1, ∆(k+2)−2, ∆(2k+3)−3, ∆(3k+1)+2, 4∆(k), and 2∆(k+1)+2∆(k)−1, where k = 1, 2.... Each class has its individual pattern of the optimal packings which is different from patterns for other classes. These were suggested by the preceding packings, and we give 3 the electronic journal of combinatorics 2 (1995), #A1 5 1 2 4 5 6 2 3 7 3 1 6 t7a13 0.366025403784439 7 4 t7a16 13 bonds 0.366025403784439 16 bonds Figure 1.1: Two equivalent but nonisomorphic densest packings of 7 disks. packings for some additional values of these forms, namely, n = 37, 40, 42, 43, 46, 49, 56, 57, 60, 63, 67, 71, 79, 84, 92, 93, 106, 112, 121, and 254, as well as for n = 58, 95, 108, 175, 255, 256, 258, and 260. We say that an infinite class of packings of n disks, n = n(1), n(2), ...n(k), ..., is tight , if [1/d(n(k) + 1) − 1/d(n(k))] is bounded away from zero as k goes to infinity. We conjecture that some of our infinite classes are tight, others are not, and that there are infinitely many tight classes. 2 The packings We performed a small number of runs with n = 21, 27, 28, 35 and 36 disks. In every case, the resulting packings were consistent with the existing results (n = ∆(k)) and conjectured (n = ∆(k) − 1). The bulk of our efforts concentrated on the other 11 values of n, for 21 ≤ n ≤ 36. These are presented in Figures 3.1 to 3.11. To navigate among the various packings presented we will use the labeling system illustrated by Fig. 3.1 t22a. Here, n = 22, “a” denotes that the packing is the best we found, “b” would be the second best (as in t23b in Fig. 3.2), “c” would be third best, and “d” would be fourth best. 4 the electronic journal of combinatorics 2 (1995), #A1 Small black dots in the packing diagrams are “bonds” whose number is also entered by each packing. For example, there are 47 bonds in t22a. A bond between two disks or between a disk and a boundary indicates that the distance between them is zero. The absence of a bond in a spot where disk-disk or disk-wall are apparently touching each other means that the corresponding distance is strictly positive, though perhaps too small for the resolution of the drawing to be visible. For example, there is no bond between disk 1 and the left side of the triangle in t18a (Fig. 2.2); according to our computations, the distance between disk 1 and the side is 0.0048728... of the disk diameter. (Packing t18a was constructed in [M1].) Each disk in most of the packings is provided with a label which uniquely identifies the disk in the packing. This labeling is nonessential; it is assigned in order to facilitate referencing. 4 1 12 11 4 5 17 13 10 14 14 7 13 6 11 9 8 5 17 14 11 8 15 16 1 7 10 2 9 9 10 6 2 16 15 7 12 t17a40 2 40 bonds 1 14 6 15 12 3 9 8 6 4 17 17 11 8 5 10 t17b36 0.208735129275750 15 4 42 bonds 0.211324865405187 15 9 12 13 12 7 1 5 9 3 10 t17b42ns 36 bonds 15 t17a43 6 14 4 43 bonds 4 16 8 16 7 13 2 13 11 3 0.211324865405187 2 3 12 t17a42 0.211324865405187 5 17 1 3 16 0.208735129275750 3 2 1 16 7 14 10 11 17 6 13 5 8 t17b42s 42 bonds 0.208735129275750 42 bonds Figure 2.1: The best (t17a40, t17a42, t17a43) and the next-best (t17b36, t17b42ns, t17b42s) packings of 17 disks. the electronic journal of combinatorics 2 (1995), #A1 5 Each disk normally has at least three bonds attached. The polygon formed by these bonds as vertices contains the center of the disk strictly inside. This is a necessary condition for packing “rigidity”. In [LS], where the packing algorithm was applied to a similar problem, the disks without bonds were called “rattlers.” A rattler can move freely within the confines of the “cage” formed by its rigid neighbors and/or boundaries. (If we “shake” the packing, the rattler will “rattle” while hitting its cage.) t22a has two rattlers, disks 3 and 5. In the packing diagrams, all disks, except for the rattlers, are shaded. A number with 15 significant digits is indicated for each packing in the figures, e.g., the number 0.17939 69086 11866 for packing t22a. This number is the disk diameter d(n) which is measured in units equal to the side of the smallest equilateral triangle that contains the centers of all disks. For packing t22a such a triangle is the one with vertices at the centers of disks 22, 17, and 12. This unit of measure for d(n) conforms with previously published conventions. Sometimes several packings exist for the same disk diameter. An example is t7a13 and t7a16 in Fig.1.1. Thus, we distinguish such packings by suffixing their labels with the number of bonds. Other examples are t17a40, t17a42, and t17a43 in Fig. 2.1, t22b42 and t22b50 in Fig. 3.1. However, even the number of bonds may not distinguish different packings of the same disk diameter; for example, t17b42ns and t17b42s in Fig. 2.1, where the provisional “ns” stands for “non-symmetric” and “s” for “symmetric.” We point out that the a-packings of 17 and 18 disks that we show have previously been given by Melissen and Schuur [MS], who also conjecture their optimality. 3 Additional comments Fig. 3.2: Two more c-packings for 23 disks that are not shown in the figure were generated: t23c55.1 and t23c55.2. Both have 55 bonds. t23c55.1 can be obtained by combining the left side of t23c53 with the right side of t23c57. t23c55.2 is a variant of t23c55.1. Fig. 3.3: Disk 20 in t24c56 and in t24c59 is locked in place because its center is strictly inside the triangle formed by the three bonds of disk 20. In both packings, the distance of the disk center to the boundary of this enclosing triangle is the distance to the line between bonds with the left side of the triangle and disk 24, and is 0.0317185... of the disk diameter. Fig. 3.4: The given d-packing of 25 disks t25d60 is symmetric with respect to the vertical axis. An equivalent non-symmetric d-packing t25d53 was also obtained in which all disks are the electronic journal of combinatorics 2 (1995), #A1 6 located in the same places as in t25d60, except for disks 5, 12, 13, 14, 23, and 24. These six disks form a pattern which is roughly equivalent to that formed by disks 10, 14, 19, 25, 20, and 22, respectively, in t25b. Disk 24 in t25d53 is a rattler. Fig. 3.6: Only one of the two b-packings of 29 disks we found is shown, namely, t29b63.2. The other b-packing, t29b63.1, differs in the placements of only disks 2, 3, 4, 7 as explained in Section 4. Fig. 3.8: Four a-packings of 31 disks exist; only three are shown in the figure; the fourth one, t31a81.1, is described in Section 4. Fig. 3.10: In t33a, the gap between disk 8 and left side is 0.0017032... of the disk diameter. In t33c, disk 7 is stably locked by its bonds with 3, 6, and 29. However, the distance from disk 7 center to the line on bonds with disks 3 and 6 is only 0.0002097575.... of the disk diameter. As a result, the cage of rattler disk 5 in t33c is very tight: the gap between disk 22 and disk 5 or disk 18 and disk 5 does not exceed 4 × 10−9 of the disk diameter. Fig. 3.11: In t34a, the small gaps between “almost” touching pairs disk-disk or disk-wall take on only three values (relative to the disk size): in pairs 20–31, 16–26, 23–27, 18–19, 1–27 the gap is 0.021359..., in pairs left-32, right-29 it is 0.024750..., and in pairs 4–34, 7–22, it is 0.042561... Similarly, there are only three values of gaps in each of t34b, t34c, and t34d. t34b: in pairs 18–19, 23–27, 17–28, 20–31, 16–26 the gap is 0.019583...; in pairs left-32, right-29 it is 0.022686...; in pairs 4–34, 7–22, it is 0.039035... t34c: in pairs 12–17, 22–27, 3–10, 14–21, 4–34. 3–16 the gap is 0.018864...; in pair left-15 it is 0.021850...; in pair 19-24 it is 0.037606... t34d: in pairs 2–4, 26–32, 15–22, 12–21, 3–16, 7–16 the gap is 0.018681...; in pair left-27 it is 0.021637...; in pairs 13–33, 19–30 it is 0.037242... 7 the electronic journal of combinatorics 2 (1995), #A1 3 9 11 8 12 11 12 1 15 5 8 2 13 17 4 18 7 6 7 2 16 13 40 bonds 9 7 11 15 36 bonds 7 16 13 13 3 5 4 6 2 1 6 0.203464834591373 15 10 10 14 t18b36 0.203465240539124 17 17 18 9 t18a 4 3 4 14 1 16 5 10 12 2 18 14 8 8 t18b40 0.203464834591373 1 18 12 10 16 9 14 6 15 17 3 5 11 t18b43 40 bonds 0.203464834591373 43 bonds Figure 2.2: The best (t18a) and the next best (t18b36, t18b40, t18b43) packings of 18 disks. 8 the electronic journal of combinatorics 2 (1995), #A1 17 15 4 18 22 6 12 8 19 11 7 1 13 16 3 7 4 13 8 5 20 10 12 2 6 17 t22a 20 47 bonds 0.179132453213560 20 6 1 16 13 8 21 15 14 7 10 42 bonds 19 19 11 18 t22b42 0.179396908611866 2 16 21 1 9 14 11 21 5 2 22 3 9 19 14 15 22 10 3 22 12 9 4 17 12 5 18 16 5 t22b50 0.179132453213560 8 1 20 6 18 7 2 15 3 13 11 17 10 4 21 14 9 t22c 50 bonds 0.178763669382058 46 bonds Figure 3.1: The best (t22a), the next-best (t22b42, t22b50), and the third-best (t22c) packings of 22 disks. 9 the electronic journal of combinatorics 2 (1995), #A1 17 22 10 4 6 15 22 8 11 3 19 10 2 1 7 18 2 3 13 11 12 16 6 23 19 9 5 7 13 4 21 18 14 1 17 52 bonds 0.174962364462008 4 21 16 3 2 19 22 5 1 7 23 15 5 16 20 14 19 23 13 3 8 10 17 13 11 14 6 52 bonds 8 18 11 23 7 12 20 8 16 t23b 0.175153309170525 15 9 5 t23a 2 12 20 21 14 20 15 17 9 10 9 21 t23c53 0.174457630187009 12 1 18 4 22 6 t23c57 53 bonds 0.174457630187009 57 bonds Figure 3.2: The best (t23a), the next-best (t23b), and the third-best (t23c53, t23c57) packings of 23 disks. 10 the electronic journal of combinatorics 2 (1995), #A1 13 17 22 12 11 9 14 6 5 4 7 2 19 17 14 24 15 21 16 1 18 12 3 19 22 2 1 3 8 20 23 7 18 21 15 6 t24a 5 63 bonds 0.171024411616889 19 13 6 16 16 24 5 11 11 2 9 7 18 4 15 17 5 3 21 2 7 4 14 10 6 20 17 9 53 bonds 23 22 20 21 4 19 23 24 16 t24b 0.174457630187010 22 10 13 8 13 11 23 10 20 9 24 3 14 12 8 1 t24c56 0.170613243353863 10 18 15 12 8 1 t24c59 56 bonds 0.170613243353863 59 bonds Figure 3.3: The best (t24a), the next-best (t24b), and the third-best (t24c56, t24c59) packings of 24 disks.