# The maximum number of SETs with six cards

The SET game works with a deck of $81$ cards. Each card contains a set of symbols with four attributes:

• color (red, green, purple),
• shading (empty, striped, or solid),
• shape (oval, squiggle, or rhombus),
• number of symbols (one, two, or three).

All the cards are unique. A SET occurs when three cards satisfy the following property for each of the four attributes:

• The attribute on each card is the same,
• or the attribute on each card is different

As an example for "the same", all three cards may have striped shading. As an example for "different", the three cards may have red, green, and purple color. In order for three cards to form a SET, they must satisfy this property for all four attributes.

Find the maximum number of SETs that can be present in six distinct cards.

• Just to clarify, if you have three cards with the same shapes and colors, for example, will that count as two sets? – nine9 Feb 22 '16 at 13:08
• @nine9 No; three cards are only a SET if they're either all the same or all different in each one of the four attributes. – DylanSp Feb 22 '16 at 13:12
• So if I have three cards and the are all stripped, but only two of them are oval, and the third is squiggle, then these cards are not in a set right? Also, if I have three cards, and all three are red, empty, ovals, but they are all difference symbols, are they a set? – Trenin Feb 22 '16 at 15:38
• @trenin if exactly 2 of your 3 cards are the same in some attribute, they are not a set. Your first example is not a set, your second example is. – Hellion Feb 22 '16 at 16:23
• There's actually a fun iOS game that works like this itunes.apple.com/us/app/groops/id659981940?mt=8 . – Slepz Feb 23 '16 at 0:21

For any two distinct cards, there exists aunique third card that completes the pair into a SET. If I pick three distinct cards $A,B,C$, then I can add three cards $X,Y,Z$ such that ABX and ACY and BCZ form SETs. Hence there exists a solution with three SETs.

To see that three SETs are best possible, we argue with linear algebra. We represent a card by a 4-dimensional vector $(w,x,y,z)$ over $\mathbb{Z}/3$. The card deck then consists of 81 vectors corresponding to the 81 cards in the SET game. Three vectors form a SET, if and only if they add up to the zero-vector.

Consider six vectors, and assume for the sake of contradiction that these six vectors contain four SETS.

• Two such sets can overlap in at most one vector. (If they agree in two elements, then they must also agree in the third one, as the third one is uniquely defined.)
• Hence each of the six vectors is contained in at most two SETs. (Three SETs would need the considered vector plus three disjoint pairs, that is, at least seven vectors).
• Hence each vector is contained in exactly two SETs. (Four SETs need altogether $4\cdot3=12$ vectors, and each of the two vectors can only be used twice.)

Now let us wrap things up. Consider some fixed vector $A$ so that ABC and ADE are SETs. Then $B$ must be in two sets; the options AB? and CB? can only be completed as ABC. The option BDE collides with ADE. Hence only BDF (or the symmetric case BEF) remains. Finally, $C$ must be in one more SET beyond ABC; the options AC? and BC? can only be completed by ABC itself; the option CDE collides with ADE, and the option CDF collides with BDF. Hence CD? is impossible, and only CEF remains. We summarize:

The four sets are ABC and ADE and BDF and CEF.

For the vectors, this means $A+B+C=0$ and $A+D+E=0$ and $B+D+F=0$ and $C+E+F=0$. Adding up these four equations and dividing by 2 yields $A+B+C+D+E+F=0$. Subtracting $A+B+C=0$ from this yields $D+E+F=0$, so that DEF is a feasible SET. But then DEF and ADE are both SETs, which implies $A=F$ so that the six cards/vectors are not pairwise distinct. Contradiction.

The maximum number of SETs that can be present in six distinct cards is 3.

• Why are 3 cards only a set if they add up to the zero-vector? Obviously that's true if they are different on all attributes, or if they're same with values '0', but shouldn't there be sets that sum (3,3,3,0) for example? – DrunkWolf Feb 23 '16 at 11:31
• @DrunkWolf we're working in $\mathbb{Z}/3$. $0 === 3$ – John Dvorak Feb 23 '16 at 11:40
• @Gamow this problem has been asked on math.stackexchange. Since this is the accepted answer, would you be willing to add it to math.stackexchange, as well? Here is the link – InterstellarProbe Jan 20 at 16:28

There can be at most three sets.

A more intuitive proof that does not rely on any higher math:

The key is that for any given two cards, there is exactly one third card that completes the set. Beginning with the simple construction of three sets as @Gamow did, we have:

A, B, C as unique cards, and find the unique cards X, Y, Z such that ABX, ACY, and BCZ are each sets. We now have three sets in six cards.

Now, imagine that there exists a fourth set. We know that it cannot contain any two cards that are both in one of our existing sets, since then it would have to also contain the same third card per the bolded statement above. We can therefore combine X with C, Y, Z; Y with B, X, Z; and Z with A, X, Y. The only three-card set that could follow this rule is X, Y, Z. Notably, A, B, C is NOT a set.

Since A, B, C is not a set, pick an attribute that causes them to not be a set. In this attribute, two of these cards are the same and one is different - assume A and B are the same. In this case, AC and BC contain the same two options in this attribute, which means that since they both form sets with Y and Z respectively, then Y and Z must be the same in this attribute as well. However, AB is different and forms a set with X, so X must be different from Y and Z in this attribute. But then X, Y, Z contains two cards which are the same and one which is different in an attribute - therefore, X, Y, Z cannot be a set. Since that was the only possible option, there can be no other sets.

• Thanks, that was insightful and easy to follow. I was too lazy to follow all steps of Gamow's proof. – Oliphaunt - reinstate Monica Feb 23 '16 at 10:53

TL;DR:

$$3$$ is possible and easy to attain; $$4$$ or more is not possible, so $$3$$ is the maximum.

With $$6$$ unique cards, it's possible to make $${6\choose3} = 20$$ different combinations of $$3$$ cards. But not all of those are valid Sets.

With cards $$A, B, C, D, E, F$$ we can make the following combinations of three cards.

$$\begin{array}{llll} ABC & ACE & BCD & BEF \\ ABD & ACF & BCE & CDE \\ ABE & ADE & BCF & CDF \\ ABF & ADF & BDE & CEF \\ ACD & AEF & BDF & DEF \\ \end{array}$$

Since any two cards define a single, unique third card to complete a valid Set, once we pick a combination as a valid Set, all other combinations that contain any two of the cards in that Set can't be a valid Set itself.
So if $$ABC$$ is a valid Set, we can cross off all combinations containing either $$AB$$, $$BC$$, or $$CA$$.

$$\require{cancel}\begin{array}{llll} \fbox{ABC} & \cancel{ACE} & \cancel{BCD} & BEF \\ \cancel{ABD} & \cancel{ACF} & \cancel{BCE} & CDE \\ \cancel{ABE} & ADE & \cancel{BCF} & CDF \\ \cancel{ABF} & ADF & BDE & CEF \\ \cancel{ACD} & AEF & BDF & DEF \\ \end{array}$$

Now if $$DEF$$ was a valid Set, those two would be the only valid Sets among those combinations, since we would need to cross off all combinations containing $$DE$$, $$EF$$, or $$FD$$ as invalid. But we're looking for more Sets, so $$DEF$$ should not be a valid Set.

Picking Sets and crossing off, we can come up with a maximum of four combinations that might be valid Sets.

$$\require{cancel}\begin{array}{llll} \fbox{ABC} & \cancel{ACE} & \cancel{BCD} & \cancel{BEF} \\ \cancel{ABD} & \cancel{ACF} & \cancel{BCE} & \cancel{CDE} \\ \cancel{ABE} & \fbox{ADE} & \cancel{BCF} & \cancel{CDF} \\ \cancel{ABF} & \cancel{ADF} & \cancel{BDE} & \fbox{CEF} \\ \cancel{ACD} & \cancel{AEF} & \fbox{BDF} & \cancel{DEF} \\ \end{array}$$

Our candidates are $$ABC, ADE, BDF, CEF$$. All other possible combinations of four candidates are variants of this.

Now that we have our Set candidates, let's check if they can actually be valid Sets.

If we pick any of the four properties, it can have three possible values: $$x, y, z$$. It can either have the same value for all three cards, or all different values. Let's explore what that means for the other candidate Sets.

$$\require{cancel} \begin{array}{llll} ABC & ADE & BDF & CEF \\ \hline xxx & xxx & xxx & xxx \\ xxx & xyz & xyz & \cancel{xzz} \\ xyz & xyz & yyy & \cancel{zzy} \\ xyz & xzy & yzx & zyx \\ \end{array}$$

From this we see that the only valid Sets can occur if and only if a property has the same value on cards $$A$$ and $$F$$, on cards $$B$$ and $$E$$, and on cards $$C$$ and $$D$$. Since this has to hold for all properties, this means the cards in these pairs are the same card, so $$A = F$$, $$B = E$$, and $$C = D$$. But we specified we wanted unique cards, so this leaves us with an impossible solution.

Since it's relatively easy to find a solution with three valid Sets — pick three cards $$A$$, $$B$$ and $$C$$ that are not a Set, then for all combinations of two of those cards, add the card that makes it a Set, so you have Sets $$ABD$$, $$BCE$$ and $$ACF$$$$3$$ is the maximum of valid Sets for three unique cards.

$$\begin{array}{c|cccc|ccc} \text{card} & \text{number} & \text{shape} & \text{colour} & \text{fill} & \text{Set #1} & \text{Set #2} & \text{Set #3} \\ \hline A & 1 & \text{oval} & \text{red} & \text{solid} & \checkmark & & \checkmark \\ B & 1 & \text{oval} & \text{green} & \text{striped} & \checkmark & \checkmark & \\ C & 2 & \text{oval} & \text{purple} & \text{solid} & & \checkmark & \checkmark \\ D & 1 & \text{oval} & \text{purple} & \text{open} & \checkmark & & \\ E & 3 & \text{oval} & \text{red} & \text{open} & & \checkmark & \\ F & 3 & \text{oval} & \text{green} & \text{solid} & & & \checkmark \\ \end{array}$$