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

ja...@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