A Simple Set Stumper

The card game Set has 81 unique cards with 4 different attributes: color (red, green or purple), fill (unfilled, striped, or filled), number (one, two, or three), and shape (diamond, squiggle, or oval). A set consists of three cards where each of the attributes must be either all the same, or all different. For example, the below three cards are a set because they're all red (color), all have two shapes (number), all are ovals (shape), and all have different fills.

After players have found all the sets in a game, there are usually some cards left over that have no sets in them. I've played games where there are 0, 6, 9, or 12 cards left after sets have been found. However, I've never played a game where there are exactly 3 cards left over. Is having three cards left over possible? If so, prove it, and if not, find a counterexample.

This is

not possible.

To see this most clearly,

label each of the possible values of each attribute (arbitrarily) as $$1,2$$ and $$3$$. Now, the crucial observation is that a collection of three cards will be all different or all the same in this attribute if and only if the sum of the labels is divisible by $$3$$ (!).

Secondly,

since the whole deck contains every possible arrangement of values, the sum of all the cards is also divisible by three in each attribute (being $$27\times 6$$). Thus, when only three cards remain, their sum in each attribute will still be a multiple of three, and so they must form a set.

Note that the same argument shows that any leftover pile has a sum of $$0$$ mod $$3$$ in every attribute. But this is of no consequence for the existence of sets in it unless it is only three cards (or large enough, I don't know how large though).

• Exactly my solution! Nicely done :) Commented Jun 2 at 16:36
• The largest possible number of cards left over is fifteen, achieved by choosing two characteristics for each of the four attributes and taking any fifteen of the sixteen cards that have one of those two attributes for each characteristic. Commented Jun 5 at 21:14
• @isaacg That is interesting, but I don't quite follow - is it easy to see that the complement of these is a collection of sets? And is it somehow clear that any pile of size 18 is impossible? (Note that there are some collections of 20 cards without a set, but I don't know if 18 of them can be the leftover pile) Commented Jun 6 at 9:15
• @TimSeifert Sorry, I should've said "At least 15", I don't know an upper bound. This might be better suited to another question, I was just speaking off the cuff. Commented Jun 6 at 14:50