In a version of the game of set, cards with shapes on them are dealt out and each has four characteristics:

Type of shape (Circle, Square, or Triangle)
Color of the shape (Red, Blue, or green)
Fill type (Empty, Half filled, or Completely filled)
Number of the shape on the card (1, 2 or 3)

A "set" is defined as a three card subgroup of the cards "in play" such that for each of these four individual characteristics are either all the same, or all different. (The cards could be all different on one characteristic and be same on another.)

What is the greatest number of different cards that can be "in play" such that there is no subgroup that can be designated a "set"?

Edit:  I give up! The below brute force method might work, but it's just too hard to do for 4 characteristics.  BTW, I found that there are 3 non-equivalent groups of 8 cards for the 3 characteristic case.

I apologize for the below incomprehensible text.

I finally found my deck of Set cards, and it suddenly got me thinking of this puzzle here again.  My last attempts at a proof failed miserably, but I'm going to try again perhaps within a week or so.  Right now, I'm just thinking about the method I will use.

I'm going to stick with my 4-d tic-tac-toe analogy.  Though practically no one likely understands it, it helps me a lot.  I'll represent each card as a four digit tertiary number.  Each digit--a 0, 1, or 2--will represent one of the characteristics.  It doesn't matter which is which.  I'll be trying a bunch of set-free combinations, and some I'll call "equivalent."  I'll find all the non-equivalent (I suspect there aren't many) combinations and prove that they all use 16 or less cards.

To show what I mean by equivalent, I'll use an example.  Suppose there are only two characteristics.  There are nine types of cards, and they can be represented in a grid, each row representing a different color, each column representing a different shape.  The number in each space shows how many cards of that type.

1|2|3                  2|1|3        2|3|1
4|5|6 is equivalent to 5|4|6 and to 6|4|5
7|8|9                  8|7|9        7|8|9

Also, these are equivalent
1|1|0 0|0|0
1|1|0 1|0|1
0|0|0 0|1|1

Basically, by equivalent, I mean that they are the same except perhaps all red and green switched, or some other similar basic transformation (or several transformations at once).  Another example of an acceptable transformation is rotating clockwise the color of all cards with 1 symbol, and counter-clockwise the color of all the cards with 2 symbols.

So far, I've been able to prove that there are only five set-free non-equivalent combinations when there are only 3 characteristics.  Each combination has a different number of cards, 0-4.  I'm hoping 3 and 4 characteristics will be equally straightforward.

Edited on October 13, 2004, 2:23 am

Edited on October 24, 2004, 9:48 pm

Posted by Tristan on 2004-10-13 02:22:09