From: clong@cnj.digex.net (Chris Long) Newsgroups: sci.math,rec.games.misc Subject: Re: Help with the game SET Date: 19 Aug 1994 07:09:08 -0400 NNTP-Posting-Host: cnj.digex.net A proof was published in the journal _Discrete Mathematics_ that the maximum is 20 in the 1970s, and I suspect that the first proof appeared long before then. Here's an old article on a related topic, somewhat dated since I have information answering some of the questions below. If anyone is interested in an update I'll put one together and post it. Path: cnj.digex.com!cnj.digex.com!not-for-mail From: clong@cnj.digex.com (Chris Long) Newsgroups: sci.math,rec.puzzles Subject: Set, Steiner Triple Systems, and Upset Date: 14 Dec 1993 08:39:51 -0500 Organization: Express Access Online Communications USA: 800-969-9090 Lines: 177 Distribution: world Message-ID: <2ekfn7$n6e@cnj.digex.com> References: <2efn8s$dgl@cnj.digex.com> <2eg22m$hbf@cnj.digex.com> <1993Dec13.194258.15788@galois.mit.edu> NNTP-Posting-Host: cnj.digex.com Xref: cnj.digex.com sci.math:11241 rec.puzzles:9279 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 k1 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? {See above} 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, 265 Old York Rd., Bridgewater, NJ 08807-2618 Score: 0, Diff: 1, clong killed by a Harvard Math Team on 1