A385403 Minimum number of triples that cover {1..n}, such that every 2-coloring of {1..n} results in at least one monochromatic triple.

10, 10, 7, 8, 8, 8

Offset: 5

Author

David Dewan, Jun 27 2025

Keywords

• nonn
• more

Comments

There is no solution for n<=4. For example for n=4, the coloring {1=red, 2=red, 3=blue, 4=blue} prevents any monochromatic triple.

This sequence gives the minimum number of triples covering {1..n} that force a monochromatic triple under any 2-coloring. For the contrasting maximum number of triples covering {1..n} that can avoid monochromatic triples under some 2-coloring, see A111384.

Examples

			a(6)=10. For example, these ten triples {{1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,6}, {1,5,6}, {2,3,6}, {2,4,5}, {3,4,5}} cover {1..6} and have at least one monochromatic triple for each of the 2^6 = 64 different 2-colorings of {1..6}.
The minimum is 10 because for each of the 167,960 different groups of 9 triples from the C(6,3) = 20 possible triples, there exists a 2-coloring of {1..6} that results in no monochromatic triple.
a(7)=7. For example, these seven triples {{1,2,3}, {1,4,5}, {1,6,7}, {2,4,6}, {2,5,7}, {3,4,7}, {3,5,6}} cover {1..7} and have at least one monochromatic triple for each of the 2^7 = 128 different 2-colorings of {1..7}.
The minimum is 7 because for each of the 1,623,160 different groups of 6 triples from the C(7,3) = 35 possible triples, there exists a 2-coloring of {1..7} that results in no monochromatic triple.
		

Links

• David Dewan, Mathematica program

Crossrefs

Cf. A111384, A383181.

Programs

Mathematica

(* see Links *)

Formula

For n>=7, a(n) <= 7+ceiling((n-7)/3) by extending any minimal 7-triple solution on {1..7} with ceiling((n-7)/3) additional triples covering {8..n}. For example, a(10) <= 8 with {{1,2,3}, {1,4,5}, {1,6,7}, {2,4,6}, {2,5,7}, {3,4,7}, {3,5,6}, {8,9,10}}.

Extensions

a(10) from Jinyuan Wang, Jun 28 2025