1. ## Another puzzle question

Trying to solve this problem:

Mixtures are made from 18 different color paints.

Every mixture has 6 different colors.

Every combination of 3 different colors is contained in at least one mixture.

What is the minimum number of mixtures that can be formed?

Example:
If the problem was 6 different color paints, 3 different colors in each mixture
and every combination of 2 different colors is contained in at least one mixture,
then the answer would be 6:
(1-2-4), (1-3-6), (1-4-5), (2-3-5), (2-5-6), (3-4-6)

I am confused with this rule:
"every combination of 2 different colors is contained in at least one mixture".
What d'hell does that mean?
Which one is it in the example answers?

2. ## Re: Another puzzle question

"Every combination of 2 different colors is contained in at least one mixture" means that at least one of the six mixtures includes both paints 1 & 2, and at least one mixture includes both paints 1 & 3, and ... and at least one mixture includes both paints 5 & 6. Stated another way: there are $\displaystyle \dbinom 6 2 =15$ pair-wise combinations of the six colors, and all 15 appear at least once in the six mixtures.

3. ## Re: Another puzzle question

Thanks Chip.
What then is the solution to the original problem?

Looks like 41 or more...

4. ## Re: Another puzzle question

By "41" I meant:

Total = 18C3 = 816 combos.
A mixture contains 6C3 = 20 combos

CEIL(816/20) = 41 = lowest possible number of mixtures.
Actual = ?

With the given example:
Total = 6C2 = 15
A mixture contains 3C2 = 3 combos

CEIL(15/3) = 5 = lowest possible; actually takes 6

Anybody got ideas how to solve directly (not by a computer program)?

5. ## Re: Another puzzle question

Originally Posted by DenisB
If the problem was 6 different color paints, 3 different colors in each mixture
and every combination of 2 different colors is contained in at least one mixture,
then the answer would be 6:
(1-2-4), (1-3-6), (1-4-5), (2-3-5), (2-5-6), (3-4-6)
You can view this as using triangles to build a hexagon with every point connected to every other. Since each point needs to be connected to 5 others, and each triangle connects each point to 2 others, there is no single solution because every point must have a connection duplicated in the final answer, but if we can limit the duplications to one per point, we will have an optimal solution.

The given problem is perhaps rather harder to achieve - I don't know if this approach would help. Build an 18-gon using hexagons with every triangle between three points drawn in.

6. ## Re: Another puzzle question

Merci Monsieur Archie.

Got any graph theory insights that might help?

7. ## Re: Another puzzle question

Nope. Not my field.