Problem 65: Magic Configurations

Statement

Let a finite set of points P in the plane be given, with each point assigned a positive real weight. P is called a magic configuration if every line determined by two or more points has the same sum of weights, i.e., the sum of the weights of the points through which each line passes is the same. The problem is to prove or disprove that there are only four essentially distinct magic configurations:

1. Points in general position, with (e.g.) every point assigned weight 1.
2. All points collinear.
3. n - 1 points collinear with weight (e.g.) 1, and one point not on that line with weight n - 2.
4. The 7-point configuration shown in Fig. 4, or its projective equivalents.

   Figure 4: Edge midpoints have weight 2, while all other points have weight 1. All nine lines have sum 4.

   

Origin

[Mur71]

Status/Conjectures

Settled positively, 2007: [ABK+08]

Motivation

The terminology ``magic configuration'' comes from the notion of magic squares, 2D matrices such that every row, column, and (optionally) diagonal sums to the same value.

Partial and Related Results

An ordinary line is one that passes through exactly two points. Scaling weights of a magic configuration so that the weights on each line sum to 1, the weight of the points on ordinary lines must be ${\frac{{1}}{{2}}}$ in any magic configuration other than the third example above. It is known that, for n$\ge$3 noncollinear points, at least ${\frac{{6}}{{13}}}$n lines must be ordinary [CS93].

Settled in [ABK+08], the journal version of a paper that originally appeared in the Proceedings of the 2007 Symposium on Computational Geometry.

Appearances

Originally posed by U. S. R. Murty in [Mur71]. Reposed by Murty at a June 2006 celebration of V. Chvátal's 60th birthday. Two people who heard this posing, X. Chen and P. Taslakian, brought the problem to the conference Discrete and Computational Geometry--Twenty Years Later in Snowbird, June 2006. In particular, Chen posed the problem at the open-problem session.

Categories

point sets

Entry Revision History

J. O'Rourke, 14 Jul. 2006; E. Demaine, 15 Jul. 2006; J. O'Rourke, 16 Jul. 2008.

Bibliography

ABK+08

Eyal Ackerman, Kevin Buchin, Christian Knauer, Rom Pinchasi, and Günter Rote.
There are not too many magic configurations.
Discrete Comput. Geom., 39:3-16, 2008.

CS93

J. Csima and E. T. Sawyer.
There exist 6n/13 ordinary points.
Discrete & Computational Geometry, 9(1):187-202, December 1993.

Mur71

U. S. R. Murty.
How many magic configurations are there?.
American Mathematical Monthly, 78(9):1000-1002, November 1971.