Match Problem


Given n matches (i.e., rigid unit line segments), find the number of topologically distinct planar arrangements which can be made (Gardner 1991). In this problem, two matches laid end-to-end with no third match at their meeting point are considered equivalent to a single match, so triangles are equivalent to squares, n-match tails are equivalent to 1-match tails, etc.

Solutions to the match problem are planar connected unit-distance topological graphs on e edges, and the first few values for e=1, 1, 3, 5, 10, 19, 39, 84, 196, 479, ... (OEIS A003055).

See also

Cigarettes, Graph Smoothing, Graph Subdivision, Homeomorphic Graphs, Matchstick Graph, Planar Graph, Polynema, Topological Graph, Unit-Distance Graph

Explore with Wolfram|Alpha


Gardner, M. "The Problem of the Six Matches." In The Unexpected Hanging and Other Mathematical Diversions. Chicago, IL: Chicago University Press, pp. 79-81, 1991.Read, R. C. "From Forests to Matches." J. Recr. Math. 1, 60-172, Jul. 1968.Sloane, N. J. A. Sequence A003055/M2464 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Match Problem

Cite this as:

Weisstein, Eric W. "Match Problem." From MathWorld--A Wolfram Web Resource.

Subject classifications