login
Minimal number of monochromatic three-term arithmetic progressions that a two-coloring of {1,...,n} can contain.
1

%I #21 Jun 02 2014 01:34:12

%S 0,0,0,0,0,0,0,0,1,1,2,2,3,4,5,6,7,8,10,12,14,16,18,20,22,24,26,28,31,

%T 34,37,40,43,46,49,52,55,58,62,66,70,74,78,82,86

%N Minimal number of monochromatic three-term arithmetic progressions that a two-coloring of {1,...,n} can contain.

%C a(9) = 1 is the well-known fact that the van der Waerden number for two colors and three-term arithmetic progressions is 9.

%C From _Rob Pratt_, May 27 2014: (Start)

%C By ignoring the last element, we see that a(n) >= a(n-1).

%C The general problem for k terms and r colors can be solved by using integer programming, with binary decision variables x[i,c] = 1 if element i receives color c and 0 otherwise, y[i,d] = 1 if arithmetic progression (i,i+d,...,i+(k-1)d) is monochromatic and 0 otherwise. The constraints are sum {c in 1..r} x[i,c] = 1 for all i in 1, …, n and sum {j=0 to k-1} x[i+j*d,c] - k + 1 <= y[i,d] for all i, d, c. The objective is to minimize sum {i, d} y[i,d].

%C Upper bounds are a(46) <= 90, a(47) <= 95, a(48) <= 100, a(49) <= 104, a(50) <= 110.

%C (End)

%e a(8) = 0 because we can two color {1,...,8} by 11001100 so that there are no monochromatic three-term arithmetic progressions.

%Y Cf. A005346, A121386.

%K nonn,more

%O 1,11

%A _Steve Butler_, Jul 26 2006

%E a(35)-a(45) from _Rob Pratt_, May 27 2014