Newsgroups: sci.math
From: janee@world.std.com (Jane Eisenstein)
Subject: Seeking puzzle solution
Date: Thu, 12 Jan 1995 13:13:21 GMT

I've been trying to solve a problem which seems representative of a
more general set of problems.  I'm not very mathematical so don't know
where to begin looking beyond the net.  I'm looking for the solution
to this particular problem as well as for pointers to algorithms that
can be applied to solve such problems.
 
My problem is that given the following 13 sets of numbers:
{ 1, 5 }
{ 2, 6 }
{ 3, 7 }
{ 4, 8 }
{ 1, 5, 8 }
{ 2, 6, 8 }
{ 4, 7, 8 }
{ 1, 5, 7, 8 }
{ 3, 6, 7 }
{ 4, 6, 7, 8 }
{ 2, 5, 6, 8 }
{ 3, 5, 6, 7 }
{ 2, 4, 5, 6, 8 }
are there 10 or fewer sets of numbers from which these can be derived
by unioning no more than two together at any time?  If so, what are
these sets?
 
Playing with this problem, I've already come up with 10 sets of
numbers which meet these criteria except that in one case I must union
three together.  By the way, this problem comes from weaving where I'm
trying to design a skeleton tie up for my 8 shaft, 10 treadle loom
which will allow me to weave a complex structure without having to
hold more than two treadles down at any time.

--
Jane Eisenstein
janee@world.std.com

==============================================================================

From: prem@ix.netcom.com (Prem Sobel)
Newsgroups: sci.math
Subject: Re: Seeking puzzle solution
Date: 13 Jan 1995 12:10:02 GMT

In <D2AnE9.AKr@world.std.com> janee@world.std.com (Jane Eisenstein) 
writes: 

>My problem is that given the following 13 sets of numbers:
>{ 1, 5 }
>{ 2, 6 }
>{ 3, 7 }
>{ 4, 8 }
>{ 1, 5, 8 }
>{ 2, 6, 8 }
>{ 4, 7, 8 }
>{ 1, 5, 7, 8 }
>{ 3, 6, 7 }
>{ 4, 6, 7, 8 }
>{ 2, 5, 6, 8 }
>{ 3, 5, 6, 7 }
>{ 2, 4, 5, 6, 8 }
>are there 10 or fewer sets of numbers from which these can be derived
>by unioning no more than two together at any time?  If so, what are
>these sets?

This is a well known problem in "covering" for which there is a good
algorithm. It is used, for example, in Quine-McClusky logic 
minimization. An implication table is made, then a cover function
is formed and simplified, and the term(s) of the simplified cover 
function with the minimal set factors is(are) optimal. There is a
simplifying step when a total union set element is covered by only
one sub set, but that does not occur in this example, nor is it
necessary to use (it only save work).

I will illustrate for the above:

                         1 2 3 4 5 6 7 8
                        -----------------
>{ 1, 5 }            a | x       x
>{ 2, 6 }            b |   x       x
>{ 3, 7 }            c |     x       x
>{ 4, 8 }            d |       x       x
>{ 1, 5, 8 }         e | x       x     x
>{ 2, 6, 8 }         f |   x       x   x
>{ 4, 7, 8 }         g |       x     x x
>{ 1, 5, 7, 8 }      h | x       x   x x
>{ 3, 6, 7 }         i |     x     x x
>{ 4, 6, 7, 8 }      j |       x   x x x
>{ 2, 5, 6, 8 }      k |   x     x x x
>{ 3, 5, 6, 7 }      l |     x   x x x
>{ 2, 4, 5, 6, 8 }   m |   x   x x x   x

The cover function is:
   (a+e+h)(b+f+k+m)(c+i+l)(d+g+j+m)(a+e+h+k+l+m)(b+f+j+k+l+m)
      (c+g+h+i+j+k+l)(d+e+f+g+h+j+m)

To simplify this the axioms and theorems of Boolean Algebra are
used, but simplified to exclude negation (compliment), such as:

   T1) x=x+x
   T2) x=xx
   T3) x=x+xy
   T4) x+yz=(x+y)(x+z)
   T5) x=x(x+y)
   T6) uw+ux+vw+vx=(u+v)(w+x)

By T5, the cover function simplifies to:

   (a+e+h)(b+f+k+m)(c+i+l)(d+g+j+m)(a+e+h+k+l+m)(b+f+j+k+l+m)

Using T4 the cover function becomes:

   (a+e+h)(c+i+l)((b+f+k)(d+g+j)+m)((a+e+h)(b+f+j)+k+l+m)

Removing the inner parenthesis yields:

   (a+e+h)(c+i+l)(bd+bg+bj+fd+fg+fj+kd+kg+kj+m)
      (ab+af+aj+be+ef+ej+bh+fh+hj+k+l+m)

At this point to skip steps, we can se that the optimal solutions
(and there are more than one) will require 3 sets: m plus one of
(a+e+h) plus one of (c+i+l) giving at least 9 optimal solutions.

Prem

==============================================================================

From: hoey@aic.nrl.navy.mil (Dan Hoey)
Newsgroups: sci.math
Subject: Re: Seeking puzzle solution
Date: 13 Jan 1995 17:01:37 GMT

janee@world.std.com (Jane Eisenstein) writes:

> My problem is that given the following 13 sets of numbers:
> { 1, 5 }
> { 2, 6 }
> { 3, 7 }
> { 4, 8 }
> { 1, 5, 8 }
> { 2, 6, 8 }
> { 4, 7, 8 }
> { 1, 5, 7, 8 }
> { 3, 6, 7 }
> { 4, 6, 7, 8 }
> { 2, 5, 6, 8 }
> { 3, 5, 6, 7 }
> { 2, 4, 5, 6, 8 }
> are there 10 or fewer sets of numbers from which these can be derived
> by unioning no more than two together at any time?

This is a variant of the "set cover" problem, which is NP-complete in
the general case.  But this instance is small it could easily be done
with a program, and regular enough that it even succumbs to
hand-analysis.  In particular, we may restrict our candidate sets to
those that are realizable as intersections of the target sets, which
implies that all of the two-element sets will be included.  By
considering which of the three- and four-element target sets are
formed as unions, we find a number of ten-set solutions and a nine-set
solution:

    8,67,78, 15,26,37,48, 2568,3567

where the nonprimitive sets are realized as 158=15+8, 268=26+8,
478=48+78, 1578=15+78, 367=37+67, 4678=48+67, and 24568=48+2568.  I am
pretty sure that this nine-set solution is essentially unique, in a
sense that excludes some trivial variants.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil