Journal of Integer Sequences, Vol. 3 (2000), Article 00.2.5 |
Mike Keith
4100 Vitae Springs Road
Salem, OR 97306
Email addresses: efriedma@stetson.edu and domnei@aol.com
In its most general form, a magic carpet is a collection of k different subsets of a set S of positive integers, where the integers in each subset sum to the same magic constant m. In this paper we always take S = {1, 2, 3, ... n}, and refer to a magic carpet on this set as an (n, k)-carpet.
A (9,8)-carpet is shown in Figure 1, with each element of S depicted as a point (labeled with the element it represents) and each subset of S as a line connecting the points in that subset.
Figure 1. A (9,8) magic carpet
This is just an ordinary 3x3 magic square, with each row, column, and diagonal having the same magic sum. Indeed, the motivation for this study is to generalize the notion of a magic square to an arbitrary structure on the set {1...n}, and to count and classify all non-isomorphic carpets on n points. By doing so, all possible "diagrams" of this type, in which points are labeled by {1...n} and whose lines or circles or other geometric elements pass through points with the same sum, can be generated. By omitting labels, such a diagram turns into a puzzle whose object is to determine the magic numbering. For example, the seven intersections in Figure 2 can be numbered with {1...7} such that the circle and each of the two ellipses sum to the same value. Can you verify that this is a (7,3) magic carpet by finding such a numbering? (The answer is given later, in Figure 4.)
Figure 2. A 7-point diagram that can
be magically numbered.
A magic carpet is a generalization of other structures which have appeared in the literature, such as magic circles [5], magic stars [3], and magic graphs [2].
Denote the subsets of S by S_{1}, ..., S_{k}. Let element i in S be included ("covered") c_{i} times in the union of all the S_{i}. The thickness of a carpet is t = min{c_{i}} and its height is h = max{c_{i}}. Since t <= h, there are two cases: a smooth carpet with t = h, or a bumpy one with t < h. Because of the analogy with magic squares, holey carpets with t = 0 are not very interesting, since we would like each element of S to be covered at least once (or, equivalently, for every number from 1 to n to be used in labeling the figure). In fact, a magic square has t = 2, so we are also less interested in the thin carpets with t = 1. Instead, we prefer to concentrate on plush carpets with t >= 2.
Let the subset S_{i} have e_{i} elements. Define the weave of a carpet to be w = min{e_{i}}. Again motivated by magic squares, we note that loose carpets with w = 1 are not as interesting as tight ones with w >= 2. If all the e_{i} are equal (i.e., all subsets are the same size) then the carpet is balanced.
Example: an r x r magic square, r >= 3 odd (with rows, columns, and two diagonals having the same magic sum), is a magic carpet with n = r^{2}, k = 2r + 2, t = 2, h = 4 and w = r. It is balanced but not smooth, since t < h. Its non-smoothness is due to the diagonals being covered three times and the central square four times, while the rest are only covered twice. If the diagonals are omitted (so that we have a so-called semi-magic square) then it becomes smooth. In either case, it is plush (since t = 2) as well as tight (since w >= 2).
Define a basic magic carpet to be one that is both plush and tight. Two magic carpets are isomorphic if they are equivalent under some permutation of the elements of S. (Of course, equality of the collection of subsets is made without regard to order of the subsets.) The motivation for this definition is that two carpets which are equivalent under a permutation of S correspond to two different magic numberings of the same "figure"; i.e., we seek magic carpets with the same basic structure. In other words, we wish to enumerate all essentially different magic-numbering puzzles (blank diagrams), not all distinct solutions (labeled diagrams).
The primary combinatorial problem is to determine B(n) or B(n,k), the number of non-isomorphic basic magic carpets with given parameters. We also denote by M(n,k,t,h) the number of magic carpets (basic or not) of type (n,k,t,h).
Theorem 1: B(n) = 0 for n < 5, B(5) = 1, B(n) >= 1 for n >= 6.Proof: The values for n <= 5 are easily obtained by direct enumeration. For n > 5, observe that any (n, k) magic carpet can be extended to an (n+1, k) carpet by taking each S_{i}, adding 1 to each of its elements, then appending the element "1".
The unique smallest basic magic carpet, with (n,k,t,h) = (5,3,2,2), can be drawn as shown in Figure 3. It is smooth but not balanced.
Figure 3. The unique (5,3) basic
magic carpet.
Theorem 2: M(n,k,t,h) = M(n,k,n-h,n-t).
Proof: From each (n,k,t,h) carpet, form another one by taking the complements of the S_{i}.
Two carpets which are related by complementation of the subsets are called duals. Note that if C' is the dual of carpet C that has magic constant m, then C' has magic constant T_{n} - m, where T_{n} = n(n+1)/2, the nth triangular number.
We now ask a fundamental question: for a given n, which values of k admit a basic magic carpet? From the definitions it is clear that 2 <= k <= 2^{n} - n - 1 (the latter being the number of subsets with at least two elements); however, the actual range of k is considerably smaller than this.
Theorem 3: There is a basic (n,k) magic carpet if and only if n >= 5 and 3 <= k <= q, where q is the largest coefficient in the polynomial
n | |||
P(n) | = | (1+x^{i}) | |
i=1 |
Proof: See Theorem 1 for the proof that n >= 5 is necessary and sufficient. Obviously k cannot be 2, because two distinct subsets of {1...n} cannot cover all elements twice. Thus k >= 3 is necessary. That k <= q is necessary is trivial, since the coefficient of x^{j} in P(n) is the number of distinct subsets of {1...n} whose elements sum to j, and q is by definition the maximum coefficient.
We now show that 3 <= k <= q is sufficient.
Let d_{j}(n) be the coefficient of x^{j}in the polynomial P(n) given above. Note that the sequence d_{j}(n) is symmetric:
d_{j}(n) = d_{T}_{n}_{ - j}(n). | (*) |
Let
q(n) | = | max | d_{j}(n) |
j |
which equals the maximal number of subsets of {1,...n} that have the same sum. Finally, define m(n) to be the largest integer such that d_{m(n)}(n) = q(n).
Lemma 1: T_{n}/2 <= m(n) <= T_{n} - 5.
Proof: The first inequality follows from (*). For n >= 4, d_{0}, d_{1}, d_{2}, d_{3}, d_{4}, d_{5} = 1,1,1,2,2,3. Since d_{5}(n) > d_{j}(n) for 0 <= j <= 4, (*) gives d_{T}_{n}_{ - 5}(n) > d_{T}_{n}_{ - j}(n) for 0 <= j <= 4, which means that m(n) is at most T_{n} - 5.
Lemma 2: Let n >= 6 and 1 <= j <= n. There are at least two subsets of {1...n} that add to m(n) and contain j.
Proof: The number of subsets of {1...n} that add to m(n) and contain j is the coefficient of x^{m(n)-j }in the polynomial
n | ||||
P(n, j) | = | (1+x^{j})^{-1} | (1+x^{i}) | |
i=1 |
We prove by induction on n that this coefficient is always at least 2.
By Lemma 1, it is necessary to show that the coefficients of x^{r} in P(n,j) are at least 2 for T_{n}/2 <= r-j <= T_{n} - 5, or T_{n}/2 - j <= r <= T_{n} - 5 - j. If a given P(n,j) satisfies this we say that P(n,j) has property P.
The lemma is true for n=6 since the coefficients of P(n,j) are
j=1: 101112222323222211101 j=2: 11012222233222221011 j=3: 1111123322233211111 j=4: 111212323323212111 j=5: 11122233233222111 j=6: 1112233333322111
and each of these (as indicated by the boldface numbers) has property P.
Now consider two cases:
Case I: j <= 6. We have
n | ||||
P(n, j) | = | P(6, j) | (1+x^{i}) | |
i=7 |
We know P(6, j) has property P (see table above), and multiplying by each factor i in the product is equivalent to shifting the vector of coefficients to the right by i places and adding to the original. This preserves property P.
Case II: j > 6. In this case we start with
6 | |
(1+x^{i}) | |
i=1 |
which has coefficients 1112234445555444322111 and satisfies property P. Again, multiplying this by the remaining (1+x^{i}) will preserve property P.
Lemma 3: d_{m(n-1)}(n) = d_{m(n-1)}(n-1) + d_{m(n-1)-n}(n-1).
Proof: Since
n | n-1 | ||||
(1+x^{i}) | = | (1+x^{n}) | (1+x^{i}) | ||
i=1 | i=1 |
it follows from the definition of d_{j}(n) that d_{j}(n) = d_{j}(n-1) + d_{j-n}(n-1). The lemma follows by setting j = m(n-1).
Lemma 4: For n >= 10, q(n-1) > 2n.
Proof: Consider the equation of Lemma 3. The left-hand side is no larger than q(n). The first term on the right-hand side is q(n-1). The second term is at least 2, because Lemma 1 says that m(n-1)-n >= T_{n-1}/2 - n, the right-hand side of which is at least 3 (if n >= 7), and d_{j}(n) is at least 2 if j is at least 3. Therefore, q(n) >= q(n-1)+2.
Now note that the values of q(n), starting with n=5, are:
3, 5, 8, 14, 23, 40, 70, 124, 221, 397, ...
which is sequence A25591 in [6]. Since q(10-1) = 23 > 210, the lemma is true for n=10. Using q(n) >= q(n-1)+2 and induction on n completes the proof.
We can now prove Theorem 3 by induction. First, it is true for n < 10 by direct construction by computer. We can construct (n,k) basic magic carpets for 3 <= k <= q(n-1) by taking an (n-1,k) carpet and appending n to each subset. By Lemma 4, this gives carpets for 3 <= k <= 2n.
Next, we construct an (n,k) basic magic carpet with k = 2n and magic constant m(n). For each j, 1 <= j <= n, we find two subsets which add to m(n) and contain j, which is possible by Lemma 2. We can add any number of additional subsets and still have a basic magic carpet, thus producing basic (n,k) carpets for 2n <= k <= q(n), and completing the proof.
Table 1 shows all values of B(n,k) up to n=8, determined by computer calculation. The initial values of B(n), starting with n=5, are 1, 10, 271, 36995, ... (sequence A55055).
k=3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | Total | |
n=5 | 1 | 1 | |||||||||||
6 | 2 | 4 | 4 | 10 | |||||||||
7 | 2 | 23 | 98 | 105 | 38 | 5 | 271 | ||||||
8 | 6 | 112 | 1300 | 5570 | 10090 | 9907 | 6240 | 2739 | 840 | 170 | 20 | 1 | 36995 |
Table 1. The values of B(n,k) for small indices.
Table 2 lists all the basic carpets for small values of n and k. For each carpet, the magic sum and the elements in each subset are listed (in a compact format: 1234 means {1,2,3,4}).
(n,k) Sum Subsets(5,3) 10 1234 235 145 (6,3) 14 2345 1346 1256 15 12345 2346 1356 (6,4) 11 1235 245 236 146 12 1245 345 1236 246 14 2345 1346 1256 356 15 12345 2346 1356 456 (6,5) 9 234 135 45 126 36 10 1234 235 145 136 46 11 1235 245 236 146 56 12 1245 345 1236 246 156 (7,3) 19 13456 12457 12367 21 123456 23457 13467 (7,4) 14 1256 356 1247 347 15 2346 1356 1347 1257 15 2346 456 1347 1257 15 12345 1356 1347 267 15 12345 456 1347 267 15 12345 2346 1257 267 16 12346 2356 2347 1357 16 12346 1456 2347 1357 16 12346 2356 1357 457 17 12356 2456 12347 2357 17 12356 2456 12347 1457 17 12356 2456 12347 1367 17 2456 12347 2357 1367 17 12356 2456 12347 467 17 12356 12347 2357 467 17 12356 12347 1457 467 18 12456 3456 12357 1467 18 3456 12357 2457 1467 18 12456 3456 12357 567 19 13456 12457 3457 12367 19 13456 12457 12367 1567 21 123456 23457 13467 12567 21 123456 23457 13467 3567 (8,3) 24 123567 14568 23478 24 123567 123468 4578 25 124567 123568 123478 25 34567 123568 123478 28 1234567 234568 134578 28 1234567 134578 25678
Table 2. The non-isomorphic basic magic carpets for small (n,k).
The (5,3) carpet was shown graphically in Figure 3. The (6,3), (6,4), (6,5), and (7,3) carpets are depicted in Figure 4 (in the same order they are listed in Table 2).
(6,3):
(6,4)
(6,5)
(7,3)
Figure 4. The distinct basic magic carpets for n=6 and (n,k) = (7,3).
These figures show just one way of diagramming each magic carpet (in this case, primarily using circles and ellipses). The question of how best to visualize a carpet is primarily an aesthetic one.
The first (6,3) carpet in Figure 4 (one of the "magic circle" figures shown in [5]) is the smallest one that is both smooth and balanced, and also the smallest one with a high degree of symmetry (six-fold).
Since many well-known magic structures (such as magic squares and stars) are either smooth and/or balanced, it is of interest to enumerate just the smooth or balanced basic carpets. Table 3 shows the number of smooth basic carpets for all (n,k) up to n=9. The last column is sequence A55056.
k=3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | Total | |
n=5 | 1 | 1 | ||||||||||||
6 | 1 | 1 | ||||||||||||
7 | 2 | 2 | 2 | 1 | 7 | |||||||||
8 | 2 | 4 | 9 | 11 | 8 | 12 | 8 | 1 | 55 | |||||
9 | 3 | 19 | 10 | 548 | 156 | 2 | 568 | 1306 |
Table 3. The number of smooth basic (n,k) magic carpets up to n=9.
In this table, empty cells indicate that there are no smooth carpets for that (n,k). (There are also none for n=9 and k > 15). Some of these missing (n,k) values are explained by:
Theorem 4: (n,k) basic balanced carpets can exist only if there exists a 2 <= t <= k with
tT_{n} = 0 (mod k).
Proof: Since each element of S appears exactly t times in the union of all the subsets, the sum of all elements of the subsets is tT_{n}. This means that the magic constant is tT_{n}/k, which must be an integer, and so the theorem follows.
For example, for n=9 smooth carpets cannot exist, by Theorem 4, for k = 13, 14, 16, 17, 19, 22, and 23. However, this theorem does not predict all inadmissable k values - Table 3 also gives zeros for k = 4, 7, 8, 11, 18, 20, and 21. A complete characterization of which (n,k) pairs permit smooth basic carpets remains an open problem.
The largest k value which admits a smooth carpet (for n=5, 6...) is 3, 3, 8, 14, 15... (sequence A55057).
Table 4 gives the number of balanced basic carpets for all (n,k) up to n=9 (last column is sequence A55605).
k=3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | Total | |
6 | 1 | 1 | |||||||||
7 | 1 | 1 | 2 | 1 | |||||||
8 | 1 | 5 | 12 | 15 | 4 | 1 | 38 | ||||
9 | 2 | 10 | 73 | 343 | 699 | 688 | 367 | 118 | 22 | 2 | 2324 |
Table 4. The number of balanced basic (n,k) magic carpets up to n=9.
The largest k value which admits a smooth carpet (for n=6, 7,...) is 3, 5, 8, 12, 20, 32, 58, 94, 169, 289... (sequence A55606).
All balanced carpets up to n=8 are listed in Table 5.
(n,k) Sum Subsets(6,3) 14 2345 1346 1256 (7,3) 19 13456 12457 12367 (7,4) 15 2346 1356 1347 1257 (7,5) 12 345 246 156 237 147 16 2356 1456 2347 1357 1267 (8,3) 25 124567 123568 123478 (8,4) 18 2367 1467 2358 1458 20 13457 12467 12458 12368 21 23457 12567 13458 12468 22 23467 13567 23458 12478 27 234567 134568 124578 123678 (8,5) 16 2356 2347 1267 1348 1258 16 1456 1357 1267 1348 1258 17 2456 2357 1367 2348 1358 17 2456 1457 1367 2348 1358 18 3456 2457 1467 2358 1458 18 3456 2367 1467 2358 1458 18 3456 2457 2367 1458 1368 20 23456 13457 12467 12458 12368 21 23457 13467 12567 13458 12468 21 13467 12567 13458 12468 12378 22 23467 13567 23458 13468 12478 22 23467 13567 23458 12568 12478 (8,6) 13 346 256 247 157 238 148 16 2356 1456 2347 1357 1348 1258 16 2356 1456 2347 1267 1348 1258 16 2356 1456 1357 1267 1348 1258 16 2356 2347 1357 1267 1348 1258 16 1456 2347 1357 1267 1348 1258 17 2456 2357 1457 1367 2348 1358 17 2456 2357 1457 1367 2348 1268 17 2456 2357 1457 2348 1358 1268 18 3456 2457 2367 1467 2358 1458 18 3456 2457 2367 1467 1458 1368 18 2457 2367 1467 2358 1458 1368 18 3456 2457 2367 1458 1368 1278 21 23457 13467 12567 13458 12468 12378 22 23467 13567 23458 13468 12568 12478 (8,7) 16 2356 1456 2347 1357 1267 1348 1258 17 2456 2357 1457 1367 2348 1358 1268 18 3456 2457 2367 1467 2358 1458 1368 18 3456 2457 2367 1467 1458 1368 1278 (8,8) 18 3456 2457 2367 1467 2358 1458 1368 1278
Table 5. All balanced basic carpets up to n=8.
Finally, Table 6 gives the number of smooth and balanced basic carpets up to n=9, and Table 7 lists them explicitly.
k=3 | 4 | 5 | 6 | 7 | 8 | 9 | Total | |
6 | 1 | 1 | ||||||
7 | 0 | |||||||
8 | 2 | 2 | 1 | 5 | ||||
9 | 1 | 2 | 6 | 9 |
Table 6. The number of
smooth-and-balanced basic (n,k) magic carpets up to n=9.
(n,k) Sum Subsets(6,3) 14 2345 1346 1256 (8,4) 18 2367 1467 2358 1458 27 234567 134568 124578 123678 (8,6) 18 2457 2367 1467 2358 1458 1368 18 3456 2457 2367 1458 1368 1278 (8,8) 18 3456 2457 2367 1467 2358 1458 1368 1278 (9,3) 30 234678 125679 134589 (9,6) 15 357 267 348 168 249 159 30 234678 135678 234579 125679 134589 124689 (9,9) 20 2567 3458 1568 2378 1478 2459 2369 1469 1379 20 3467 2567 3458 1568 1478 2459 2369 1379 1289 20 3467 2567 3458 1568 2378 2459 1469 1379 1289 25 24568 23578 14578 13678 23569 14569 23479 12679 13489 25 34567 24568 14578 13678 23569 23479 12679 13489 12589 25 34567 24568 23578 13678 14569 23479 12679 13489 12589
Table 7. All basic basic carpets that are both balanced and smooth, up to n=9.
Note that these appear in dual pairs, unless (a) one is a self-dual, like the first (8,4) example, or (b) the dual is not a 2-cover, like the second (8,4) example.
[1] Dudeney, H. E., "536 Puzzles and Curious Problems", Scribner's, 1967.
[2] Hartsfield, N. and Ringel, G. Pearls in Graph Theory: A Comprehensive Introduction, Academic Press, 1990.
[3] Heinz, H., M agic Stars, http: //www.geocities.com/CapeCanaveral/Launchpad/4057/magicstar.htm
[4] Kordemsky, B., "The Moscow Puzzles", Scribner's, 1972
[5] Madachy, J. S., Madachy's Mathematical Recreations, Dover, p. 86, 1979.
[6] Sloane, N. J. A. On-line Encyclopedia of Integer Sequences
(Concerned with sequences A25591, A55055, A55056, A55057, A55605, A55606. )
Received Feb. 23, 2000; revised version received May 30, 2000; published in Journal of Integer Sequences June 10, 2000.