\magnification=\magstep1
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Discussion 1 -- The Game of Set}
\centerline{January 21, 2005}
\bigskip
\noindent
{\it Background and Goals}
\bigskip
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:
\bigskip
\item{$\bullet$} A {\it number}: 1, 2, or 3
\item{$\bullet$} A {\it shape}: oval, diamond, or ``squiggle''
\item{$\bullet$} A {\it color}: red, green, or purple
\item{$\bullet$} A {\it shading}: open, shaded, solid
\bigskip
\noindent
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 \in \{0,1,2\}$ gives the number, 
$a_2$ the shape, etc.

A ``set'' in the terminology of the game is a collection
of exactly {\it three cards} that has the property that
with respect to each of the four attributes, the three
cards are either {\it all the same}, or else {\it 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''.
\bigskip
\noindent
A)  Some ``warmup'' {\it enumeration} questions.
\item{1)}  Let {\bf 1} denote the set of all cards
showing number 1, let {\bf Red} denote the set
of all red-colored cards, and let {\bf 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 = {\bf 1}, \quad B = {\bf 1} \cap {\bf Red},\quad  C = {\bf Squiggle} - {\bf Red}, 
\quad D= ({\bf 1} \cap {\bf Squiggle}) \cup {\bf Red}, \quad
$$
($C$ is the {\it set difference}).
\bigskip
\noindent
B) One of the interesting things about combinatorics is the 
way an {\it 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 {\it vector sum} of the three four-tuples 
corresponding to the three cards in a ``set''?  Prove your assertion.
\bigskip
\noindent
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 
{\it much easier}!)
\item{1)}  Given any two distinct cards in the deck,
how many ``sets'' contain both of them?
\item{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.)
\item{3)}  How many ``sets'' are there in the entire deck?
\bigskip
\noindent
D)  Other combinatorial questions deal with the 
{\it 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 {\it no ``sets'' at all}?  Find
such a set of 12 cards, or say why none exists.
\bigskip
\noindent
E)  On the other hand, it's possible for 12 cards to contain
{\it 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. {\it Don't worry} about whether this kind
of hand is likely to be dealt or not.)
\bigskip
\noindent
{\it Assignment}
\bigskip
Group writeups due Wednesday, January 26.
\bye