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"?

This proof is wrong.  See above comment.

 

'm going to abandon the tic-tac-toe hyperdonut analogy for the sake of a more comprehensive proof.  The "Half a proof" comment helped me find this proof, but this is not the same proof.

First, I will assume no identical cards.

As Danny has already shown, there is a 16 card solution.  To get this solution, have all 81 cards, then eliminate all with triangles, green, completely filled or with 3.  16 are left with no sets.

To prove that 16 is the upper bound, I need to consider the number of possible sets that include any one card.  There are 15 sets that use each card.  Recall that a set can include any combination of two cards, and the third is determined by the first two.  So 15 possible sets use each card, and only one possible set will use a combination of two cards.

Say I have x cards on the table.  One might say that the number of sets that use at least one of the cards on the table is 15x, but one would be wrong to say so.  This is because some sets use two or three cards on the table, and are counted twice.  Let's assume that none of the sets have three of their cards on the table.  The number of sets with two cards on the table is xC2, for every pair of cards will form a set if you have the right third card.  So in truth, the number of sets that use at least one card on the table is 15x-xC2.

15x-xC2 forms a parabola that stops rising at 16 and then drops.  But it is not possible for it to drop, because adding more cards on the table should make it higher, or at least stay the same!  This inconsistency arises from our assumption that no set has all its cards on the table.  Therefore, there is no arrangement with more than 16 cards that has no complete sets.

Also, if identical cards are allowed, the answer is 32 rather than 16.  Every card would have a single twin on the table, and more would create sets.

Edited on May 15, 2004, 10:56 am

Posted by Tristan on 2004-05-14 17:08:37