Jim Boyce

Hi,

Any collection of 10 cards contains a Superset, and there is a

collection of 9 cards that does not have a Superset.

A superset is a collection of 4 cards that are left if you take two Sets

that share a common card and remove that common card. (I will give

another characterization later.) This gives a trivial upper bound, that

14 cards must contain a Superset. Each pair of cards (there are 91

pairs) defines a third card that completes its Set. there are only 81

cards, so there are pairs that share the same "completer". The pairs
do

not overlap, beacuse then they would be identical. So two paris witht e

same "completer" form a Superset.

The second characterization of a Superset requires some more machinery.

Put some reasonable coordinate systems on the cards, so that you can

take the difference between two cards to get a direction (and

distance). Suppose you have two (disjoint) pairs of cards and their

differences are the same. Then these four cards form a parallelogram.

There are also a Superset. The diagonals of a parallelogram intersect

at another card.

There are 40 (unsigned) directions for lines. With 10 cards, there are

45 pairs of cards. Each pair of cards has a difference which is one of

those 40 directions. If there are 2 disjoint pairs with the same

difference, then we have a Superset. We see that there are pairs with

the same difference. If they overlap, then they are a Set, and that

direction is used 3 times. If the 10 cards consists of 3 Sets and

another card, then the 3 sets account for 3 directions 3 times each, and

there are still 36 pairs which might be distributed over the remaining

37 directions without overlap.

However, it turns out that while you can find 3 Sets that do not contain

a Superset, there is no room for the 10th card.

Here is a diagram of a 9-card collection with no Superset:

xxx ooo ooo

ooo ooo ooo

ooo ooo ooo

xoo ooo ooo

xoo ooo ooo

xoo ooo ooo

ooo xoo ooo

ooo oxo ooo

ooo oox ooo

-jim

----------------------------------------

Dear Ed,

I'm writing to you about SET. In the January 2000

installment of my Mindsharpener column for Optima, the

newsletter of the Mathematical Programming Society, I

described how integer programming can be used to find

a largest `Set'less collection of SET cards. The idea

of formulating the problem as an integer program (IP)

is due to Mohan Rajagopolan, who was at the time a

student at Oberlin College (he is now a Ph.D. student

at Cornell). Some crucial ideas that led to the

solution of Mohan's IP were contributed by me (Bob Bosch),

Oliver Schirokauer (also a member of Oberlin's Math Dept.)

and Carl Cotner (of Penn State). I believe that our

integer-programming based proof was the first published

proof that the maximum number is 20. (The SET site

presents a collection of 20, but does not present a

complete proof; it does provide a link to David Van Brink's

site, which contains what may be the beginnings of a valid

proof.) My Optima article is available online at

http://www.ise.ufl.edu/~optima/ (see Optima 63, pages 2-3).

Also, about a year ago, Mohan e-mailed me to tell me

that Joseph S. Miller, a graduate student at Cornell,

had found a nice combinatorial proof.

Best regards,

Bob