A Think Again Media Group publication
Puzzle Stumper

The geometry of SET cards: four features and finite lines

By Phil Springer, Editor · Published · Updated · Puzzle Stumper

The Question

Match each person with the correct contribution. The people are Marsha Falco, Dion Gijswijt. The objects are 1974 card design, 2016 cap-set bound. Each slot contains one person and one object; use each person and contribution exactly once. Which pairing is correct?

Read the full story

The geometry of SET cards: four features and finite lines

The 81 SET cards carry four features: number, shape, color and shading. Each feature has three possible values, making a deck of 81 distinct cards. Marsha Falco developed the game in 1974 after using symbol cards in her work as a population geneticist. Its matching rule later connected a tabletop contest with finite geometry, including research by Dion Gijswijt and Jordan Ellenberg in 2016 on the size of sets containing no three-point line. [1, 2, 3, 4]

A valid SET contains three cards. For each of the four features considered separately, the cards must be either all alike or all different. Three red cards can therefore satisfy the color condition, as can one red, one green and one purple card. Two red cards and one green card fail that condition. Shape, number and shading each undergo the same independent test. Meeting three of the four conditions is insufficient. [1, 2]

The possible numbers are one, two and three. The shapes are ovals, diamonds and squiggles, and the shadings are open, striped and solid. Combining any choice of number with any shape, color and shading gives one card. The four features vary independently: no feature restricts which values another feature can take. This independent choice across four categories gives three times three times three times three possibilities. [1, 3]

Play begins with twelve cards laid out. Everyone searches at the same time, with no individual turns. Someone identifying a SET takes those three cards, and replacement cards come from the deck. If the layout contains no SET, three more cards are added. Play continues until the deck has been used and no SET remains on the table; the player who has collected the most sets wins. The cards offer a shared search space that changes as triples are removed. [1, 2]

Numbering each feature’s values 0, 1 and 2 gives every card a four-coordinate address. Arithmetic in each coordinate is performed modulo 3: after 2 comes 0 again. Three equal values sum to 0 in this arithmetic, and three different values do too, because 0 plus 1 plus 2 is 3. A triple is therefore a SET exactly when its coordinate vectors add to the zero vector. [2, 3]

This representation places the deck in a four-dimensional affine space over the three-element field. The SETs are its three-point lines. Given any two distinct cards, precisely one third card completes their line. Each coordinate of the missing card is determined: repeat a feature if the first two agree, or supply its unused third value if they differ. There is no choice remaining once those two cards have been specified. [3]

Consequently, a randomly selected third card has one successful possibility among the 79 cards outside a chosen pair. The probability that three distinct random cards form a SET is 1 in 79. Counting all pairs and dividing by the three pairs inside each successful triple gives 1,080 SETs in a full deck. A random twelve-card layout contains about 2.78 SETs on average, although an average does not guarantee even one in a particular layout. [2]

A collection containing no SET is a cap. In the four-dimensional space of the ordinary deck, the largest cap contains 20 cards. Every collection of 21 distinct SET cards must therefore contain a SET. The geometric result behind this boundary predates the commercial game: Giuseppe Pellegrino established the corresponding maximum in 1971. Falco’s later design gave this finite-geometric problem a physical form that players could manipulate and search. [3]

The four features can be extended by adding further independent categories. With three values per feature, n features produce 3 to the power n cards. In dimensions one through four, the largest SET-free collections have sizes 2, 4, 9 and 20. Adding features makes a larger space, while preserving the condition that a prohibited triple sums to zero coordinate by coordinate. The general cap-set problem asks how large a collection can become while still avoiding every such triple. [2, 4]

Restricting SET cards to the red cards produces a three-feature game with 27 cards. Keeping only red ovals leaves two variable features, which can be represented on a three-by-three array. A five-feature version can instead add size, with small, medium and large values, producing 243 cards. Each change alters the number of independent coordinates while keeping three possible values in each coordinate. These physical subsets and extensions make the dimensional change visible without changing the three-card line condition. [2, 3]

In 2016, Ellenberg and Gijswijt obtained an upper bound growing like c to the power n, for a constant c smaller than 3. Their independent work used a polynomial method building on a recent result of Ernie Croot, Vsevolod Lev and Péter Pach. Because the whole space grows as 3 to the power n, the bound forces the maximum possible SET-free proportion to shrink as dimension increases. It constrains the general family of spaces rather than supplying an exact maximum for every dimension. [4]

[1] PlayMonster: SET, official game description and rules. https://playmonster.com/product/set/

[2] Dion Gijswijt: Lines in F3n, STAtOR 20(2), 2019. https://www.vvsor.nl/wp-content/uploads/2018/11/STAtOR-2019-2-10-13-Gijswijt.pdf

[3] Benjamin Lent Davis and Diane Maclagan: The Card Game SET. https://www.playmonster.com/wp-content/uploads/2019/10/set.pdf

[4] Jordan Ellenberg and Dion Gijswijt: On large subsets of Fnq with no three-term arithmetic progression, 2016. https://arxiv.org/html/1605.09223v1

Show the answer

The Answer

Marsha Falco: 1974 card design; Dion Gijswijt: 2016 cap-set bound.

Send this question to a friend

Read next

By clicking “Send me a stumper” you agree to Puzzle Stumper’s Terms of Use and Privacy Policy.