🚀 go-pugleaf

Excerpts from netnews.rec.puzzles: 10-Jan-93 A question on the game
"SET" Mark Kobayashi@hpindda.c (696)

> I thought someone here might know the answer....

> I bought the card game "SET" (matching off 3 cards at a time with
> similar or unique combinations).

> My question - what is the maximum number of cards which can 
> be put down which would not contain any "set"? (or, what
> number of cards would guarantee at least 1 set?)

Ha -- I just subscribed to rec.puzzles for the sole purpose of asking
that question :-)

Since you seem to have left out the game rules, let me do so:

Each card shows a figure. The figure has N independent attributes; each
attribute has 3 possible values. So there are 3^N possible cards. The
deck contains exactly one of each.

In the deck sold, N=4, so there are 81 cards. The attributes are 
	shape (diamond / oval / squiggle)
	shade (solid / striped / hollow)
	color (red / green / blue)
	number (one copy / two copies / three copies)

Three cards form a "set" if: 
For every attribute, either all three cards' values match, or the three
cards' values are all different.

So, for the standard deck (N=4):
 (one solid red diamond)  (two solid red diamond)  (three solid red
diamond) is a set.
So is (one solid blue diamond)  (two solid green diamond)  (three solid
red diamond)
And (one hollow blue diamond)  (two striped green oval)  (three solid
red squiggle)
Three identical cards would form a set, except that there is only one of
each card in the deck.
But  (one solid blue oval)  (two solid green diamond)  (three solid red
diamond) is not a set; it fails for the attribute of shape. 

Again, the question is: what is the maximum number of cards you can lay
out without any three of them forming a set?

I've thought about this for a few days now. My first guess was 2^N, but
that's wrong; I found arrangements of 9 cards with no set in the N=3
case, and 18 cards for N=4.

Bonus question (easier, I have an answer and proof): How does the answer
change if you allow repeated cards?

BTW, it's a very cool game, and only costs $10 or $12. The game is just
laying out cards and trying to find sets as fast as possible.

--Z