Mathematics 357 – Combinatorics Discussion 1 – The Game of Set January 21, 2005

Background and Goals

Recall that last time we introduced the idea of the card game called Set, which is played with a deck of 81 cards, one with each possible combination of four attributes:

• A number: 1, 2, or 3

• A shape: oval, diamond, or “squiggle”

• A color: red, green, or purple

• A shading: open, shaded, solid

As we saw last time, if we make some (any) associations of the numbers, shapes, colors, and shadings with the set {0, 1, 2}, then we can think of the deck of cards as represented by the set {0, 1, 2}^{4} of ordered 4-tuples (a_{1}, a_{2}, a_{3}, a_{4}), where a_{1} ∈ {0, 1, 2} gives the number, a_{2} the shape, etc.

A “set” in the terminology of the game is a collection of exactly three cards that has the property that with respect to each of the four attributes, the three cards are either all the same, or else all different. We will always use the quotation marks to distinguish “sets” in this sense from sets in the more general mathematical sense.

In today’s discussion, we want to take this setup from the game of Set and look at a sampling of different types of combinatorial questions that one might ask concerning the Set deck and the special arrangements of cards called “sets”.

A) Some “warmup” enumeration questions.

1) Let 1 denote the set of all cards showing number 1, let Red denote the set of all redcolored cards, and let Squiggle denote the set of all “squiggle”-shaped cards. Say in words what the following sets represent, and find the number of cards in each:

A = 1, B = 1 ∩ Red, C = Squiggle − Red, D = (1 ∩ Squiggle) ∪ Red,

(C is the set difference).

B) One of the interesting things about combinatorics is the way an algebraic structure often underlays the arrangements in a combinatorial problem. (This is one reason why MATH 357 satisfies the Algebra breadth area for Mathematics majors!). We will pick and fix an identification of the Set deck of 81 cards with the set {0, 1, 2}^{4} as discussed last time. What algebraic operations can you do with the elements of {0, 1, 2}? (Think about ideas you learned in Algebraic Structures.) What is always true about the vector sum of the three four-tuples corresponding to the three cards in a “set”? Prove your assertion.

C) Use your answer to B to answer the following additional enumeration questions, and justify your reasoning with a complete explanation. (Note: These can also be done by “brute force” if necessary, and that’s a good check on your answers. But you should find that using question B makes these much easier!)

1) Given any two distinct cards in the deck, how many “sets” contain both of them?

2) How many “sets” are there in the deck that contain a single, given card? (Hint: the answer is the same for all cards, but you’ll need to be careful in counting so that you don’t end up counting the same “set” more than once.)

3) How many “sets” are there in the entire deck?

D) Other combinatorial questions deal with the existence of certain arrangements. Here’s a question of this type. In the play of the game, is it possible that the 12 cards dealt contain no “sets” at all? Find such a set of 12 cards, or say why none exists.

E) On the other hand, it’s possible for 12 cards to contain lots of “sets”. Try to find some 12 cards containing more than 12 “sets”. What’s the largest number of “sets” you can find in some collection of 12 cards? (Hint: Suppose you had lots of cards with the same two attributes, for instance lots of solid red cards. Don’t worry about whether this kind of hand is likely to be dealt or not.)

Assignment

Group writeups due Wednesday, January 26.