Problem of the Month
Solution to Problem 5: SET!

1. The six sets are:

   

   Hide/Reveal Description of Sets for #1
   • 3 red open squiggles, 1 red striped diamond, and 2 red solid ovals
   • 3 red open squiggles, 1 red solid oval, and 2 red striped diamonds
   • 1 purple striped diamond, 3 red solid squiggles, and 2 green open ovals
   • 2 red open squiggles, 2 red solid ovals, and 2 red striped diamonds
   • 2 red solid ovals, 2 green open ovals, and 2 purple striped ovals
   • 2 purple striped ovals, 2 green striped squiggles, and 2 red striped diamonds

   ---

   Going by the labels in the statement of the problem, the six sets are $$\{A,B,E\},\{A,F,L\},\{C,G,I\},\{D,E,L\},\{E,I,J\},\{J,K,L\}.$$

2. Since each property has three options, and there are four properties, there are $$3\times 3\times 3\times 3=81$$ cards in a SET! deck.

For the next two questions, we first make the following observation: Given any two cards $A$ and $B$, there is a unique third card $C$ so that the three cards $A$, $B$, and $C$ form a set. Let’s see why this is true.

For each property, if the options on $A$ and $B$ are the same, then the option for that property on card $C$ must also be the same as it is for $A$ and $B$. If the options are not the same for $A$ and $B$, then $C$ must have the third option for that property.

For example, if $A$ and $B$ are both shaded solid, then $C$ must be shaded solid. On the other hand, if the shading of $A$ is striped and the shading of $B$ is solid, then the shading of $C$ must be open.

3. With the observation above in mind, to create a set that contains the given card, we just have to choose any other card. Then the given card with our choice of second card uniquely determines a third card that forms a set.

   There are $80$ choices for a second card. However this counts every set twice! To see why, call the card we are given in the question $A$. Suppose we choose a card $B$, and the unique third card that forms a set is $C$. If instead we choose $C$ as the second card, then $B$ is the unique card that forms a set with $A$ and $C$. So choosing $B$ as the second card results in the same set as choosing $C$ as the second card.

   Therefore the answer is $\frac{80}{2}=40$.

4. Solution 1: We again rely on the observation above that once we have chosen two cards as part of a set, the third is determined.

   There are 81 ways to choose the first card in our set, and 80 ways to choose the second. However, since there are $3!=6$ ways to order the three cards in a set, the number $81\times 80$ counts each set six times. Therefore the number of different sets in a SET! deck is $\frac{81\times 80}{6}=1080$.
   
   Solution 2: Using Question $3$, we know each card appears in $40$ sets. Since there are $81$ cards in a full deck, and $3$ cards in a set, there are $\frac{40\times 81}{3}=1080$ sets in a SET! deck.

5. For this question, we will need to introduce a different way of thinking about the cards. We can encode each card by a $4$-tuple $(q,r,s,t)$, where each entry $q,r,s,t$ is either $1$, $2$, or $3$ as in the following table:

   Entry in the $4$-tuple	Number	Shading	Colour	Shape
   $1$	$1$	open	red	diamond
   $2$	$2$	striped	green	oval
   $3$	$3$	solid	purple	squiggle

   For example, consider the cards from one of the sets from Problem 1 above:

   

   These cards are encoded by the tuples $(3,1,1,3)$, $(1,2,1,1)$, and $(2,3,1,2)$ respectively.

   Let’s think about what it takes for three $4$-tuples to form a set. Each coordinate in the tuple (ie, the first, second, third, or fourth entry) corresponds to one of the properties (number, shading, colour, and shape, in that order).

   The condition that a property has the same option across the three cards translates to the entry in the corresponding coordinate being the same across all three $4$-tuples. In the example above, all three cards are red. Therefore, the entries in the third coordinates of all three $4$-tuples are $1$.

   The condition that a property has all different options across the three cards translates to each of $1$, $2$, and $3$ appearing in the corresponding coordinate in the three $4$-tuples. In the example above, all three cards have different shadings. Therefore, the entries $1$, $2$, and $3$ appear in some order in the second coordinates of the three $4$-tuples.

   Our goal now is to characterise exactly when a collection of three numbers $\{a,b,c\}$ is either $\{1,1,1\}$, $\{2,2,2\}$, $\{3,3,3\}$, or $\{1,2,3\}$. Note that in the last case, $a,b,c$ must be equal to $1,2,3$ in some order (not necessarily $a=1$, $b=2$, and $c=3$).
   
   Suppose $a,b,c$ are three integers, each of which is either $1$, $2$, or $3$. Then $a+b+c$ is a multiple of three exactly when either $a=b=c$ or $a$, $b$, and $c$ are all distinct.
   
   Let’s justify this claim. First, if $a=b=c$ then $a+b+c$ is equal to $3$, $6$, or $9$. If $a$, $b$, and $c$ are distinct, then $a$, $b$, and $c$ are $1$, $2$, and $3$ in some order. Therefore, $a+b+c=1+2+3=6$. Now suppose it is not true that all three of $a$, $b$, and $c$ are equal or distinct. That means two of the numbers are equal, and one is not. We can check the sum $a+b+c$ in each of these cases. $$\begin{array}{rl}1+1+2& =4\\ 1+1+3& =5\\ 2+2+1& =5\\ 2+2+3& =7\\ 3+3+1& =7\\ 3+3+2& =8.\end{array}$$ In all of these cases, the sum $a+b+c$ is not a multiple of $3$, so the claim is true!

   Great! Let’s harness this by adding up coordinates among tuples to check whether or not three $4$-tuples come from cards that form a set.

   To make our lives a little easier, given two $4$-tuples, let’s add them together to create another $4$-tuple by simply adding up the coordinates. More precisely, given two $4$-tuples $\mathbf{\text{v}}=(a,b,c,d)$ and $\mathbf{\text{w}}=(p,q,r,s)$, we define $$\mathbf{\text{v}}+\mathbf{\text{w}}=(a+p,b+q,c+r,d+s).$$ If you have experience with vectors, you may recognise that this is exactly how we add two vectors together. Using this definition of addition for $4$-tuples, we can repeatedly add as many $4$-tuples together as we like!

   In particular, given three $4$-tuples we can add them together to get another $4$-tuple. The resulting $4$-tuple may include entries other than $1$, $2$, and $3$, but that’s okay! By using the claim above, we know that the three $4$-tuples correspond to three cards that form a set exactly when the $4$-tuple resulting from adding them together has the property that every entry is a multiple of $3$. Check for yourself that this works for the example set at the beginning of the solution to Problem $5$.

   More precisely, suppose $\mathbf{\text{v}}$, $\mathbf{\text{w}}$, and $\mathbf{\text{u}}$ are three $4$-tuples corresponding to SET! cards. Then $\mathbf{\text{v}}+\mathbf{\text{w}}+\mathbf{\text{u}}$ has every coordinate a multiple of $3$ exactly when the cards corresponding to $\mathbf{\text{v}}$, $\mathbf{\text{w}}$, and $\mathbf{\text{u}}$ form a set. Choose your favourite set, and your favourite non-set, and check this for yourself!

   We are now ready to attack the original question. First convert the $81$ cards in a SET! deck into $4$-tuples. For each coordinate, the integers $1$, $2$, and $3$ appear exactly $27$ times each (this is because once the entry in a coordinate has been fixed, there are three different options for each of the remaining three coordinates, and $3\times 3\times 3=27$). Therefore, for each coordinate, the sum over all $81$ entries in that coordinate is $27\times 1+27\times 2+27\times 3=162$, which is a multiple of $3$.

   Considering the question at hand, we have collected $26$ sets from a full SET! deck. We want to show that the remaining three cards also form a set. Let ${\mathbf{\text{w}}}_1,{\mathbf{\text{w}}}_2,{\mathbf{\text{w}}}_3$ be the three $4$-tuples corresponding to the remaining three cards. For the $78$ cards used in the $26$ sets, label the $78$ $4$-tuples ${\mathbf{\text{v}}}_1,{\mathbf{\text{v}}}_2,\dots ,{\mathbf{\text{v}}}_{78}$ so that for every positive integer $k\le 26$, ${\mathbf{\text{v}}}_{3k-2},{\mathbf{\text{v}}}_{3k-1}$, and ${\mathbf{\text{v}}}_{3k}$ form a set (ie, ${\mathbf{\text{v}}}_1,{\mathbf{\text{v}}}_2,{\mathbf{\text{v}}}_3$ form a set, ${\mathbf{\text{v}}}_4,{\mathbf{\text{v}}}_5,{\mathbf{\text{v}}}_6$ form a set and so on).

   Then we know that for every positive integer $k\le 26$, ${\mathbf{\text{v}}}_{3k-2}+{\mathbf{\text{v}}}_{3k-1}+{\mathbf{\text{v}}}_{3k}$ is a $4$-tuple where every coordinate is a multiple of $3$. Summing up all of the resulting $4$-tuples gives us that $${\mathbf{\text{v}}}_1+{\mathbf{\text{v}}}_2+\cdots +{\mathbf{\text{v}}}_{78}=(a,b,c,d)$$ where $a,b,c,d$ are all multiples of $3$. We also know $${\mathbf{\text{v}}}_1+{\mathbf{\text{v}}}_2+\cdots +{\mathbf{\text{v}}}_{78}+{\mathbf{\text{w}}}_1+{\mathbf{\text{w}}}_2+{\mathbf{\text{w}}}_3=(162,162,162,162).$$ We can now conclude that $${\mathbf{\text{w}}}_1+{\mathbf{\text{w}}}_2+{\mathbf{\text{w}}}_3=(162-a,162-b,162-c,162-d).$$ All of $162$, $a$, $b$, $c$, and $d$ are all multiples of $3$. Therefore, $162-a$, $162-b$, $162-c$, and $162-d$ are multiples of $3$. We can finally conclude that ${\mathbf{\text{w}}}_1,{\mathbf{\text{w}}}_2,$ and ${\mathbf{\text{w}}}_3$ are $4$-tuples corresponding to three cards that form a set.