I'm slow in math so bear with me. :)

Alright, first of all, I have a list of adjectives (in this example,
140), which must be grouped into increments of 20.  (The same for my
solution, I am only interested in 120, 140, 160, 180, 200, etc.)  For
each increment of 20, I will assign a letter:  A, B, C, etc.  So I am
dealing with 140 different adjectives, which is 7 lists of 20,
ABCDEFG.  I know that I can come up with a solution by hand where I
have uniquely paired each of the 7 (ABC, ABD, ABE, etc.)  In doing
this, I come up with 35 possible ways to combine these 7 lists.  What
I am trying to do, however, is simply to make sure that every list
gets the same exposure in as few expressions as possible.

The rules are:
- Each letter must appear the same number of times
- Each 2-way combination (AB, BD, etc.) must occur the same number of times
- I always want fewer exposures

So, in this 140, 7 list of 20, ABCDEFG scenario, I can minimize the
unique combinations to that of 7:  ABC, ADE, AFG, BDF, BEG, CEF, CDG. 
In this solution, each letter is seen the same number of times (3
times), and each combination of letters occurs only once (AB, AC,
AD.... EG, FG all pair only once).  In some solutions, each
combination may need to occur several times, BUT each combination must
always be seen the SAME number of times.

So, if this is the solution for 140, is there a rule/program/formula
for solving for 200, 220, 240?

---

Clarification of Question by demeralda-ga on 15 Sep 2004 13:20 PDT

I'm sorry, I think I forgot one very important point!

I'm trying to solve for combinations of 3.

---

Request for Question Clarification by mathtalk-ga on 15 Sep 2004 20:14 PDT

Hi, demeralda-ga:

Please see my Comment below.  If I have understood your Question
correctly, then I could probably solve most of the specific cases you
ask about.  While there isn't exactly a general rule or formula that
works for all sizes, enough is known about particular constructions to
say for what numbers of lists a solution will exist.

If you like I could post this information as an Answer, along with
specific solutions for some smallish sizes like 9 lists.

regards, mathtalk-ga

Hi, demeralda-ga:

The smallest possible designs that you're asking about (each pair of
points appears but once) are called Steiner triple systems.  Here's a
link which gives the basic result about when they exist:

[Steiner Triple System -- from MathWorld]
http://mathworld.wolfram.com/SteinerTripleSystem.html

These are special cases of balanced incomplete block designs, namely
those for which the block size is 3 and the number of times each
distinct pair appears is 1.   There are a number of notations used,
but it will be convenient to refer to these as (v,3,1)-designs.  The
general notation is:

  (v,k,?)-designs

where v = number of points (or lists in your application),
      k = size of each block (which is 3 in your application),
      ? = number of times each disinct pair appears (1 is minimal).

The theorem proved by T. P. Kirkman in 1847 is that (v,3,1)-designs
exist exactly when the remainder of v divided by 6 is either 1 or 3:

      v ? 1,3 mod 6

So the most minimal designs exist only for 7 (which you know about)
and 9 (which we'll show in a moment; it's given in the link above),
and then for every multiple of 6 added to either 7 or 9.

      v = 7,9,13,15,19,21,25,...

A solution for 9 points or lists is unique (up to rearranging the
points) and where the solution you found is called the Fano plane,
this is called an affine plane:

      {{a,b,c},{d,e,f},{g,h,i},
       {a,d,g},{b,e,h},{c,f,i},
       {a,e,i},{b,f,g},{c,d,h},
       {a,f,h},{b,d,i},{c,e,g}}

This will seem less mysterious if you compare the triples shown to the
rows, columns, and (wrap-around) diagonals of this 3x3 array:

          a  b  c
          d  e  f
          g  h  i

Thus exactly one "line" through every pair of (distinct) points.

While the solutions for v = 7,9 are essentially unique (up to
"isomorphism"), the number of nonisomorphic solutions grows rapidly. 
For v = 13 there are just two different solutions, then for v = 15
there are 80!

Here's one way to construct a solution for v = 13.  Consider these two blocks:

    {0,1,4} and {0,2,8}

Now for each non-zero "residue" modulo 13, we add (mod 13) to each
entry in both blocks to get two more blocks.  The result is a
collection of 26 "triples" that form a (13,3,1)-design:

    {{0,1,4},{0,2,8},{1,2,5},{1,3,9},{2,3,6},{2,4,10},
     {3,4,7},{3,5,11},{4,5,8},{4,6,12},{5,6,9},{5,7,0},
     {6,7,10},{6,8,1},{7,8,11},{7,9,2},{8,9,12},{8,10,3},
     {9,10,0},{9,11,4},{10,11,1},{10,12,5},{11,12,2},{11,0,6},
     {12,0,3},{12,1,7}}

This construction is an example of using the method of differences. 
What makes it tick is that every possible nonzero difference 1-12 is
produced when two values from the same one of our two "initial" blocks
are subtracted mod 13.  By virtue of this every pair of points appears
in some block.

Here's a quick sketch of a way to construct a (15,3,1)-design.  Take
the nonzero binary 4-bit words as your points:

    { 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000,
        1001, 1010, 1011, 1100, 1101, 1110, 1111 }

and define a triple of this points {X,Y,Z} whenever:

     X xor Y = Z

It's a property of the "exclusive or" operation that the above is
equivalent to saying either X xor Z = Y or Y xor Z = X, so that these
triples form well-defined subsets of size 3 (blocks).

Now let's back up and consider what our options are for other values:

    v = 6, 8, 10, 11, 12

For some general results on balanced incomplete block designs, see the
introductory sections of:

[On the Existence of (v, 5, 1)-BIBDs by Clayton Smith]
http://www.argilo.net/papers/bibd.pdf

In particular Lemma 3 tells us that each point in a (v,k,?)-design
will appear exactly:
            (v - 1)
     r =  ? -------
            (k - 1)

times, ie. a whole number of times (the same number for each point),
and will require this many blocks (the number of points, times how
many appearance each makes, divide by the size of a block):

     b =  vr/k

Now for v = 6 and k = 3, we need ? even to get a whole number.  The
smallest possibility is ? = 2, so that each point appears r = 5 times.
 The number of blocks is then b = 6*5/3 = 10.

One such (6,3,2)-design is this collection of ten blocks:

     {{a,b,c},{a,c,d},{a,d,e},{a,e,f},{a,b,f},
      {b,d,e},{b,c,e},{b,f,d},{c,d,f},{c,e,f}}

in which you can check each symbols appears five times and each
distinct pair twice.

That's still better than the complete block design on v = 6 points,
which requires 20 blocks.

However for v = 8 we cannot do better (with k = 3) than taking the
complete block design.  To see why, first look at the relationship on
number of times r that each point appears:

            (v - 1)
     r =  ? -------  = ? * (7/2)
            (k - 1)

so again ? will need to be even.  But also count the number of blocks:

     b = vr/k = r * (8/3)

which implies that r must be divisible by 3.  That requires (from
above) that ? is divisible by 3 as well as 2, i.e. ? must be at least
6.  And ? = 6 gives us just the 56 blocks of the complete block
design.

For v = 10 we already know that we need at least ? = 2.  The following
example shows this is possible, albeit using a bit different technique
than what you might have expected!

So far our examples have not used the same _triple_ more than once. 
In other words all our blocks were different.  This next example of a
(10,3,2)-design contains some _repeated_ blocks.  However every
distinct pair appears just twice among all the 30 blocks:

     {{1,2,3},{1,2,4},{1,3,4},{2,3,4},
      {1,5,6},{1,5,7},{1,6,7},{5,6,7},
      {1,8,9},{1,8,10},{1,9,10},{8,9,10},
      {2,5,8},{2,5,8},{2,6,9},{2,6,9},
      {2,7,10},{2,7,10},{3,5,10},{3,5,10},
      {3,6,8},{3,6,8},{3,7,9},{3,7,9},
      {4,5,9},{4,5,9},{4,6,10},{4,6,10},
      {4,7,8},{4,7,8}}

Despite the repeated blocks this is considerable better than the
complete block design, which for v = 10 requires 120 blocks.  For the
construction of this particular example, see here:

[Pairwise balanced designs]
http://www.math.mun.ca/~davidm/4341/pbd.pdf

The analysis we did before by counting how many times r that each
point appears and how many blocks b there are (which must both be
whole numbers) tells us this about the remaining cases v = 11,12:

If v = 11, then ? must be at least 3.

If v = 12, then ? must be at least 2.

I'll need to do some further research to find designs of this types however.

regards, mathtalk-ga

---

Clarification of Answer by mathtalk-ga on 01 Oct 2004 07:55 PDT

Hi, demeralds-ga:

Here are a few more designs in which you may have an interest.  I've
labelled the points beginning with 0.  These are among a large number
of 2-designs cataloged at this Web site:

[Database at DesignTheory.org]
http://www.designtheory.org/database/

The first design has triples from 10 points in which every pair
appears twice (and each point is used 9 times), but unlike my earlier
example, this one has no repeated "blocks" (all the blocks are
different):

{ 0, 1, 2 } { 0, 1, 3 } { 0, 2, 3 } { 0, 4, 5 } { 0, 4, 6 } 
{ 0, 5, 7 } { 0, 6, 8 } { 0, 7, 9 } { 0, 8, 9 } { 1, 2, 3 } 
{ 1, 4, 5 } { 1, 4, 9 } { 1, 5, 8 } { 1, 6, 7 } { 1, 6, 8 } 
{ 1, 7, 9 } { 2, 4, 6 } { 2, 4, 9 } { 2, 5, 7 } { 2, 5, 8 } 
{ 2, 6, 7 } { 2, 8, 9 } { 3, 4, 7 } { 3, 4, 8 } { 3, 5, 6 } 
{ 3, 5, 9 } { 3, 6, 9 } { 3, 7, 8 } { 4, 7, 8 } { 5, 6, 9 } 

Here's a design on 11 points in which every pair appears 3 times among
the "blocks" of three (triples), and no repeats among the blocks:

{ 0, 1, 3 } { 0, 1, 4 } { 0, 1, 7 } { 0, 2, 5 } { 0, 2, 7 } 
{ 0, 2,10 } { 0, 3, 9 } { 0, 3,10 } { 0, 4, 5 } { 0, 4, 6 } 
{ 0, 5, 9 } { 0, 6, 8 } { 0, 6,10 } { 0, 7, 8 } { 0, 8, 9 } 
{ 1, 2, 4 } { 1, 2, 5 } { 1, 2, 8 } { 1, 3, 6 } { 1, 3, 8 } 
{ 1, 4,10 } { 1, 5, 6 } { 1, 5, 7 } { 1, 6,10 } { 1, 7, 9 } 
{ 1, 8, 9 } { 1, 9,10 } { 2, 3, 5 } { 2, 3, 6 } { 2, 3, 9 } 
{ 2, 4, 7 } { 2, 4, 9 } { 2, 6, 7 } { 2, 6, 8 } { 2, 8,10 } 
{ 2, 9,10 } { 3, 4, 6 } { 3, 4, 7 } { 3, 4,10 } { 3, 5, 8 } 
{ 3, 5,10 } { 3, 7, 8 } { 3, 7, 9 } { 4, 5, 7 } { 4, 5, 8 } 
{ 4, 6, 9 } { 4, 8, 9 } { 4, 8,10 } { 5, 6, 8 } { 5, 6, 9 } 
{ 5, 7,10 } { 5, 9,10 } { 6, 7, 9 } { 6, 7,10 } { 7, 8,10 } 

Finally here is a design on 12 blocks in which every pair appears
twice, but this design does have repeated blocks:

{ 0, 1, 2 } { 0, 1,11 } { 0, 2, 7 } { 0, 3, 6 } { 0, 3, 9 }
{ 0, 4, 8 } { 0, 4, 8 } { 0, 5, 7 } { 0, 5,10 } { 0, 6, 9 }
{ 0,10,11 } { 1, 2, 3 } { 1, 3, 8 } { 1, 4, 7 } { 1, 4,10 }
{ 1, 5, 9 } { 1, 5, 9 } { 1, 6, 8 } { 1, 6,11 } { 1, 7,10 }
{ 2, 3, 4 } { 2, 4, 9 } { 2, 5, 8 } { 2, 5,11 } { 2, 6,10 }
{ 2, 6,10 } { 2, 7, 9 } { 2, 8,11 } { 3, 4, 5 } { 3, 5,10 }
{ 3, 6, 9 } { 3, 7,11 } { 3, 7,11 } { 3, 8,10 } { 4, 5, 6 }
{ 4, 6,11 } { 4, 7,10 } { 4, 9,11 } { 5, 6, 7 } { 5, 8,11 }
{ 6, 7, 8 } { 7, 8, 9 } { 8, 9,10 } { 9,10,11 }

regards, mathtalk-ga

mathtalk is the best, I hope I can bug him for more answers in the future!

Does the number 20 actually have anything to do with this problem? You
talk about increments of 20 but when you list you give your list of
combinations ABC, ADE, ... it doesn't seem like 20 has anything to do
with it. It seems we're just looking at combinations from a set of 7
letters. Is this correct?

In the example that was satisfactorily "solved", there were 7 sets of
20.  Yes, 20 must always be used.  Therefore, when I want to solve for
160, I'll have 8 sets of 20, meaning ABCDEFGH, and still trying to
solve for a 3 letter combination (ABC, ABD, ABE...FGH, so forth).  I
want to be able to arrive at this solution for any time I add another
increment of 20.  Somehow I doubt there is, but if I could even make
it to 240 (which is typically the largest data set I'm working with),
it would be good.  So for 240, I'll have 12 sets of 20, ABCDEFGHIJKL,
and still trying to find the minimum number of outcomes of three
letter combinations, and still satisfying the earlier stated rules.

I hope that clarifies a bit.

Hi, demeralda-ga:

I think the point sigfpe-ga is making is the same thought that struck
me in reading your "solution" to the 140 adjectives case.  The real
constraints appear to have to do with using 7 lists, not 140
adjectives.  You decided to use 20 as the size of a list, so clearly
the factor of 20 has a significance to you.  But in terms of the
properties of the solution, what you are describing is known in the
"math biz" as the Fano plane (or configuration):  an arrangement of
seven points into seven "lines", with each "line" containing three
points and each point lying on three "lines", and any two "lines"
intersecting in exactly one point.

Your Question can then be interpreted to ask if there are similar
configurations involving 6, 8, 9, 10, etc. lists where a list plays
the role of a point in such designs.

Letting each list (point) be represented by a different symbol, if you
wish.  Each "combination of 3" is a subset of size 3 of this set of
symbols (lists or points).  Taking all possible combinations of (say)
seven things 3 at a time gives 35, as you noticed.  This is known as a
"complete block design" because it includes all possible combinations.
 Sometimes, as you've seen, it is possible to come up with a smaller
collection of combinations which satisfies the conditions:

  1) every symbol (list or point) appears the same number of times

  2) every pair of distinct symbols appears the same number of times

These are known as pairwise-balanced incomplete block designs, often
abbreviated BIBD.  Many generalizations of these kinds of designs have
been proposed and studied, and they play an important role in the
design of experiments which involve more than one variable or
"factor".

There is no rule or formula which simply gives one all the possible
solutions, but for the fairly small numbers you are considering the
solutions are all known.  This area of mathematics (generally
speaking) is combinatorics.

regards, mathtalk-ga

I'd say that is pretty much an answer.  Yes, you're right, the 20 is
irrelevant, what you are saying is correct, the number of sets (6, 7,
8... up to 12) and their solution is all I'm really interested in. 
You say for such small numbers, the combinatorics already has the
answer out there somewhere.  Where would I find a decent reference
source for this?

Thank you, you clarified what I could not.

Sorry, I missed your clarification question from above.  Yes, if you
would post it as the answer (up to 9, as you stated) that would be
fabulous.  If you can do 10-12, which is my uppermost limit, I'd be
happy to pay extra, since I haven't a clue how much work it takes. 
Just let me know.

Thanks a ton, you sure helped!

Let me know if you discover 11 and 12... your example for 10 already
saved me a ton of headache.

I'll be happy to post it as a new question, if that helps.  I'll put
the same price on it, too :)

Thanks again!

Thank you so much for remembering my problem!  Now I'm *really*
impressed!  Please let me know if there's a way that I can offer you
an additional tip, or if I should post it as a new question so you can
answer.  I'm very grateful, indeed.

demeralda-ga