From: Rob Pratt <robpra@wnt.sas.com>
Subject: Re: Combination Algorithm without brut force - Combine 4's into least 6's
Date: Thu, 15 Feb 2001 10:16:37 -0500
Newsgroups: sci.math
Summary: Using integer programming to solve set covering problem

On Thu, 15 Feb 2001 12:03:01 +1000, "aufempenmss"
<aufempen@modemss.brisnet.org.au> wrote:

>Hello
>What is the algorithm  or principle to combine all the combinations of 4s
>into
>the smallest combination of 6s from a range of 10 consecutive numbers?
>What is the combinatorix formula for the least combination of 6s?
>Here is the data
>1) All the combinations of 4s in a range of 10 numbers
>  1           1  2  3  4
> 2             1  2  3  5
> 3             1  2  3  6
>...
>The full result of all combinations of 4s has
> been truncated to save space on this postingl
>.....
> 208           6  7  9  10
> 209           6  8  9  10
> 210           7  8  9  10
>
>2) The result for combining all 4s into the least number
>of 6s is 21 combinations of 6s:
>But how do you set the algorithm or explain how it works
>without using brut force?
>1          1  2  3  4  5  6
>2          1  2  3  4  7  8
>3          1  2  3  4  9  10
>4          1  2  4  5  7  10
>5          1  2  4  6  8  9
>6          1  2  5  6  7  9
>7          1  2  5  6  8  10
>8          1  3  5  6  7  8
>9          1  3  5  6  9  10
>10       1  3  7  8  9  10
>11       1  4  5  8  9  10
>12       1  4  6  7  9  10
>13       2  3  4  5  8  10
>14       2  3  4  6  7  9
>15       2  3  5  7  9  10
>16       2  3  6  8  9  10
>17       2  4  5  7  8  9
>18       2  4  6  7  8  10
>19       3  4  5  6  7  10
>20       3  4  5  6  8  9
>21       5  6  7  8  9  10
>
>Brut force = Obtaining these numbers by designing my computer program
>to number crunched all possibilities.
>
>3)Any explanation, containing combination, permutation, group mathematics
>will
>be appreciated. Please post to aufempen@modemmss.brisnet.org.au
>

Let me attempt a clarification of the problem.

The poster wants to find a minimum cardinality collection of 6-subsets
of {1, 2, ..., 10} such that every 4-subset of {1, 2, ..., 10} is
contained in at least one of the 6-subsets.

This problem can be formulated as a set covering problem and solved
via integer programming (or some specialized set-covering code).  We
have a binary variable x_S for each 6-subset S.  We want to

minimize sum x_S (sum over all 6-subsets S of {1, 2, ..., 10})
subject to 
A x >= e
x_S in {0, 1} for all S,

where e is a column vector of all ones and 
A(i,j) = 1 if 4-subset i is contained in 6-subset j, 0 otherwise.

Since each 6-subset covers binom(6,4) 4-subsets, and we need to cover
binom(10,4) 4-subsets, a lower bound for the number of 6-subsets
required is binom(10,4) / binom(6,4) = 210 / 15 = 14.