cp's OEIS Frontend

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

%I A385403 #12 Jul 03 2025 03:04:42
%S A385403 10,10,7,8,8,8
%N A385403 Minimum number of triples that cover {1..n}, such that every 2-coloring of {1..n} results in at least one monochromatic triple.
%C A385403 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.
%C A385403 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.
%H A385403 David Dewan, <a href="/A385403/a385403.txt">Mathematica program</a>
%F A385403 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}}.
%e A385403 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}.
%e A385403 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.
%e A385403 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}.
%e A385403 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.
%t A385403 (* see Links *)
%Y A385403 Cf. A111384, A383181.
%K A385403 nonn,more
%O A385403 5,1
%A A385403 _David Dewan_, Jun 27 2025
%E A385403 a(10) from _Jinyuan Wang_, Jun 28 2025