Conference rusure::math

Given a pool of N cards, there are C(N,2) pairs that may be selected from 
that pool. Assume that for every pair, the set-partner of that pair is
outside the pool. So we want C(N,2) + N >= 81. For N=12, C(12,2) = 66, so 
12 cards is not enough to guarantee a set among the 12. However, for N =
13, C(13,2) = 78, so any pool of 13 cards must contain 13+78-81 = 10 sets. 

>Given a pool of N cards, there are C(N,2) pairs that may be selected from 
>that pool. Assume that for every pair, the set-partner of that pair is
>outside the pool. So we want C(N,2) + N >= 81. For N=12, C(12,2) = 66, so 
>12 cards is not enough to guarantee a set among the 12. However, for N =
>13, C(13,2) = 78, so any pool of 13 cards must contain 13+78-81 = 10 sets. 

This would be true if the missing set-partners were unique, but that is not
always the case; e.g. the set of four cards:

(0,0,0,0) (1,1,1,1) (2,0,0,0) (2,1,1,1)

has (2,2,2,2) as a missing set-partner in two different ways. In fact,
(2,2,2,2) is the missing set-partner of a LOT of pairs (I think 40, 8 pairs
with elements in {0,1} alone, four pairs with a single 2 in each of four
places, two pairs with two 2's in six combos, 1 pair with three 2's in four
combos)...

Could you please clean up your definition ?  First you say

		A set is three cards such that...

Later, you say

		Any two cards form a set.


Perhaps you didn't mean to establish particular significance to the number 3 ?

Please clarify.

/Eric

    Re .3:
    
    Observe that .0 does not say two cards form a set; it says they define
    a set.  This is meant in the same way as saying that two points define
    a line.  Given two cards, there is only one third card that can be
    grouped with them to form a set.
    
    
    				-- edp

>This would be true if the missing set-partners were unique, but that is not
>always the case; e.g. the set of four cards:
>
>(0,0,0,0) (1,1,1,1) (2,0,0,0) (2,1,1,1)
>
>has (2,2,2,2) as a missing set-partner in two different ways. 

That's true; that's why the number of sets jumps from 0 to 10 when n 
increases from 12 to 13. When n=12, the 66 pairs can be partnered by the 
81-12 = 69 cards outside the pool, but when n=13, there is no room for the 
78 pairs to have partners outside, so some of them *must* be in the pool.

> That's true; that's why the number of sets jumps from 0 to 10 when n 
> increases from 12 to 13. When n=12, the 66 pairs can be partnered by the 
> 81-12 = 69 cards outside the pool, but when n=13, there is no room for the 
> 78 pairs to have partners outside, so some of them *must* be in the pool.

Actually, It is quite easy to find a group of 13 cards which contains no 
sets.  It is true, that given 13 cards, you have 78 groupings of two cards,
each of which define a set.  But, the 78 cards which complete
those sets do not have to be unique.   There may be 50 cards which 
will suffice to complete those 78 sets - leaving plenty of cards which will
not cause a set if included with the cards already laid out.  Remember, 1 
card does not  uniquely define a set, two cards do.  Any single card is 
actually a member of 40 different sets.

According to your reasoning, you can have 12 cards, on the table and no 
set.  There are 69 cards left in the deck, and apparently only 66 of
those actually cause (at leaste one) set to be formed with the 12 cards
on the table.  Doesn't that mean that there are 3 cards in the deck which
will not cause any set to be formed, thus giving at least three possible
combinations of 13 cards with no set?  Which leads to a paradox.

Well, I'm not sure I have explained it well, but here is a group of 13
cards which contains no set:

 (0100) (0200) (1112) (1220) (2212) (1011) (1000) (0021) (2221) (1010) 
 (2011) (0010) (1202)

And, here is a group of 18 cards which contains no set:

 (0000) (0001) (0010) (0011) (0100) (0101) (0110) (0111) (1000) (1001)
 (1010) (1011) (1100) (1101) (1112) (1122) (1212) (2112)

I hope I haven't made any typos.

-Jonathan

Aha! I see the error of my ways... back to the drawing board. Sorry about 
that.

As a courtesy to my friend, Peter Gordon, who posed this
problem to me in the first place.  He has asked me to say
on his behalf, that if this does turn out to be a *very*
difficult problem, he wants to go back to Grad school and
use it as his thesis - so he has asked that no one use
it as their thesis before he get's a chance.

Of course, if it turns out to not be all *that* difficult -
Meaning, it can be solved without months of theorizing, then
he and I are both keen to know the answer and we will both
heap great praise upon you - because it has us stumped.

Remember, there are really two problems.

The easier of the two is as originally stated...

1.  What is the minimum number of cards which you
    have to draw to insure a set.

And the more difficult problem (which encompasses
the easier one)...

2.  For a group of N cards, what is the probability
    that there is (or isn't) at least one set.

-Jonathan

I like the boggle. But I can't stop thinking that it inolves a game of any kind.
And if that's so, what is it?

I'll try to solve it, but I'd probable be more motivated if I knew what a 
solution would could be used for. And I'm sure that I'm not the only one who
asked myself from where the problem originates. So, why not tell us?

I wrote a little program last night to create all sets and systematically
remove points until all the sets were gone. Much to my surprise, it simply 
removed *all* the zeroes from everything, leaving just the 2^4=16 numbers 
composed of {1,2}!

With a simplistic selection of points, the pattern of sets removed with
each successive point is somewhat irregular, and it would probably be more
effective to use a point-selection algorithm that maximizes the number of
sets removed at each stage. 

My intuition now says that 18 is probably optimum, since it not much bigger 
than the solution produced by the program, and I would expect the best 
solution to be a multiple of 3!=6. A version of the 18-point solution given
earlier with {0,1,2} equally/symmetrically distributed would be very
convincing. 

> I like the boggle. But I can't stop thinking that it inolves a game of any kind.
> And if that's so, what is it?
> 
> I'll try to solve it, but I'd probable be more motivated if I knew what a 
> solution would could be used for. And I'm sure that I'm not the only one who
> asked myself from where the problem originates. So, why not tell us?

OK - You asked for it.  The history behind the boggle.

My friend Peter Gordon is an Associate Editor of Games magazine.  He occasionally
(sometimes frequently) calls me to try out new boggles on me or ask for help in 
cracking cryptorythms or other problems.  Now, one of the sections in Games 
magazine is a review of new games which have come on the market.  The employees
of Games usually play these games then write up a review.  One of the new games
is called "Set" (or "Sets" I'm not exactly sure).  Now, the game comes with
a deck of (you guessed it) 81 cards.  Each card has 4 attributes which are, I
believe, 1. shape (either an oval, a heart or a squiggle)  2. Color (either
red, blue or purple)  3. number (either 1, 2 or 3 shapes on the card) and
4. Fill style (either solid, outline, or hashed).  The game is played like this...
Everyone who is playing sits around a table and one player puts 12 cards down
face up.  Then everyone stares at the cards, trying mentally to find 3 cards
which form a set.  When one player thinks they have found a set. they yell "Set".
At this point, they must proceed to show the set they have found.  If they can
show a set, they get a point, and the cards are shuffled and re-dealt for the
next round.  Or, they may have made a mistake, and when they attempt to show
what they thought was a set, it actually isn't.  In this case, the player
loses a point.  It may be the case, that there is no set (or none of the
players can find one).  In this case, 3 additional cards are placed face up
on the table, and the search continues.  Peter said, that at Games, they all
enjoyed this game immensely, and highly reccommend it.  I believe it sells for
around $12.

Well, in writing up the review, they wanted to say what the probability was
that with 12 cards you could find a set, and what the probability was with 15 
cards.  Unfortunately, neither Peter, nor the other mathematician (by which
I mean taht they have bachellor's degrees in Mathematics) were able to solve
this probability problem.  The creater of the game did not know either, but
(s)he claimed that it was over 95% for 12 cards, and over 99% for 15 cards.
Peter, like myself, being stubborn was intrigued by the problem, and would
like to find the precise answer.  Or perhaps just the answer to the simpler
problem of the minimum number of cards it takes to guarantee a set.  and
that's how I came to post the problem here.

In the games they played, they found that about one in 20 deals of 12 cards
resulted in no set, and that they never had a deal of 15 cards which contained
no set.  I wrote a program that would make radom deals of the desired number
of cards.  This program shows that with 12 cards, the chance of finding a set
is somewhere between 96% and 97% (closer to 97), and with 15 cards, the
chance of finding a set is over 99.9%

With 18 cards, my program could not find a deal which did not have a set 
after 50 million deals.  But there obviously are deals of 18 cards which do
not contain a set.  Another program I wrote, which tried to find the largest
deal without a set soon turned up a deal of 18 cards which contained no set.
Unfortunately, the number of actual deals to contend with is astronomical, 
so I can't be sure if there is a deal of 19 cards which contains no set and 
I just haven't found it. Various heuristics, like picking cards one at a time
such that, the number of cards left to pick which will not cause a set is kept
a maximum, just did not work all that well.

Well, now you know the story.  I hope this will redouble your efforts.

-Jonathan

> I wrote a little program last night to create all sets and systematically
> remove points until all the sets were gone. Much to my surprise, it simply 
> removed *all* the zeroes from everything, leaving just the 2^4=16 numbers 
> composed of {1,2}!
> 
> With a simplistic selection of points, the pattern of sets removed with
> each successive point is somewhat irregular, and it would probably be more
> effective to use a point-selection algorithm that maximizes the number of
> sets removed at each stage. 

If I understand what you are saying, don't you want to minimize the number
of sets remove at each stage, so you can continue picking "points"  which
would mean cards, to end up with the maximum number of cards.

One of the programs I wrote did more or less just this.  It worked
differently, though not any better than the program which tried to maximize
the number of cards which were left to choose from.  ie. it couldn't
turn up a group of more than 16 cards, without backtracking to 
possibilities which were of equal weight and trying all of them. - which
with 18 cards, turns out to be quite a lot of possibilities over all.
Of course, I haven't tried introducing logic which would take advantage
of symmetries to reduce the actual number of possibilities.

-Jonathan

>If I understand what you are saying, don't you want to minimize the number
>of sets remove at each stage, so you can continue picking "points"  which
>would mean cards, to end up with the maximum number of cards.

Maybe it's just semantics. I construct all the sets from all the points, 
then start removing points and all their associated sets. The more sets I 
remove per point, the faster the sets disappear and the more points I have 
left over at the end with all their set-partners already gone. So far my
algorithm removes all the points with a '0' value as a coordinate (I'm
thinking in 4-space), leaving the rest. If I start with a few random
removals to disrupt the patterns, maybe I'll get something more interesting. 

> Maybe it's just semantics. I construct all the sets from all the points, 
> then start removing points and all their associated sets. The more sets I 
> remove per point, the faster the sets disappear and the more points I have 
> left over at the end with all their set-partners already gone. So far my
> algorithm removes all the points with a '0' value as a coordinate (I'm
> thinking in 4-space), leaving the rest. If I start with a few random
> removals to disrupt the patterns, maybe I'll get something more interesting. 

I think I see what you are doing now.  It is the opposite of what
I am doing.  You are starting with 81 cards, and removing cards, one by
one, until you are left with a collection of cards which contains no 
sets.  I am starting with 0 cards and adding cards (which do not cause a
set) until I get to a point at which all of the remaining cards will cause a 
set.  I'll have to try thinking about it from your perspective and see if it 
brings anything to light.

-Jonathan

    Here are the lines I am working along:
    
    There is a binary operation defined by the completion of a "set".  That
    is, if we have two cards, A and B, there is exactly one card C such
    that A, B, and C form a "set".  So we can write C = AB or C = A*B.
    
    I will use lowercase letters to indicate individual elements of a card,
    and uppercase for an entire card.  Thus, A = (a0,a1,a2,a3).
    
    There is a simple multiplication table for the elements:
    
    * | 0 1 2
    --+------
    0 | 0 2 1
    1 | 2 1 0
    2 | 1 0 2
    
    This operation is commutative, but not associative.  Thus, the
    expression abc must have a defined ordered; I will use left-to-right,
    so abc = (ab)c.  Also observe that aba = b.
    
    The binary operation on the cards is just the element-by-element
    operation on the elements; it is also commutative and associative.
    
    Suppose two cards A and B are in a hand H that does not contain any
    "sets".  Now consider an arbitrary card C, not equal to A or B or AB.
    There are then six cards:
    
    	C, CA, CAB, CABA, CABAB, and CABABA.
    
    These are six different cards, none of them A or B or AB.  This can be
    proven with a program at least.  In effect, A and B partition the
    remaining 78 cards (excluding AB) in 13 sets of 6.  (Those are math
    sets, not the game "sets".)  It doesn't matter which card is chosen for
    C in each set; the rest of the members will follow from it.  (Observe
    that CAA = C, and I think CABABA = CB; the previous statement can be
    proven from these.
    
    In each partition of six, at most 2 cards can be in the hand H.  Since
    each member is the product of the previous member (the first "follows"
    the last) and either A or B, a "set" would be formed if two adjacent
    members were selected.  If 3 cards were selected from one of these
    sets, none of the cards adjacent, we would have C, CAB, and CABAB or
    CA, CABA, and CABABA.  But (C)(CAB) = CABAB, and similarly for the
    other possibility.  (If this pans out, I can prove the preceding
    formally.)  So we can select at most 2 cards from each of these 13
    sets.  That would give us A, B, and 2*13 other cards, for a total of
    28.
    
    The next step is to demonstrate that interactions among the cards from
    the sets in the partition reduce the choices even further.
    
    
    				-- edp

    Here is a hand of twenty cards with no "set":
    
    0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1012 1022 1102 1202
    2012 2102 2110 2111 2122 2212
    
    I have a search program going, but it is going to take a while.  It is
    taking some advantage of the symmetry of the cards, but not all of it.
    
    I think we could take advantage of all of the symmetry to perform an
    exhaustive search.  There are six permutations of 0, 1, and 2, and each
    of the four elements of the cards can be subjected to one of the six
    permutations.  There are therefore 1296 permutations of the deck that
    preserve the formation of "sets".
    
    Every hand (a mathematical set of the cards) can be permuted into other
    hands by these permutations.  Every hand will be in a class with other
    hands into which it can be permuted, and which can be permuted into it
    and into each other.  We can give an ordering to the hands by sorting
    the cards within each hand and then comparing two hands card by card;
    the hand to have the first card in sorted order that is less than the
    corresponding card in the other hand is the lesser card.  Then each
    class of hands can be represented by the least card within the class.
    
    A search can then proceed by adding a potential card to a growing hand.
    Then the new hand is checked to see if all permutations leave that hand
    less than any of the permuted versions.  If one of the permutations is
    lower, the class that this hand is a member of has already been
    checked, and we skip this hand and consider a different potential card. 
    If no permutation is lower, we add another potential card.
    
    I found the twenty-card hand above using only part of the symmetry,
    only one-sixteenth of the possible symmetry for each card.  I'm sure
    that using the full symmetry would result in a faster search, one that
    would probably complete in a few seconds.
    
    
    					-- edp

    Take a "setless hand" and seperate it into three groups according to
    the value of the "lefthand" characteristic.  In each group look just
    at the remaining characteristics.  Take any two cards from any group,
    say A={x, a1, a2, a3} and B={x, b1, b2, b3}.  The completion of A and
    B is A*B={x, a1*b1, a2*b2, a3*b3}.  Obviously the hand cannot contain
    this card, or it would not be setless.

    Let us generalize the problem slightly and say that the "order" of the
    problem is the number of characteristics we are dealing with.  In this
    particular problem the order is 4.  From the previous we see that an
    order 4 setless hand consists of three order 3 setless hands, each with
    a different high order characteristic.

    An exhaustive search of the order three space (taking advantage of some
    of the implicit symmetry) takes only a few seconds and finds a maximal
    sized order three setless hand of 9.  This sets an immediate upper
    bound on the maximum size for an order 4 setless hand of 3*9 or 27.

				    Topher

RE: .16 (edp)

    Note that there is both more and less symmetry then indicated here.

    In addition to the transformations which permute the values of each of
    the four characteristics (1296 transformations), a given solution
    can be transformed by permuting the characteristics of all the cards
    in the hand.  Thus an alternate twenty card solution would be:

    0000 0010 0100 0110 1000 1010 1100 1110 0001 0011 0121 0221 1021 2021
    0122 1022 1102 1112 1222 2122

    Obtained by moving the left-most characteristic to the right.  Since
    there are 24 permutations of the 4 characteristics, we have 1296*24
    transformations or 31104 transformations in all.

    However, at least some of these transformations may map the original
    solution into the same result as other transformations.  This would
    reduce the amount of symmetry which could be exploited (each single
    potential solution would represent fewer alternate potential solutions,
    and therefore reduce the search space less).

					    Topher

   After a slight improvement to my program to reduce redundancy,
   and not print out as much garbage, it soon turned up a 
   group of 20 cards wihtout a "set".  So far, I've had 3 gut
   feelings about this problem turn up wrong.

   I'm glad to see that there have been some good thoughts on this
   problem, though I must admit, I could not really follow .15
   too well.  I don't know if trying to explain it again with
   a little more detail would help or not - or if I'm just being
   thick.

   Keep up the good work.  It appears now, that the solution is
   somewhere in the range of 21 to 28.  (For the minimum number
   of cards which guarantees a set).


   -Jonathan

    There is one more class of symmetry in the problem.  Any set of pairs
    (w,x,y,z) can be transformed to (w+x,x-y,w-2z,w+x+y+z) or other linear
    combinations of the original coordinates.  All arithmetic is modulo
    three.  The linear combinations must preserve information -- that is,
    it must be impossible to express any one of the expressions for one of
    the coordinates in terms of a linear combination of the others.
    
    I have nearly completed a search for hands of 24 cards; I expect it to
    complete without finding any.  This has taken a day and a half of
    computing time (on a MIPS 3100).  When it is done, I'll start another
    search taking advantage of the increased symmetry.
    
    Just for information's sake, if we consider a four-dimensional space
    which is of length three along each axis, with the "end" of each
    dimension connected back to its "beginning", like a torus, then the
    original problem is equivalent to asking what is the largest set that
    can be formed of points at integer coordinates that does not contain
    three colinear points.  In effect, a "set" as described in the original
    problem is really three points on a line in a toroidal four-space.
    
    Since an exhaustive search for hands in 3-space is quick, another
    approach to the 4-space problem might be to select one of the 3-space
    hands and make it one of the cubes in the 4-space.  Then slice the
    4-space differently, so we have three cubes each with one square filled
    in.  Then iterate on the possible completions of those cubes, again
    using our knowledge of the hands in 3-space.
    
    I would not be surprised if prior work exists on sets that do not
    contain colinear points.
    
    
    				-- edp

    Oh, one more observation.  All of the symmetry noted so far -- changing
    the values of the elements and permuting their positions -- can be
    captured in linear combinations of the elements plus constants.  Thus,
    by mapping w to:
    
    	aw+bx+cy+dz+e
    
    where a, b, c, d, and e are each selected from { 0, 1, 2 }, we can
    change the value of w in any of the six ways (w, w+1, w+2, 2w, 2w+1,
    2w+2) or swap it with any of the other elements.
    
    And for completeness, I should have noted that any selection of
    independent transformations for the elements does not change whether or
    not a set contains three colinear points.
    
    
    				-- edp

    My search for a hand of 24 or more cards with no "sets" did not find
    any.  The program has gotten rather complicated though, so I wouldn't
    take that as proof.
    
    In regard to the transformations noted earlier, observe that any point
    can be selected to be translated to the origin, and then any set of
    four linearly independent vectors from that point to four other points
    determine a unique basis for the 4-dimensional vector space.  There are
    81 ways to choose the first point, 81-1 ways to choose the second
    point, 81-3 ways to choose the third point so that it is not on the
    same line as the first two, 81-9 ways to choose the fourth point so it
    is not on the same plane, and 81-27 ways to choose the fifth point. 
    That gives us 982,575,360 different transformations of the points that
    preserve colinear triples.
    
    So all we need to do is select some points, check to see if they are
    canonical by testing whether any of the nearly one billion
    transformations map them to a set earlier in the sorting order, and
    then keep iterating on the selection of points.  No problem.  :-)
    
    At this point, it is obvious that there is a maximal hand that contains
    the points 0000, 0001, 0010, 0100, and 1000.  If the vectors among the
    points in any hand did not generate the complete 4-dimensional space,
    we could add another vector outside the generated space, and this new
    vector would map all the points in the hand to new points that could
    not be colinear with any two of the points in the hand.  So in the
    maximal hand, just take any point and four other points so that the
    four vectors are linearly independent, and these define a basis.  The
    coordinates of the points in this hand form a new hand that contains
    the points 0000, 0001, 0010, 0100, and 1000.
    
    
    				-- edp

    The library just got me a copy of _Projective Geometries Over Finite
    Fields_ by J. W. P. Hirschfeld.  The author almost gives us the answer:
    
         Thus a plane k-arc is a set of k points in PG(2,q) [q would
         be three in our case], no three of which are collinear:  a
         maximum plane k-arc is an oval.  A k-cap is a set of k points
         in PG(n,q) with n >= 3 such that no three are collinear.
         
    and elsewhere, about these sets and related ones:
    
         It is of great interest for applications to find maximal and
         particularly maximum such sets as k varies but the other
         parameters remain fixed . . . .  This number is known for
         only a few cases, although some bounds are always available.
         
    but Hirschfeld doesn't give any numbers!  Actually, PG(n,q) isn't quite
    the space we where thinking of (Z[q]^n), but information about it would
    be a significant step in the right direction.
    
    
    				-- edp

    Another way to approach this is to find a minimal set of cards that
    *cannot* be in the set.  E.g., in the boolean expression which is the
    product of 81*80/3=2160 triples:
    
    	(c0000+c1111+c2222)(c0000+c1112+c2221) ... (c0222+c1111+c2000)
    
    Expand this expression into a sum of terms, and then a term with the
    fewest atomic factors shows how to minimize the disallowed cards,
    and therefore to maximize the hand.
    
    I think this is the simpler approach, but it is computationally expansive
    (pun intentended).  The expansion will have 3^2160 = 3.82�10^1030 terms.
    But there's so much symmetry, much of it can be done symbolically, right?
    
    
    Note that this problem is just one from the following general class,
    and I think we've hit a few of these (and vice versa):
    
    Given a set of objects S, find a maximal subset T such that a collection
    of rules are satisfied.  Each rule has the form: If set M_i is in T,
    then object x_i is not in T.
    
    Does the generalization help?  Can a generic program be written for it?
    A fast one?  Can the 'finding of symmetries' amoung the rules be automated?
    
    
    Finally, here are a few variants on the original problem, in decreasing
    order of difficulty:
    
    	1.  Find the smallest set of cards such that any additional card
    	    will make a 'set'.
    
    	2.  Solve the original problem for the 27-card deck, where each
    	    card is a triple, rather than a 4-tuple.
    
    	3.  Solve the original problem using 2**4 'binary' cards.  A set is
    	    defined as *two* cards in which the values of any given attribue
    	    are all the same, or all different.

What's the problem?

	Let V_n be the vector space of dimension n over the field Z_3.   If 
S subset of V_n has no 3 collinear points, we'll say that it is *line-free*.
What is f(n), the maximum size of a line-free subset of V_n.


Some progress:

	f(4) < 22.
	Since we have a line-free subset of V_4 of order 20, it remains to
examine the case 21.


Approach:

	The key idea is that of a *triptych*.   If v is *any* non-zero vector
in V_n, then V_n can be partitioned into 3 hyperplanes perpendicular to v.
Each will be a translate of the subspace IM to V_(n-1).   Now, a partition
of S is induced by the partition of V_n, write:
	a -> [a1,a2,a3]
where a=b+c+d to indicate that S of order A is being partitioned into S1,S2,S3,
where |Si| = ai.   The Si will be line-free subsets of V_n-1.   We are free to
permute the ai, so will take a1>=a2>=a3.

	[How many triptychs are there in V_n?   v & -v induce the same 
partition, hence there are �(3^n-1) triptychs.]

	It is easy to see that:
		f(1)=2
		f(2)=4
		f(3)=9

	Now, suppose we have S (of order 9) subset of V_3, then since f(2)=4,
the following unfoldings of 9 in a triptych are conceivable:
	9 -> [4,4,1]		(9i)
	9 -> [4,3,2]		(9ii)
	9 -> [3,3,3]		(9iii)

	It is the work of a couple of minutes to see that (9ii) 9->[4,3,2] is 
not feasible, but the others are feasible as:

(9i)
**.	..*	...
**.	..*	...
...	**.	..*

or

(9iii)
**.	**.	...
*..	*..	.**
...	...	.*.

	In fact I can show that there is up to IM only one subset of V_3 of
order 9, and that has 9 triptychs of the form [4,4,1] and 4 triptychs of the
form [3,3,3].

	Now let's consider a line-free subset S (of order 22) of V_4, if such
a subset could exist.   The triptych forms of S are constrainted by the value 
of f(3):
	22 -> [9,9,4]		(22i)
	22 -> [9,8,5]		(22ii)
	22 -> [9,7,6]		(22iii)
	22 -> [8,8,6]		(22iv)
	22 -> [8,7,7]		(22v)

	Now, I have an arithmetic theory which I will put in the next reply
which says that S if it exists we can find a vector v with respect to which
the triptych is of the form (22i) or (22ii).

	So let's explore these.   We are free to exploit the symmetries of V_n
by rotating the left element of a triptych to be any orientation we like.   We
are also then free to make more limited transformations of the central element.
I will not make explicit comment that I am reducing the symmetry in this way.

(22i)	22->[9,9,4].   Unfold each of the 3 elements of the triptych vertically.

	4 4 ?
	4 4 ?
	1 1 ?

or	4 3 ?
	4 3 ?
	1 3 ?

but each of the question marks can be filled in only by 0 or 1, for the simple
reasons given above.   So we cannot get |S|=22.

(22ii)	22->[9,8,5].   Again unfold each of the 3 elements vertically.

	4 4 ?
	4 4 ?
	1 0 ?

	4 4 ?
	4 3 ?
	1 1 ?

	4 3 ?
	4 3 ?
	1 2 ?

	For each of these, no '?' can be replaced by more than 1, hence we
cannot do better than |S|=20!   The final possibility for (22ii) is:

	4 4 ?
	4 2 ?'
	1 2 ?

	Here ?' can be as much as 2, so while we certainly can't get 22 out
of the set, it looks as if we could squeeze 21 from it as:

	4 4 1
	4 2 2			(call this foo)
	1 2 1

	but this is not possible.   Briefly, the line-free 4-set of V_2 is
unique up to IM.   It can be viewed as:

**.    ..*    **.
**. or ..* or *..	call these block, cross and mixed.
...    **.    .*.

	If you have a block in a [4,4,1], the other 4 is a cross, and
vice versa.   So since we can choose the lhs of foo, we choose a block
and a cross, and the 4 in the middle-top element of foo can not be assigned
to permit the bottom left, top right, and bottom right elements to be 1.
This will be used in a couple of replies, so I show it here.

Andrew

The theory

Suppose S subset of V_n has a elements.  Any n of those may define a hyperplane
of V_n (by which I mean some linear translate of a subspace of V_n of dimension
n-1.)   Or if there are linear dependencies among the n points, the n-subset 
will appear in a plural number of hyperplanes.   In any case the important 
thing is that each n-subset of S *appears* in at least 1 hyperplane of V_n.

	There are C(a,n) (a choose n) hyperplanes, so there are >= C(a,n)
appearances.

	Now consider what it looks like from the perspective of the triptychs.
Each triptych is 3 hyperplanes.   How many n-sets appear in each triptych?
If a -> [a1j,a2j,a3j], then the triptych j witnesses C(a1j,n)+C(a2j,n)+C(a3j,n)
= s_j appearances of n-sets.   Since there are �(3^n-1) triptychs, there
exists a triptych j such that:

	s_j >= ceiling(2*C(a,n)/3^n-1)


Example: prove that f(n) < 10.

	Suppose that n=3, a=10.
	C(10,3) = 120.
	�(3^3-1) = 13.

	So there's a triptych j such that s_j >= ceiling(120/13) = 10.

	Now f(2) is famously 4, so let's look at the possible values for aij
& the corresponding C(aij,n):

	aij	C(aij,n)
	----------------
	=<2        0
	 3         1
	 4	   4
	----------------

	Now remember that a1j+a2j+a3j=10, and write the possible values of
the {aij,i=1..3} against s_j:

	{a1j,a2j,a3j}	s_j
	-------------------
	    {4,4,2}      8
	    {4,3,3}	 6

	The best that can be achieved is 8.   8 < 10, so there's no answer.


	Now, let's show using the same method that there must be a triptych
for 22 in V_4 of the form (22i) or (22ii), assuming that a line-free 22-subset
of V_4 exists:

	n=4
	a=22
	C(22,4) = 7315
	�(3^4-1) = 40.
	So there's a triptych j with s_j >= ceiling(7315/40) = 183.

	aij	C(aij,n)
	----------------
	=<3        0
	 4         1
	 5	   5
	 6	  15
	 7	  35
	 8	  70
	 9       126
	----------------

	{a1j,a2j,a3j}	s_j
	-------------------
	    {9,9,4}     253
	    {9,8,5}	201
	    {9,7,6}	176
	    {8,8,6}	155
	    {8,7,7}	140

	So since the average of all s_j >= 183, there's one s_j which is
253 or 201.   QED.


	This technique can be extended.   We can generalize to examine m-sets
rather than restricting ourselves to n-sets.   We can also examine more
closely the case of linear dependence in any 1 m-set.   No 3 set will be
degenerate, by definition of the problem.   But if a 4-set is degenerate, then
in V_4 for example, it will appear in 4 hyperplanes rather than 1.   Thus
the number of appearances is unchanged mod 3.   And so on.

a=21?

	Suppose that we were examining 3-sets instead of 4-sets:

	n=3
	a=21
	C(21,3) = 1330
	�(3^4-1) = 40.
	But note that each 3-set appears in 4 hyperplanes.
	So there's a triptych j with s_j >= ceiling(4*1330/40) = 133, but also
importantly, there are no degeneracies, so the sum is exact, and sum(s_j)=5320.

	aij	C(aij,n)
	----------------
	=<2        0
	 3	   1
	 4         4
	 5	  10
	 6	  20
	 7	  35
	 8	  56
	 9        84
	----------------

	but now:

	{a1j,a2j,a3j}	s_j
	-------------------
	    {9,9,3}     169
	    {9,8,4}	144
        ----------------------< average value 133 appears here.
	    {9,7,5}	129
	    {9,6,6}	124
	    {8,8,5}     122
	    {8,7,6}     111
	    {7,7,7}	105

	So one of {9,8,3} and {9,8,4} appears.   But a couple of replies ago,
I show that {9,8,4} can't be line-free.   For similar reasons:
	4 4 1
	4 4 1
	1 1 1
can't exist.   The only way that {9,9,3} could appear is as:
	4 3 1
	4 3 1
	1 3 1

(Remember, we are free to choose the left hand side, so always choose the
most cantakerous version of 9.)

	Now, I have done some arithmetical stuff, and I believe I've proved
that there is no solution of for a=21.   I basically examine the number of
2-sets, and then have 4 equations relating the 7 frequencies of the different
triptych forms.   Two minutes iterative work with MAPLE gives the answer.   To 
confirm it, one could directly show that:
	4 3 1
	4 3 1
	1 3 1
cannot be satisfied.

Andrew