What is the size of the largest collection of cards from which NO "set" can be selected ?
competition/games/set Added material
Problem
What is the size of the largest collection of cards from which NO "set" can be selected ?
Show solution
I can get 20:
1ROL
1GDL
1GDM
1GOM
1GSL
1PDH
1PDM
1POL
1POM
2RSL
2PDM
3ROL
3ROM
3RSL
3RSH
3GDM
3GOL
3GSL
3GSM
3POM
This collection of 20 is a local maximum.
The small C progam shown below was used to check for all possible
extensions to a collection of 21.
Of course this leaves open the question whether there exists a completely
different collection of 21 from which no "set" can be selected.
-- Gene Miller
------- C Program enclosed -------
#define N 21
static int data[N][4]= {
1, 1, 2, 1, /* 00 */
1, 2, 1, 1, /* 01 */
1, 2, 1, 2, /* 02 */
1, 2, 2, 2, /* 03 */
1, 2, 3, 1, /* 04 */
1, 3, 1, 3, /* 05 */
1, 3, 1, 2, /* 06 */
1, 3, 2, 1, /* 07 */
1, 3, 2, 2, /* 08 */
2, 1, 3, 1, /* 09 */
2, 3, 1, 2, /* 10 */
3, 1, 2, 1, /* 11 */
3, 1, 2, 2, /* 12 */
3, 1, 3, 1, /* 13 */
3, 1, 3, 3, /* 14 */
3, 2, 1, 2, /* 15 */
3, 2, 2, 1, /* 16 */
3, 2, 3, 1, /* 17 */
3, 2, 3, 2, /* 18 */
3, 3, 2, 2, /* 19 */
0, 0, 0, 0 /* 20 */ /* leave space for Nth combo */
};
main()
{
int x, y, z, w;
for (x=1; x<=3; x++) /* check all combos */
for (y=1; y<=3; y++)
for (z=1; z<=3; z++)
for (w=1; w<=3; w++)
printf ("%d %d %d %d -> sets=%d\n", x, y, z, w,
check (x, y, z, w));
}
int check(x,y,z,w)
int x, y, z, w;
{
int i,j,k,m;
int errors, sets;
for (i=0; i<N; i++) /* check for pre-existing combos */
if (x==data[i][0] &&
y==data[i][1] &&
z==data[i][2] &&
w==data[i][3] ) {
return -1; /* discard pre-existing*/
}
data[N-1][0] = x; /* make this the Nth combo */
data[N-1][1] = y;
data[N-1][2] = z;
data[N-1][3] = w;
sets = 0; /* start counting sets */
for (i=0; i<N; i++) /* look for sets */
for (j=i+1; j<N; j++)
for (k=j+1; k<N; k++) {
errors = 0;
for (m=0; m<4; m++) {
if (data[i][m] == data[j][m]) {
if (data[k][m] != data[i][m]) errors++;
if (data[k][m] != data[j][m]) errors++;
}
else {
if (data[k][m] == data[i][m]) errors++;
if (data[k][m] == data[j][m]) errors++;
}
}
if (errors == 0) /* no errors means is a set */
sets++; /* increment number of sets */
}
return sets;
}
--
I did some more experimenting. With the enclosed C program, I looked at many
randomly generated collections. In an earlier version of this program I
got one collection of 20 from a series of 100 trials. The rest were collections
ranging in size from 16 to 19. Unfortunately, in an attempt to make this
program more readable and more general, I changed the algorithm slightly and
I haven't been able to achieve 20 since then. I can't remember enough about
my changes to be able to get back to the previous version. In the most recent
1000 trials all of the maximaml collections range in size from 16 to 18.
I think that this experiment has shed very little light on what is the
global maximum, since the search space is many orders of magnitude larger
than what can be tried in a reasonable amount of time through random
searching.
I assume that Mr. Ring found his collection of 20 by hand. This indicates
that an intelligent search may be more fruitful than a purely random one.
------------------ Program enclosed -------------
int n;
int data[81][4];
main()
{
int i;
for (i=0; i<1000; i++) { /* Do 1000 independent trials */
printf ("Trial %d:\n", i);
try();
}
}
try()
{
int i;
int x, y, z, w;
n = 0; /* set collection size to zero */
for (i=0; i<100; i++) { /* try 100 random combos */
x = 1 + rand()%3;
y = 1 + rand()%3;
z = 1 + rand()%3;
w = 1 + rand()%3;
check (x, y, z, w);
}
for (x=1; x<=3; x++) /* check all combos */
for (y=1; y<=3; y++)
for (z=1; z<=3; z++)
for (w=1; w<=3; w++)
check (x, y, z, w);
printf (" collection size=%d\n", n);
}
int check(x, y, z, w) /* check whether a new combo can be added */
int x, y, z, w;
{
int i,j,k,m;
int errors, sets;
for (i=0; i<n; i++) /* check for pre-existing combos */
if (x==data[i][0] &&
y==data[i][1] &&
z==data[i][2] &&
w==data[i][3] ) {
return -1; /* discard pre-existing*/
}
data[n][0] = x; /* make this the nth combo */
data[n][1] = y;
data[n][2] = z;
data[n][3] = w;
sets = 0; /* start counting sets */
for (i=0; i<=n; i++) /* look for sets */
for (j=i+1; j<=n; j++)
for (k=j+1; k<=n; k++) {
errors = 0;
for (m=0; m<4; m++) {
if (data[i][m] == data[j][m]) {
if (data[k][m] != data[i][m]) errors++;
if (data[k][m] != data[j][m]) errors++;
}
else {
if (data[k][m] == data[i][m]) errors++;
if (data[k][m] == data[j][m]) errors++;
}
}
if (errors == 0) /* no errors means is a set */
sets++; /* increment number of sets */
}
if (sets == 0) {
n++; /* increment collection size */
printf ("%d %d %d %d\n", x, y, z, w);
}
return sets;
}
------------------ end of enclosed program -------------
-- Gene
--
Gene Miller Multimedia Communications
NYNEX Science & Technology Phone: 914 644 2834
500 Westchester Avenue Fax: 914 997 2997, 914 644 2260
White Plains, NY 10604 Email: gene@nynexst.com
From: Douglas Zare (NC) <zare@virtu.sar.usf.edu>
I cannot remember exactly what I have said before, but I think I
mentioned that I have been working on a game called Set. It turns out
that the game (although listed as "ages 6+") is equivalent to recognizing
lines in affine 4-space over Z3. A friend of mine introduced me to this
game this summer, and I have been corresponding with her advisor. The
main problem we have been looking at is the maximum size of sets of
points which contain no lines.
The following is an abridged transcript of the dialog we have had:
Date: Thu, 7 Jul 1994 20:27:01 -0400 (EDT)
From: "Douglas Zare (NC)" <zare@virtu.sar.usf.edu>
To: smith_k@mth15.mth.cmich.edu
Subject: Set
Hello, I am a co-worker of Lynn's and I have also been working on the
Set problem. I have been able to show that the maximum number of points one
can choose from A4(Z3) without containing a line is 20. A proof which is
still one of exhaustion for reader, writer, and technique is given below.
My undergraduate thesis was essentially a geometric study of block
designs with \l = 1, but I am unfamiliar with this type of problem in
general. At the end of this message, I have selected a few questions
which were stimulated by Set. I hope that you can answer these, but if
not, they might be good places for future research.
Definition: A collection of points is lineless if it does not contain
any line.
Claim: No set of 21 points in A4(Z3) is lineless.
Proof: First, the following lemmas are useful. Their proofs are
elementary, so I will only state them.
Lemma 1: The largest possible size of a lineless set in A2(Z3) is 4.
Lemma 2: Given a lineless set of 4 points in A2(Z3), there is an
automorphism of A2(Z3) which sends the points to xxo
xxo
ooo
Lemma 3: Given at least 6 points in A3(Z3), there is a plane which
contains at least 4 of them.
Definition: A lineless set of 4 points in a plane has type 4ab (a,b in
{H,V,D,D'}) if there are two pairs of points in the "a" direction
and two pairs of points in the "b" direction. For example, the set of
points written above is of type 4HV.
Lemma 4: Given 4 points in the (0,*,*) plane of A3(Z3) and
X1 points in the (1,*,*) plane, there are at most X2 points which
can be added in the (2,*,*) plane to form a lineless set, where X1
and X2 are related by the following table:
X1 0 1 2 3 4
X2 4 4 2 1 1
Further, the partition (4,4,1) implies that the 4's are of type 4ab
and 4cd such that {a,b}U{c,d} = {H,V,D,D'}.
Cor 1 to Lemma 4: All lineless sets of 9 points in A3(Z3) are isomorphic
to xxo oox ooo
xxo oox ooo
ooo xxo oox.
Cor 2 to Lemma 4: If a lineless set of points has 4 points in the (0,*,*)
plane of A3(Z3) but at most 3 points apiece in the (1,*,*) and (2,*,*)
planes, then there are at most 8 points in the set.
Now we have enough tools to make the summary of the proof reasonably
short.
Suppose that there exists a lineless set of 21 points in A4(Z3).
By the pigeonhole principle and Lemma 3, there must be some plane of
A4(Z3) which contains 4 points of the set. By Lemma 2, without loss of
generality we can assume that the (0,0,*,*) plane has the following 4
points: xxo
xxo
ooo.
Consider the planes of A4(Z3) which are of the form (i,j,*,*). At
most 4 of these can contain 4 points of the set. If there were at least
5, then the set of (i,j)'s would not be lineless and there would be a
lineless set of 12 points in some 3-flat of A4(Z3). Thus we need only
consider the cases of 1, 2, 3, or 4 of these planes containing 4 points.
Case 1: Let us count the number of points in the planes (i,j,*,*).
Without loss of generality, these are 4 a1 b1
a2 a3 a4
b2 b4 b3.
By assumption, ai<4 and bi<4. Thus, by Cor 2 to Lemma 4, ai + bi <= 4.
Thus, the total number of points in the set is at most
4 + (a1+b1) + (a2+b2) + (a3+b3) + (a4+b4) <= 20, which is a
contradiction.
Case 4: By Lemma 2, we can rearrange the planes which contain 4 points so
that they are (i,j,*,*) for i,j in {0,1}. Without loss of generality, the
numbers of points in each plane of the form (i,j,*,*) are 4 4 a1
4 4 a2
a3 a4 a5.
By Lemma 4, ai <= 1. Thus the only case we need to consider is when ai=1
for all i. Consider the types of the sets of 4 points in (0,0,*,*),
(0,1,*,*), and (1,0,*,*). By Cor 1 of Lemma 4, (0,0,*,*) must have
complementary type to (0,1,*,*). Similarly, (0,0,*,*) and (1,0,*,*) must
be of opposite type. Then (1,0,*,*) and (0,1,*,*) must be of the same
type, so a5 = 0, which is a contradiction.
Case 3: We can rearrange the planes so that, without loss of generality,
the numbers of points in each plane of the form (i,j,*,*) are 4 4 a1
4 b1 b2
a3 b3 a5.
By the reasoning in Case 4, a1 + a3 + a5 <= 2. By Cor 2 of Lemma 4,
b1 + b2 <= 4
b2 + b3 <= 4
b1 + b3 <= 4
Thus, b1 + b2 + b3 <= 6, so the total number of points in the plane is at
most 20, which is a contradiction.
Case 2: We can rearrange the planes so that, without loss of generality,
the numbers of points in each plane of the form (i,j,*,*) are 4 a1 b1
4 a2 b2
c1 a3 b3.
By Lemma 4,
c1 <= 1
a1 + b1 <= 4
a1 + b3 <= 4
a2 + b2 <= 4
a2 + b3 <= 4
a3 + b1 <= 4
a3 + b2 <= 4.
For the total number of points in the set to be 21, these must all be
equalities. Without loss of generality, a1 is not equal to 1. Then we
have two cases to check: a1=2 or a1=3.
Case 2.2: a1=2, so b1,b3=2, so a2,a3=2, and then b2=2 by the fact that
the above relations are equalities.
By exhaustion left to reader, this is impossible. (Sorry. I have not
been able to simplify this, but the exhaustion is fairly easy; one only
needs to check about 3-6 cases.)
Case 2.3: a1=3, so b1,b3=1, so a2,a3=3, and then b2=1. Again, this is
impossible by an exhaustion left to the reader.
This completes the proof. Unfortunately, the computer lab is closing now,
so I cannot complete this message as I said I would.
Date: Mon, 18 Jul 1994 18:43:55 -0400 (EDT)
From: "Douglas Zare (NC)" <zare@virtu.sar.usf.edu>
To: smith_k@mth15.mth.cmich.edu
Subject: Set
Questions stimulated by Set:
1) Given any hypergraph, what is the maximum number of points that can be
chosen so that no line is contained? Equivalently, what is the minimum
number of points that one must choose so as to intersect each line? Of
course, it would be interesting to solve the case of affine d-space over
Z3 as a first step. For d=5, the best construction I have found is 42.
xxo oox ooo ooo ooo oox ooo ooo ooo
xxo oox ooo ooo ooo oox ooo ooo ooo
ooo xxo oox ooo ooo xxo ooo oox ooo
oox xxo ooo ooo ooo oox ooo ooo ooo
oox xxo ooo ooo ooo oox ooo ooo ooo
xxo ooo oox ooo ooo xxo oox ooo ooo
ooo ooo ooo oox oox ooo ooo ooo xxo
ooo ooo ooo oox oox ooo ooo ooo xxo
oox oox ooo xxo xxo ooo ooo ooo ooo
Projective space is quite simple; d-space can be blocked by a
projective (d-1)-space, and it is easy to show that this is necessary.
2) For which hypergraphs and which values of n can one find a set of
points which intersects each line in exactly n points? What if one allows
a set of values? For the construction of block designs, of course, it is
particularly interesting to consider sets which either contain lines or
have some constant intersection, for then we can induce a new design by
removing this set.
3) Can some of the properties of the xxo oox ooo
xxo oox ooo
ooo xxo oox
collection of points be generalized? One interesting property is that
every point which is not in the set is contained in exactly two lines
containing two points of the set. This property, or generalizations of
it, seems to be rare.
Date: Wed, 20 Jul 94 11:52:15 EST
From: "Ken W. Smith" <smith_k@mth15.mth.cmich.edu>
To: "Douglas Zare (NC)" <zare@virtu.sar.usf.edu>
Subject: Re: Set
Hi Doug,
Thanks for your message. I got the first half (sent earlier) and
skimmed through it and felt that it looked very good. I have not yet read it
real carefully. I am looking at a book by Segre and trying to find out what is
known in the literature about arcs.
We had power out here for 3 days (!) after a hard rain flooded the
building with the power transformer... So your more recent message was bounced
back to you. But I just received the re-send.
I'll get back to you soon, after I've read your work more carefully.
Ken
-------------------------------------------------------------------------------
Kenneth W. Smith (smith_k@mth15.mth.cmich.edu or 32wenpw@cmuvm.csv.cmich.edu)
Math Department, Central Michigan University, Mt. Pleasant MI 48859
Work phone: 517-774-3639 or 3596
Date: Thu, 4 Aug 94 11:13:46 EST
From: "Ken W. Smith" <smith_k@mth15.mth.cmich.edu>
To: "Douglas Zare (NC)" <zare@virtu.sar.usf.edu>
Subject: Re: Set
Hi Doug,
Here is the abstract of a talk I will give at the end of this month.
ABSTRACT:
SET - a combinatorial card game
Ken W. Smith* and Doug Zare
A new popular card game uses a deck of 81 cards with geometrical
shapes. Players compete to recognize "SETS", that is, certain patterns or
"anti-patterns" of cards.
This is a game every finite geometer should know, for the game can be
described as a hunt for lines in AG(4,3)! I will introduce the game (I've
brought my own deck!) and will briefly talk about certain obstructions to the
game which form large arcs in AG(4,3).
This talk will be very casual and requires no mathematical background.
Ken
Date: Thu, 4 Aug 1994 21:53:39 -0400 (EDT)
From: "Douglas Zare (NC)" <zare@virtu.sar.usf.edu>
To: smith_k@mth15.mth.cmich.edu
Subject: Set
The abstract looks good.
Although I had never seen Set before June, it seems to have been out
for a couple of years. According to the packaging on the decks I bought,
GAMES Magazine reviewed Set very favorably, as did MENSA. I am guessing
that this means some analysis has been made in GAMES or in the Journal of
Recreational Mathematics, but I do not have access to a good library at
the moment. One other thing: the instructions which came with the deck I
bought give a weaker upper bound for the size of an arc: size < 22.
Anyway, I have not done any more work on Set in a while, so I have
no more results. However, one idea has been bothering me for a while.
Suppose one used a sort of greedy algorithm for generating arcs: at each
step, add a point to the arc-so-far which maintains the property of being
an arc and leaves the greatest possible number of points not on a line
with two points. Another way of looking at this algorithm is to choose
the point which maximizes the number of overlaps of lines containing two
points of the arc. Of course, this choice is not unique, so perhaps there
could be other decision heuristics used to break ties, but I suspect
that this algorithm would come fairly close to finding the optimum.
Another idea is to find the smallest maximal arc. I suspect that the
opposite heuristic to the one described above might do well at
constructing these, but I have not investigated this problem yet, even
in A3(Z3).
By the way, in what type of a setting will you be giving the talk?
You mention finite geometers so I assume that you mean some sort of
conference in that area, but I am unfamiliar with conferences in general.
Would it be possible to get a bulk discount on Set? I imagine that a good
fraction of anyone seeing the talk would be interested in buying a deck.
Anyway, I'll e-mail again next week with data on the algorithms.
Doug
Date: Tue, 9 Aug 94 20:05:39 EST
From: "Ken W. Smith" <smith_k@mth15.mth.cmich.edu>
To: "Douglas Zare (NC)" <zare@virtu.sar.usf.edu>
Subject: Re: Set
Hi Doug,
I'm in a hurry so I'll make some brief responses --
I've not seen it in J.R.M. (which I subscribed to until recently) but
I've not looked at GAMES. I had NO instructions (almost) with my deck and
certainly no mention of arc size. It is GREAT that your copy mentions "size <
22" for this provides additional motivation for our paper!
I'm attending the
SECOND UPPER-MICHIGAN COMBINATORICS WORKSHOP
ON
CODES, DESIGNS, AND GEOMETRIES
at Michigan Technological University in Houghton, Michigan, Aug 17 - 20. It is
sponsored by Al Baartmans, Don Kreher and Vladimir Tonchev, who are some pretty
sharp guys in design theory.
Ken
Date: Sun, 30 Oct 1994 23:10:27 -0500 (EST)
From: "Douglas Zare (NC)" <zare@virtu.sar.usf.edu>
To: "Ken W. Smith" <smith_k@mth15.mth.cmich.edu>
Subject: Hello again,
There are some interesting patterns that I have noticed in the maximum
oviods of Set. I do not have time to go through all of them now, but I
will summarize a couple:
1) The subgroup of the affine group in three dimensions which fixes the
9-point ovoid in A3(Z3) as a set is large. It is two-transitive and is
of order 144. This classifies it, but I forget the name of the group.
Note that the action of this group on the complement set is transitive.
2) AAB CCA BBC
AAB CCA BBC
BBC AAB CCA
Then each of the {A's}, {B's}, and {C's} form a 9-point oviod.
3) Recall that every point of the complement of the 9-point ovoid is on
exactly two lines containing two points of the ovoid. 60 out of the 61
points in the complement of the 20 point ovoid in A4(Z3) are on exactly
three lines containing two points of the ovoid. There is one special
point, which is on ten such lines. This happens with one and two instead
of three and ten in two dimensions.
4) Observation by David Roberts (my Algebra professor): Every line
through the special point in the complement of the 20 point ovoid
contains 0 or 2 points of the ovoid. Thus, perhaps we should be looking
at ovoids in P3(Z3) with 10 points (I have not checked this).
5) 2 + 0(2) + 1 = 3
4 + 1(4) + 1 = 9
9 + 2(9) + 0 = 27
20 + 3(20) + 1 = 81
This suggests that a the number of "non-special" points in the
complement of an ovoid might be related to a multiple of the size of
the ovoid. This would suggest a size of 48 [+4(48)+3=243], although
perhaps 44 [+9/2(44)+1=243] might be reasonable as well. I still have not
progressed beyond the bounds of 44-53.
More later,
Doug
--------------------------------------------------------------------------
Anyway, I think that there is more in the literature, and I will check
that soon. I welcome any comments and contributions.
More later,
Doug
Additional material
[ Editor: two further postings: Chris Long's December 1993 summary on
Set, Steiner triple systems and the generalization "Upset", and Greg
Dionne's proof for a 1996 "Ob-SET puzzle" by Tom Magliery. ]
In article <2efn8s$dgl@cnj.digex.com> I posed the following problem:
> Define a finite set S to be "Setable" if there exists a commutative
> binary operation * defined on S such that for all elements a,b,c \in
> S a*a=a, and if a*b=c then b*c=a. Prove or disprove that |S|=3^n for
> some integer n.
I meant that a*b should be defined for all a,b \in S, as otherwise
there are trivial counterexamples. Isn't a binary operation on a set
by definition defined for all pairs of elements from that set?
I received several excellent replies (and questions) and I came across
some related information on my own. I'll try to cover everything in
this one article; if you're looking for something specifically you may
wish to skim.
Set:
The commercial game of Set is played with 81 cards. Each card has 4
attributes (color, number, shading, shape), and each attribute has 3
possible values (red-green-blue; 1-2-3; open-solid-lined; diamond-
oval-squiggle). Each possible combination of attributes is
represented once and only once (hence 3^4=81 cards). A set is defined
to be any 3 cards such that for each attribute either each card has
the same value, or all 3 have different values. Any number of people
may play. The deck is shuffled and placed face down, and then the
cards are turned over one at a time and spread over the playing
surface (at a pace agreed upon by the players). As soon as someone
spots a valid set, they cry out "Set! and claim the 3 cards. The
winner is the person with the most sets at the end of the game.
A simple version of Set with only 2 attributes may be played using 9
cards from a regular deck. The first attribute will be rank (e.g.
jack-king-queen), the other suit (e.g. clubs-hearts-diamonds).
Setable sets, BIBDs, and Steiner Triple Systems
A Steiner Triple System, or STS, is a specific type of balanced
incomplete block diagram, or BIBD. From Roberts, _Applied
Combinatorics_:
A *balanced block design* consists of a set X of v>=2 elements
called *varieties* or *treatments*, and a collection of b>0 subsets
of X, called *blocks*, such that the following conditions are
satisfied:
each block consists of exactly the same number k of varieties, k>0
each variety appears in exactly the same number r of blocks, r>0
each pair of varieties appears simultaneously in exactly the same
number p of blocks, p>0
A balanced block design with k<v is called a *balanced incomplete
block design* since each block has fewer than the total number of
varieties. Such a design is also called a BIBD, a (b,v,r,k,p)-
design, or a (b,v,r,k,p)-configuration.
A Steiner Triple System, or STS, is a special type of BIBD with k=3
and p=1. The connection between a Setable set and an STS is
immediate. A set S with |S|>1 is Setable if and only if an STS exists
with v=|S|; note however that sets with |S|=0,1 are Setable there do
not exists STSes with v=0 or 1. To see this connection, if we have an
STS and {a,b,c} are a block define a*b=c etc.; likewise if S is
Setable and a*b=c (distinct), define {a,b,c} to be a block.
The question of for values values of v do there exists STSes was
settled by Kirkman (the same Kirkman of the Schoolgirls Problem) in
1847; he proved that there is an STS of v varieties if and only if v=3
or v=6n+1 or v=6n+3, n>=1. Hence a set S is Setable if and only if
|S|=1,3 (mod 6).
Thanks go to erickw@fraser.sfu.ca for pointing out this connection.
Upset and a projective plane
We can now use STSes to generalize the game Set. Given a set S of
cards such that an STS exists with v=|S|, define a set to be any 3
cards that form a block. The play is then as given above for Set. I
call Set generalized this way Upset since most games will be quite
complicated, Upset-ting you.
It follows from the previous results that the smallest possible
counterexample to my original problem has |S|=7. How could we play
this game? Number the cards from 1 to 7, and define 3 cards a,b,c to
be a set if and only if {a,b,c} = {x,x+1,x+3} (mod 7) for some x. The
sets are then {1,2,4}, {2,3,5}, {3,4,6}, {4,5,7}, {5,6,1}, {6,7,2},
and {7,1,3}. This is playable (but simple) since the rule isn't
difficult to remember. Interestingly, this is the same as the
projective plane of order 2 (the Fano plane); the connection is
obtained by defining cards to be points and {a,b,c} to be a line iff
{a,b,c} is a set (this arises because an STS with v=7 is *symmetric*
(i.e. b=v and r=k)). To make things clear for everyone, a projective
plane is defined by two properties:
two distinct points lie on one and only common line
two distinct lines pass through one and only one common point
A projective plane is called nondegenerate if there are four distinct
points, no three of which lie on the same line.
William Schneeberger (william@math.princeton.edu), erickw, and David
Radcliffe (radcliff@csd4.csd.uwm.edu) provided counterexamples with
|S|=7. David additionally noticed the connection between this and the
Fano plane, and also that Set with n attributes correspond to affine
planes.
Upset and a conjecture about primes = 1 (mod 6)
Upset with |S|=7 is too simple, and it turns out that the next non-Set
Upset (see below) occurs with |S|=13. One such version of Set employs
rules similar to that which we gave for |S|=7. Number the cards from
1 to 13, and define 3 cards a,b,c to be a set if and only if {a,b,c} =
{x,x+1,x+4} (mod 13) OR {a,b,c} = {x,x+2,x+7} (mod 13) for some x.
The fact that such a rule exists for |S|=7 and 13 leads me to
conjecture that such a representation is always possible if |S| is a
prime (except for |S| clearly we must have |S|=1 (mod 6)). It is
known that there are 2 essentially different STSes with v=13; does
this other STS have modular rules? If this is the case, do all STSes
with prime v = 1 (mod 6) admit modular rules?
Upset and number of ways to play
The number of different versions of Upset for |S|=0,1,3,7,9 equals 1;
for |S|=13 there are 2 and for |S|=15 there are 80 (Roberts). The
number of distinct STSes of v varieties is in general unknown
(Roberts, 1984), but I imagine that there are some partial results.
For example, is it known have many distinct STSes there are if v is
prime?
This answers a question posed by Tim Chow in
<1993Dec13.194258.15788@galois.mit.edu>:
> Another question: are there nonisomorphic Set structures on the same
> set?
Set, Upset, groups of cards with no sets, and a neat question
A problem which has been discussed on Usenet but for which I have seen
no complete solution is the question of the maximal subset of cards in
Set from which no set can be formed. Let this number for a version of
Set with n attributes be M(n), then easily M(0)=1, M(1)=2, M(2)=4; not
so easy but still not hard M(3)=9. The discussion on Usenet about
normal Set (4 attributes) resulted in M(4)>=20 (easily M(n+1)>=2*M(N))
and the conjecture that M(4)=20. However, Clint Williams mentioned to
me that Mrs. Falco (the inventor of Set) told him that M(4)=21! Can
anyone find such a subset, or a journal article on the topic?
This partially answers a question posed by Tim Chow in
<1993Dec13.194258.15788@galois.mit.edu>:
> What I've always wondered is, how many cards do you need to deal
> before you're guaranteed to have a set? In the above terminology, if
> S is Setable, then what is the largest subset T of S such that a*b is
> in S - T for every pair of distinct elements a and b in T? In
> particular, what is the answer for the standard deck (of 81 cards, I
> believe)?
This question can be extended to Upset. For a given game of Upset U,
define M(U) analogous to above. Then for |U|=0 we have M(U)=0, and as
before for |U|=1,3,9 we have M(U)=1,2,4. It's easy to see that for
|U|=7 M(U)=4 (what does M(U) for my second Upset example equal?). The
most interesting question occurs for values of |U| for which there is
more than one possible version of Upset. Given two different games of
Upset U and V for which |U|=|V|, is it true or false that M(U)=M(V)?
If true, is there an easy way to calculate M(U) given |U|?
-- Chris Long <clong@cnj.digex.com>
----------
In article <mag-2002961313240001@jayhawk.ncsa.uiuc.edu>,
mag@ncsa.uiuc.edu (Tom Magliery) writes:
> Ob-SET puzzle: (This one's easy; I'm just curious to see different
> approaches to proving it.) (If you don't know what the game of SET
> is, look here: http://sdg.ncsa.uiuc.edu/~mag/Set/) First a fact:
> For any two SET cards, there is exactly one other that together with
> them will form a SET. Now then, suppose you have two SETs, one with
> cards {a,b,c} and one with cards {d,e,f}. Let g, h, and i be the
> cards that form the SETs {a,d,g}, {b,e,h}, and {c,f,i}. Prove that
> either {g,h,i} is a SET, or g, h, and i are all the same card.
For those of you without a web reader, here's the relevant section,
taken from Tom's home page:
The object of the game is to identify a 'Set' of three cards from
12 cards laid out on the table. Each card has a variation of the
following four features:
(A) COLOR: Each card is red, green, or purple.
(B) SYMBOL: Each card contains ovals, squiggles, or diamonds.
(C) NUMBER: Each card has one, two, or three symbols.
(D) SHADING: Each card is solid, open, or striped.
A 'Set' consists of three cards in which each feature is EITHER
the same on each card OR is different on each card. That is to
say, any feature in the 'Set' of three cards is either common to
all three cards or is different on each card.
The Magic Rule: If two are... and one is not, then it is not a
'Set'
Tom requested different solutions, so, here's mine. Compare with
yours.
I see by the above rules that if {g,h,i} are all the same card, then it
is a set. I didn't find out how many cards were available to choose
from, but I assume this distinction was added because each card is
unique in the game. I don't know if the deck of cards to choose from
contains all the various permutations of colors, symbols, numbers, and
shadings... I'll assume it does, but I'm guessing that there is a
suitably chosen set of all the permutations available in the real
deck.
Disclaimer: This is a brain-dump with rather sloppy notation, so I
hope this will be somewhat coherent.
Let's assume {a,b,c}, {d,e,f}, {g,h,i}, {a,d,g}, {b,e,h}, and {c,f,i}
are all sets. We will now show {g,h,i} is a set.
define: {a,b,c} = {(A1,A2,A3,A4),(B1,B2,B3,B4),(C1,C2,C3,C4)}
{d,e,f} = {(D1,D2,D3,D4),(E1,E2,E3,E4),(F1,F2,F3,F4)}
{g,h,i} = {(G1,G2,G3,G4),(H1,H2,H3,H4),(I1,I2,I3,I4)}
Where the 1's correspond to COLOR, 2's correspond to SYMBOL,
etc.
Any (Xi,Yi,Zi) is a 'triplet' if Xi, Yi, and Zi are all the
same or are all different.
We note that if (Xi, Yi, Zi) is a triplet for each 'i', then the
corressponding {x, y, z} is a set. We will now try to show that
(Gi, Hi, Ii) is a triplet for each 'i'.
Let's analyze this one feature ('i') at a time dropping the subscripts,
commas, spaces, and parenthesis from our notation:
(Thus, (Xi, Yi, Zi) simply becomes XYZ):
1. We know that each of: ABC DEF ADG BEH CFI are all triplets,
because they are assumed to be from sets.
2. We note that each feature has three members.
We label them with numeric tokens '0,' '1,' and '2.'
3. Any triplet must be 000, 111, 222, or some permutation of 012;
all others violate "The Magic Rule."
4. Note that the sum of the numeric tokens must be divisible by
three (any combination that isn't divisible by three is not a
set). This is equivalent to saying that the addition of each
token modulo 3 better be equal to zero for it to be a triplet.
So, we have, by assumptions:
5a. (A+B+C)%3 = (D+E+F)%3 = 0.
5b. (A+D+G)%3 = (B+E+H)%3 = (C+F+I)%3 = 0.
6. From (5a), (A+B+C+D+E+F)%3 = 0.
7. From (5b), (A+D+G+B+E+H+C+F+I)%3 = 0.
8. Subtract 6 from 7: (G+H+I)%3 = 0.
Then, GHI is a triplet, each (Gi, Hi, Ii) is a triplet, and {g,h,i} is
a set.
=)
-- Gregory E. Dionne <dionne@icd.teradyne.com>
[ Editor: the opening "Let's assume ... {g,h,i} ... are all sets"
assumes what is to be proved; the argument in steps 5-8 uses only the
other five sets. ]