The Search For Set

Part 1: The Korean Word For Three is Set

David Van Brink, June 1997

Introduction

I was introduced to the game of Set early this year, 1997. It was during a ski trip with twenty of my closest friends, in Tahoe. Our first night there, over a cup of scotch and a roaring fireplace, in fact. You'll love this game, Rocky told me, It's a Vulcan children's game, he said. We just started playing, he didn't tell me the rules. They were fairly immediately clear, of course. After a few minutes, he asked, So, how many cards are there in the deck? 81 , I answered.

I will here presume you have a familiarity with the Set deck and the rules for Set. If not, you may wish to read the Set game's web site .

Now, I very much enjoyed playing this game. It had a wholemind sort of appeal, and the scotch was pretty good too. But, being of an analytical kink, my mind soon wandered from the rigors of competition, into loftier areas. Various questions came to mind. How many Sets are there in total? How many Sets is each card a member of? What's the largest number of cards you can have without any Sets at all? (This last question comes up during game play: Normally, there are 12 cards visible on the table. If there are no Sets on the table, 3 more cards are dealt. One might wonder the maximum number of cards which might ever be needed on the table.)

One note before I proceed. The word "set" has a definition in mathematics, specifically, in set theory. In this paper I will use the word "Set" (capitalized) to refer to a collection of three cards which is called a "Set" by the rules of the game of Set. I will usually refer to a group of cards as a collection, and the collection of all possible cards, a deck.

How Many Sets Are There?

We first make the simple observation that given any two cards, there exists one and only one third card which completes the Set. This fact is so useful and basic that I call it the Primary Theorem of Set.

The Primary Theorem Of Set: Given any two cards, there exists one and only one third card which completes the Set.

Proof is by construction, in four steps.

1. If the two cards are of the same shape, then the third card has that shape; otherwise, it must have whatever shape is not on either of the two first cards.

2. If the two cards are of the same shading, then the third card has that shading; otherwise, it must have whatever shading is not on either of the two first cards.

3. If the two cards are of the same color, then the third card has that color; otherwise, it must have whatever color is not on either of the two first cards.

4. If the two cards are of the same number, then the third card has that number; otherwise, it must have whatever number is not on either of the two first cards.

If you go through these four steps, you will find the unique third card that completes any two cards' set.

:.

Intuitively, every Set player knows this, of course. Still, if we're getting formal about it, it's best to spell things out. Also, this fact will be used so often in later discussion that it is convenient to name it. A simple corollary follows.

Corollary to the Primary Theorem Of Set: Any two Sets share either no cards in common, one card in common, or all three cards in common.

Proof is by contradiction. The Corollary may be restated as "no two Sets share exactly two cards in common." Assume we have two Sets which have two cards in common. Following the construction described in the proof to the Primary Theorem to find the third card for each Set will give the same third card for each Set; therefore the two Sets must, in fact, share 3 cards in common.

:.

This simple fact helps us to find the total number of Sets in the 81 card deck. To find all the Sets, we count how many choices there are for the first, second, and third cards of a Set. Any card can be the first card: 81 choices. Any of the remaining cards can be the second card: 80. Only one card may be the third card, by the Primary Theoreom. Choosing cards one at a time like this, however, will count each Set more than once; in fact, it will count each Set 6 times, since there are 6 ways to reorder 3 cards (123, 231, 312, 321, 213, and 132). So, the number of Sets in the deck is 81 * 80 * 1 / 6 = 1080.

How many Sets is each card a member of?

To determine how many Sets each card is a member of, we will count all the possible Sets for a particular card. Start with some card X. Then, we start taking cards from a pile of the 80 remaining cards, one at a time. For each card we remove from the pile, we also remove the unique third card which, together with the card X, completes a Set. The third card will never be one we've already removed from the pile; that would imply that the third card and X are members of two different Sets, which contradicts the Corollary to the Primary Theorem. Since we start with 80 cards in the pile, we can remove 40 pairs of cards from the pile, indicating that the card X is a member of 40 different Sets, and, therefore, each card in the Set deck is a member of 40 different Sets.

Since each card is a member of the same number of Sets, we should be able to multiply that number by the number of cards, and divide by three, to get the total number of Sets (since just multiplying the number of cards by the number of Sets per card will count every Set three times, once for each card in the Set). This gives us 40 * 81 / 3 = 1080.

What's the largest collection of cards with no Sets?

This is the most elusive of the problems I've so far considered. It can be restated in a couple of different ways: "What's the smallest number of cards which must contain a Set, regardless of which cards we choose?" and "What's the smallest collection of cards which contains at least one card from each of the 1080 Sets?"

A Counting Technique

The complete Set deck has 1080 Sets in it. That number is constant. When we take a collection from the deck, we are really dividing the deck into two subdecks, and each of those 1080 Sets then has four possible states: all three cards may be in the first subdeck; all three cards may be in the second subdeck; one card may be in the first subdeck, with two in the second; or two cards may be in the first subdeck, with one in the second.

In this diagram, a deck of seven cards has been divided into two subdecks, of four and three cards, respectively. The four card subdeck is shown to be Setless; that is, of the various possible pairs of cards within the subdeck, each pair's Set is completed by a card not in that subdeck. In the diagram, in fact, the six possible cardpairs can all be completed by the three cards in the other subdeck; two cardpairs are completed by each the three card subdeck. This leads us to a simple theorem.

Theorem: A collection of 55 cards must have a Set in it.

Proof is by contradiction. Suppose we have a 55 card Setless collection. This means that each of the 1080 Sets has at least one card in the remaining 26 cards (if none of the Set's three cards were in the remaining 26 cards, then all three would be present in the 55 card collection, which would not be Setless). Since each card is a member of 40 different Sets, the remaining 26 cards can only be members of, at most, 26 * 40 = 1040 Sets. This does not account for all 1080 Sets; therefore, at least 40 Sets must lie entirely within the 55 card collection.

:.

However, by noting the Primary Theorem, and looking at all the possible pairs of cards in the subdeck, we can find a lower bound than 55.

Theorem: A collection of 47 cards must have a Set in it.

Proof is by contradiction. Suppose we have a 47 card Setless collection. Since, by the Primary Theorem, any two cards are part of a Set, there are 47-choose-2, or 1081, Sets for which two of the cards lie in the 47 card Setless collection. But the entire deck has only 1080 Sets, and the initial supposition is false.

:.

Theorem: If the largest Setless collection for the n dimensional deck has S_n cards, then the largest Setless collection for the n+1 dimensional deck is S_n+1 where

2S_n <= S_{n+1 <= 3S_n.}

(This theorem was devised by Qarin Van Brink and Eric Uhrhane)

Proof of the lower boundary is by construction; of the upper, by contradiction.

If we consider the n+1 dimensional deck to consist of three slabs, each isomorphic to the n-dimensional deck, then we can construct a Setless collection of the n+1 dimensional deck consisting of two slabs containing the largest Setless collection from the n dimensional deck, and no cards in the third slab. Since every Set must exist either entirely in one slab (none can; each slab has either no cards or has a Setless collection from the n dimensional deck) or span all three slabs (none can; the third slab is empty), we have constructed a Setless collection of 2S_n cards.

Suppose we have a Setless collection of the n+1 dimensional deck containing 3S_n+1 cards. The sum of the numbers of cards in each of the three slabs must therefore be 3S_n+1. This means that at least one of the slabs has S_n+1 or more cards in it. The largest Setless collection for the n dimensional deck has S_n cards; therefore that slab must have a Set in it, and our initial assumption is false.

:.

Part 2: Answering the Lazy Way

I gather that there exist clean proofs of the largest setless collection... But alas, I'm not that smart. I used a computer search to discover the actual largest Setless collection. The simplest computer search would take trillions of years to complete; by precomputing all the solutions for the 27 card Set deck, and eliminating rotations and reflections in one of the three slabs, and only searching for very specific numbers of cards, I reduced the search time to about a week on a 90 Mhz Pentium processor.

The answer, by the by, is 20 cards.
Set Deck rendering visible in the introduction was rendered with QuickDraw 3d and custom software written using Metrowerks. The Set card images were borrowed without permission from the complete deck of .gif files on the www.setgame.com web site.