Journal of Integer Sequences, Vol. 3 (2000), Article 00.2.5

Abstract: A set-theoretic structure, the magic carpet, is defined and some of its combinatorial properties explored. The magic carpet is a generalization and abstraction of labeled diagrams such as magic squares and magic graphs, in which certain configurations of points on the diagram add to the same value. Some basic definitions and theorems are presented as well as computer-generated enumerations of small non-isomorphic magic carpets of various kinds.

Introduction

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].

Definitions

Denote the subsets of S by S₁, ..., 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², 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).

Results

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).

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 - 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+xi)
		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^jin the polynomial P(n) given above. Note that the sequence d_j(n) is symmetric:

Let

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₀, d₁, d₂, d₃, d₄, d₅ = 1,1,1,2,2,3. Since d₅(n) > d_j(n) for 0 <= j <= 4, (*) gives d_{Tn - 5}(n) > d_{Tn - 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+xj)-1		(1+xi)
			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+xi)
			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+xi)
i=1

which has coefficients 1112234445555444322111 and satisfies property P. Again, multiplying this by the remaining (1+xⁱ) 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+xi)	=	(1+xn)		(1+xi)
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.

Numerical Results

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).

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.

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).

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.

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.

References

[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.