Communications of the ACM
Home/Magazine Archive/February 2012 (Vol. 55, No. 2)/Puzzled: Where Sets Meet (Venn Diagrams)/Full Text
Last byte
Puzzled: Where Sets Meet (Venn Diagrams)
Credit: Branko Grnbaum / The University of Washington
The theme is Venn diagrams, those ubiquitous but useful pictures, usually consisting of two or three intersecting circles that illustrate how sets meet.
Venn diagrams were devised and introduced in 1880 by John Venn (18341923), Master of Arts, Fellow, and Lecturer in Moral Science, Caius College, Cambridge University, in a paper entitled "On the Diagrammatic and Mechanical Representation of Propositions and Reasonings." To be precise, a Venn diagram of order n is a collection of n simple closed curves in the plane with the property that for each subset of the curves, there is exactly one component of the plane minus the union of the curves whose points lie inside the curves in the subset and outside the rest of the curves. The Venn diagrams considered here have the additional requirement that they are "simple," meaning all intersections of curves are simple crossings involving just two curves.
Pictured in the figure here is an order-5 Venn diagram consisting of five congruent ellipses, due to Branko Grünbaum of the University of Washington, Seattle. Curiously, Venn himself did not believe such a construction was possible.
Venn diagrams are very special figures of which much can be said. Here are two puzzles based on properties of Venn diagrams, and a third concerning a property Venn diagrams may or may not have:
- Prove that Venn diagrams of all orders exist; that is, construct for each n a Venn diagram of order n.
- Show that every Venn diagram of order n has the same number of vertices (crossing points); how many?
- Prove or disprove that to any Venn diagram of order n another curve can be added, making it a Venn diagram of order n+1; remember, only simple crossings allowed.
Footnotes
Readers are encouraged to submit prospective puzzles for future columns to [email protected].
©2012 ACM 0001-0782/12/02 $10.00
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from [email protected] or fax (212) 869-0481.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2012 ACM, Inc.
No entries found