3-color Schur numbers

3-color Schur numbers L. Boza, J.M. Marín, M.P. Revuelta, M.I. Sanz * Departamento de Matemática Aplicada I, Universidad de Sevilla, Avenida Reina Mercedes s/n, C.P. 41012, Sevilla, Spain Keywords: Schur numbers Sum-free sets n-coloring Monochromatic solution a b s t r a c t Let k ≥ 3 be an integer, the Schur number Sk(3) is the least positive integer, such that for every 3-coloring of the integer interval [1, Sk(3)] there exists a monochromatic solution to the equation x1 + · · · + xk = xk+1, where xi, i = 1, . . . , k need not be distinct. In 1966, a lower bound of Sk(3) was established by Znám (1966). In this paper, we determine the exact formula of Sk(3) = k3 + 2k2 − 2, finding an upper bound which coincides with the lower bound given by Znám (1966). This is shown in two different ways: in the first instance, by the exhaustive development of all possible cases and in the second instance translating the problem into a Boolean satisfiability problem, which can be handled by a SAT solver. 1. Introduction For integers a≤b, we shall denote [a,b]the integer interval. A set Aof integers is said to be k-sum-free if it contains no k+1 elements x1,x2, . . . , xk+1∈Asatisfying x1+···+xk=xk+1, where xi,i=1, . . . , kare not necessarily distinct. Schur [11] in 1916 proved that, given a positive integer n≥1, there exists a greatest positive integer S2(n), with the property that the integer interval [1,S2(n)−1]can be partitioned into nsets which are 2-sum-free. These numbers S2(n) are called the Schur numbers. In terms of coloring, the Schur number S2(n) [11] is the least positive integer such that for every n-coloring of [1,S2(n)]: ∆: [1,S2(n)] −→ {1,2, . . . , n} there exists a monochromatic solution to the equation x1+x2=x3, where x1,x2and x3need not be distinct. Schur numbers are known only for a few small values of n. For instance, one has S2(1) =2 and S2(2) =5. A partition of [1,4]into 2 sum-free sets is provided by [1,4] = {1,4}⊔{2,3}. Two more exact values of S2(n) are currently known, namely S2(3) =14 and S2(4) =45.While the value S2(3) can still be settled by hand, the value S2(4) [2] relies on an exhaustive computer search. Recently S2(6) =161 has been obtained by Heule [6]. In 2000, Fredricksen and Sweet [4] obtained S2(6) ≥537 and S2(7) ≥1681 by considering symmetric sum-free partitions. Schur proved for every n≥1, the following lower and upper general bounds [11]: (3n+1)/2≤S2(n)≤ ⌊n!e⌋. Furthermore, he established S2(n)≥3S2(n−1) −1. *Corresponding author. E-mail addresses: [email protected] (L. Boza), [email protected] (J.M. Marín), [email protected] (M.P. Revuelta), [email protected] (M.I. Sanz). In 1933, Rado [8] obtained in particular the following generalization: given two positive integers, nand k≥2, there exists a greatest positive integer, Sk(n), such that the integer interval [1,Sk(n)−1]can be partitioned into nsets which are k-sum-free. In 1966, Znám [12] established a lower bound on the numbers Sk(n): Sk(n)≥k−1 k((k+1)n−1) +1.(1) An upper bound given in 1955 [5] was improved by Irving [7] in 1973: Sk(n)≤⌊k−1 √e n!(k−1)n⌋. In 1982, Beutelspacher and Brestovansky [3] proved that for two k-sum-free sets the following equality is verified: Sk(2) =k2+k−1,k≥2. Although there has been progress in establishing new bounds in the last years, there have been no advances for over 35 years in the calculation of exact formulas. In 2010 [9], the last author obtained the exact value of S3(3) =43.Independently, Ahmed and Schaal [1] in 2016 obtain the values of Sk(3) for k=3,4,5 and also present a conjecture that coincides with the exact formula of Sk(3) given in this paper. We determine the exact formula of Sk(3) =k3+2k2−2 for all k≥3, finding an upper bound that coincides with the lower bound given by Znám [12]. This is shown in two different ways: first, by the exhaustive development of all possible cases; and second by translating the problem into a Boolean satisfiability problem, which can be handled by a SAT solver [10]. 2. Exact formula of Sk(3) We now prove that the exact formula of Sk(3) =k3+2k2−2. The lower bound was established in 1966 [12], so we focus on the upper bound. We shall prove that for every 3-coloring of the integer interval [1,k3+2k2−2], there exists a monochromatic solution to the equation: x1+ ··· + xk=xk+1.We start, by analyzing 27 cases and achieving a contradiction in each of them. The proof consists in checking in all 27 cases that all the coloring obtained have monochromatic solutions. We shall prove that for every 3-coloring: ∆: [1,k3+2k2−2] −→ {1,2,3} there exists a monochromatic solution to the equation x1+··· +xk=xk+1. Let sets A1,A2and A3be such that ∆(A1)=1, ∆(A2)=2 and ∆(A3)=3, so that [1,k3+2k2−2] = A1⊔A2⊔A3. Given a subset X⊆ [1,k3+2k2−2], we denote f(X)=X∔··· ∔X= {x1+··· +xk|x1, . . . , xk∈X}∩[1,k3+2k2−2]. By hypothesis on ∆, for 1 ≤i≤3, we have Ai∩f(Ai)= ∅.(2) The proof rests on the following claims, which are both direct consequences of (2). For all integers i,j,ksuch that {i,j,k} = {1,2,3}, we have •Claim I. f(Ai)∩f(Aj)⊆Ak. •Claim II. f(Ai)∩f(Aj)∩f(Ak)= ∅. Without loss of generality we may assume that ∆(1) =1 and ∆(k)=2. To avoid the monochromatic solution in A2, since k    k+··· +k=k2, we consider two cases depending on the color of k2.These two cases are discussed in Sections 3and 4. We begin with a scheme of the cases to study, to facilitate the exhaustive development of this proof. ∆(k2)=1 ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ∆(k2+k−1) =2⎧ ⎨ ⎩ ∆(k2+k)=1 ∆(k2+k)=2 ∆(k2+k−1) =3 ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ∆(k3)=2 ∆(k3)=3 ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ∆(k3+k2−k)=1⎧ ⎨ ⎩ ∆(k+1) =2 ∆(k+1) =3 ∆(k3+k2−k)=2 ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ ∆(k3+2k2−2k)=1 ∆(k3+2k2−2k)=3⎧ ⎨ ⎩ ∆(2k−1) =1 ∆(2k−1) =2 ∆(k2)=3 ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ∆(k3)=1 ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ∆(k3+k−1) =2 ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ∆(k+1) =2 ∆(k+1) =3 ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ∆(k3+k2+k−2) =2⎧ ⎨ ⎩ ∆(k2−k+1) =2 ∆(k2−k+1) =3 ∆(k3+k2+k−2) =3⎧ ⎨ ⎩ ∆(k2+k−1) =1 ∆(k2+k−1) =2 ∆(k3+k−1) =3 ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ∆(k2+k−1) =1⎧ ⎨ ⎩ ∆(k2+2k−2) =2 ∆(k2+2k−2) =3 ∆(k2+k−1) =2 ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ ∆(2k2−1) =1⎧ ⎨ ⎩ ∆(2k−1) =1 ∆(2k−1) =3 ∆(2k2−1) =3 ∆(k3)=2 ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ∆(k2+k)=1 ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ∆(k3+k2−k)=1⎧ ⎨ ⎩ ∆(k2+k−1) =2 ∆(k2+k−1) =3 ∆(k3+k2−k)=3 ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ ∆(k3−k+1) =2⎧ ⎨ ⎩ ∆(k+1) =2 ∆(k+1) =3 ∆(k3−k+1) =3 ∆(k2+k)=3⎧ ⎨ ⎩ ∆(k2+k−1) =2 ∆(k2+k−1) =3 3. Assigning the color 1 to k2 We suppose ∆(k2)=1, therefore A1⊇ {1,k2},A2⊇ {k}. We have that k2+ k−1    1+··· +1=k2+k−1 so to avoid a monochromatic solution in A1, we assume that ∆(k2+k−1) =2 or ∆(k2+k−1) =3. 3.1. Assigning the color 2 to k2+k−1 We consider ∆(k2+k−1) =2 so that A1⊇ {1,k2}and A2⊇ {k,k2+k−1}.As 1 +(k−1) ×(k+1) =k2would be a monochromatic solution in A1and 1 ×k+(k−1) ×(k+1) =k2+k−1 would be a monochromatic solution in A2, applying Claim I produces k+1∈A3.To avoid k×(k+1) =k2+kbeing a monochromatic solution in A3, we assume that ∆(k2+k)=1 or ∆(k2+k)=2. Case 1: A1⊇ {1,k2,k2+k},A2⊇ {k,k2+k−1},A3⊇ {k+1}. Consider 1 +(k−1) ×(k2+k)=k3−k+1 and k+(k−1) ×(k2+k−1) =k3−k+1 and apply Claim I to get ∆(k3−k+1) =3. Now, one of the following equations must be monochromatic k2+(k−1)×(k2+k)=k3+k2−k;k3+k2−k=k×(k2+k−1); and k3+k2−k=k3−k+1+(k−1) ×(k+1). We show k3+k2−k∈ Ai,i=1,2,3, for otherwise k3+k2−k⊆Ai∩f(Ai), a contradiction. Case 2: A1⊇ {1,k2},A2⊇ {k,k2+k−1,k2+k},A3⊇ {k+1}. We have k×k2=k3and k+(k−1) ×(k2+k)=k3so we deduce that ∆(k3)=3.Apply Claim I to k2+k−1+(k−1) ×(k2+k)=k3+k2−1 and k3+(k−1) ×(k−1) =k3+k2−1 to get ∆(k3+k2−1) =1. Since (2k2−1) +(k−1) ×k2=k3+k2−1 and k2+k−1+(k−1) ×k=2k2−1, applying Claim I so we deduce that ∆(2k2−1) =3. We now obtain a contradiction by noting that one of the following equations must be monochromatic, 1 +(3k2−2) + (k−2) ×k2=k3+k2−1; 3k2−2=2×(k2+k−1) +(k−2) ×k; and 3k2−2=2k2−1+(k−1) ×(k+1).We show 3k2−2∈ Ai,i=1,2,3, for otherwise 3k2−2⊆Ai∩f(Ai). 3.2. Assigning the color 3 to k2+k−1 We consider ∆(k2+k−1) =3,so that A1⊇ {1,k2},A2⊇ {k}and A3⊇ {k2+k−1}.We have k×k2=k3, we assume ∆(k3)∈ {2,3}. Case 1: A1⊇ {1,k2},A2⊇ {k,k3}and A3⊇ {k2+k−1}.Apply Claim I to k3+(k−1) ×k=k3+k2−kand k×(k2+k−1) =k3+k2−k, to get ∆(k3+k2−k)=1.Since k2+(k−1)×(k2+k)=k3+k2−kand k+(k−1)×(k2+k)=k3, applying Claim I we deduce ∆(k2+k)=3.Consider 1 +(k−1) ×(k+1) =k2and k×(k+1) =k2+kand apply Claim I to get ∆(k+1) =2. We now obtain a contradiction by noting that one of the following equations must be monochromatic, k3+k2−k+(k− 1) ×1=k3+k2−1; k3+(k−1) ×(k+1) =k3+k2−1; and k2+k−1+(k−1) ×(k2+k)=k3+k2−1.We show k3+k2−1∈ Ai,i=1,2,3, for otherwise k3+k2−1⊆Ai∩f(Ai). Case 2: A1⊇ {1,k2},A2⊇ {k}and A3⊇ {k2+k−1,k3}.We have k×(k2+k−1) =k3+k2−kto avoid the monochromatic solution in A3, we consider ∆(k3+k2−k)∈ {1,2}. Case 2.1: A1⊇ {1,k2,k3+k2−k},A2⊇ {k}and A3⊇ {k2+k−1,k3}.We have 1 +(k−1) ×(k+1) =k2, so to avoid a monochromatic solution in A1, we assume ∆(k+1) ∈ {2,3}. Case 2.1.1: ∆(k+1) =2.Apply Claim I to k2+(k−1)×(k2+k)=k3+k2−kand k×(k+1) =k2+kto get ∆(k2+k)=3. Since (k3+k2−k)+(k−1)×1=k3+k2−1 and (k2+k−1)+(k−1)×(k2+k)=k3+k2−1, we have ∆(k3+k2−1) =2. After applying Claim I to 1 +(k−1) ×(k2+2k+1) =k3+k2−1 and k+(k−1) ×(k2+2k+1) =k3+k2−1 we obtain ∆(k2+2k+1) =3. We now obtain a contradiction by noting that one of the following equations must be monochromatic, k3+k2−k+(k− 2)×1+k2=k3+2k2−2; (k3+k2−1)+(k−1)×(k+1) =k3+2k2−2; and (k2+k−1)+(k−1)×(k2+2k+1) =k3+2k2−2. We show k3+2k2−2∈ Ai,i=1,2,3, for otherwise k3+2k2−2⊆Ai∩f(Ai). Case 2.1.2: ∆(k+1) =3.Consider k2+(k−1) ×(k2+k)=k3+k2−kand k×(k+1) =k2+kand apply Claim I to get ∆(k2+k)=2.We have 2 ×k2+(k−2) ×1=2k2+k−2 and (k2+k−1) +(k−1) ×(k+1) =2k2+k−2 so we deduce that ∆(2k2+k−2) =2.Since (k3+k2−k)+(k−1) ×1=k3+k2−1 and k3+(k−1) ×(k+1) =k3+k2−1 applying Claim I we have ∆(k3+k2−1) =2.Once we apply Claim I to k2+(k3+k2−k)+(k−2) ×1=k3+2k2−2 and (2k2+k−2) +(k−1) ×(k2+k)=k3+2k2−2 we obtain ∆(k3+2k2−2) =3. We now obtain a contradiction by noting that one of the following equations must be monochromatic, 1+(k−1)×(k2+ 2k+1) =k3+k2−k; 1 ×k+(k−1) ×(k2+2k+1) =k3+k2−1; and (k2+k−1) +(k−1) ×(k2+2k+1) =k3+2k2−2. We show k2+2k+1∈ Ai,i=1,2,3, for otherwise k2+2k+1⊆Ai∩f(Ai). Case 2.2: A1⊇ {1,k2},A2⊇ {k,k3+k2−k}and A3⊇ {k2+k−1,k3}.We have (k3+k2−k)+(k−1) ×k=k3+2k2−2k, so to avoid a monochromatic solution in A1, we assume ∆(k3+2k2−2k)∈ {1,3}. Case 2.2.1: ∆(k3+2k2−2k)=1.Apply Claim I to k2+(k−1)×(k2+2k)=k3+2k2−2kand k+(k−1)×(k2+2k)=k3+k2−k to get ∆(k2+2k)=3.Since (k3+2k2−2k)+(k−1)×1=k3+2k2−k−1 and (k2+k−1)+(k−1)×(k2+2k)=k3+2k2−k−1, applying Claim I we deduce ∆(k3+2k2−k−1) =2.We have 1+(k−1)×(k+1) =k2and (k3+k2−k)+(k−1)×(k+1) = k3+2k2−k−1 so we obtain ∆(k+1) =3.Once we apply Claim I to 2 ×k2+(k−2) ×1=2k2+k−2 and (k2+k−1) +(k−1) ×(k+1) =2k2+k−2 we deduce ∆(2k2+k−2) =2.Since k×(k2+2k−2) =k3+2k2−2kand (k2+2k−2)+(k−1)×k=2k2+k−2 we have ∆(k2+2k−2) =3.Consider (2k2+k−2)+(k−1)×(k2−2) =k3+k2−k and (k2+2k−2) +(k−1) ×(k2−2) =k3and apply Claim I to get ∆(k2−2) =1.Since 2 ×1+(k−2) ×(k+2) =k2−2 and k×(k+2) =k2+2kwe deduce ∆(k+2) =2. We now obtain a contradiction by noting that one of the following equations must be monochromatic, k2+(k−1) × (k2−2) =k3−2k+2; (k3−2k+2) +(k−1) ×(k+2) =k3+k2−k; and 2 ×(k+1) +(k−2) ×(k2+2k)=k3−2k+2. We show k3−2k+2∈ Ai,i=1,2,3, for otherwise k3−2k+2⊆Ai∩f(Ai). Case 2.2.2: ∆(k3+2k2−2k)=3.We have (2k−1) +(k−1) ×(k2+k−1) =k3, so to avoid a monochromatic solution in A3, we assume ∆(2k−1) ∈ {1,2}. 1. ∆(2k−1) =1.We have (k2−k+1) +(k−1) ×1=k2, we assume ∆(k2−k+1) ∈ {2,3}. (a) ∆(2k−1) =1.Consider (2k−1)+(k−1)×(k−1) =k2and k+(k−1)×(k−1) =k2−k+1 and apply Claim I to get ∆(k−1) =3.Since k×(2k−1) =2k2−kand (k2+k−1)+(k−1)×(k−1) =2k2−kapplying Claim I we obtain ∆(2k2−k)=2. We have k+(k−1)×2k=2k2−kand k3+(k−1)×2k=k3+2k2−2kso we deduce that ∆(2k)=1.Since 1+(k−1)×(k+1) =k2and (k2−k+1)+(k−1) ×(k+1) =2k2−k, we have ∆(k+1) =3. Apply Claim I to (2k−1) +(k−1) ×2k=2k2−1 and (2k2−1) +(k−1) ×(k2+k−1) =k3+2k2−2kto get ∆(2k2−1) =2.Consider 1 +(k−1) ×2k=2k2−2k+1 and (k2−k+1) +(k−1) ×k=2k2−2k+1 and apply Claim I to obtain ∆(2k2−2k+1) =3. We now obtain a contradiction by noting that one of the following equations must be monochromatic, k2+(k− 1) ×2k=3k2−2k; (2k2−k)+(k−1) ×k=3k2−2k; and (2k2−2k+1) +(k−1) ×(k+1) =3k2−2k. We show 3k2−2k∈ Ai,i=1,2,3, for otherwise 3k2−2k⊆Ai∩f(Ai).. (b) ∆(2k−1) =1.Apply Claim I to 1 +(k−1) ×2=2k−1 and (k2−k+1) +(k−1) ×2=k2+k−1, to get ∆(2) =2.Since k×2=2kand k3+(k−1) ×2k=k3+2k2−2kwe have ∆(2k)=1.Once we apply Claim I to (2k−1) +(k−1) ×2k=2k2−1 and (2k2−1) +(k−1) ×(k2+k−1) =k3+2k2−2kwe obtain ∆(2k2−1) =2. We now obtain a contradiction by noting that one of the following equations must be monochromatic, 1 +(k− 1) ×2k=2k2−2k+1; (2k2−2k+1) +(k−1) ×2=2k2−1; and (2k2−2k+1) +(k−1) ×(k2−k+1) =k3. We show 2k2−2k+1∈ Ai,i=1,2,3, for otherwise 2k2−2k+1⊆Ai∩f(Ai). 2. ∆(2k−1) =1.Apply Claim I to 2 ×(2k−1) +(k−2) ×k=k2+2k−2, and k×(k2+2k−2) =k3+2k2−2k, to get ∆(k2+2k−2) =1.Since (2k−1)+(k−1)×(k2+2k−1) =k3+k2−kand (k2+k−1)+(k−1)×(k2+2k−1) =k3+2k2−2k, we have ∆(k2+2k−1) =1.We have (k2+2k−2) +(k−1) ×(k2+2k−1) =k3+2k2−k−1 and (k3+k2−k)+(2k−1) +(k−2) ×k=k3+2k2−k−1 apply so we deduce ∆(k3+2k2−k−1) =3. Since k+(k−1)×(k2+2k)=k3+k2−kand (k2+k−1)+(k−1)×(k2+2k)=k3+2k2−k−1, we obtain ∆(k2+2k)=1. We have 2×k2+(k−2)×1=2k2+k−2 and (2k2+k−2)+(k−1)×(k2+k−1) =k3+2k2−k−1 applying Claim I we deduce ∆(2k2+k−2) =2. Since (2k−1)+(k−1)×(2k+1) =2k2+k−2 and k3+(k−1)×(2k+1) =k3+2k2−k−1 we obtain ∆(2k+1) =1. After applying Claim I to 1+(k−1)×(2k+1) =2k2−kand k×(2k−1) =2k2−k, we have ∆(2k2−k)=3. Consider 1 +(2k+1) +(k−2) ×(k2+2k)=k3−2k+2 and (k3−2k+2) +2×(2k−1) +(k−3) ×k=k3+k2−k we have ∆(k3−2k+2) =3. Since k2+(k−1) ×2=k2+2k−2 and (k3−2k+2) +(k−1) ×2=k3we deduce ∆(2) =2. We now obtain a contradiction by noting that one of the following equations must be monochromatic (k2+k)+(k− 1)×1=k2+2k−1; (2k2+k−2)+2+(k−2)×(k2+k)=k3+k2−k; and (2k2−k)+(k−1)×(k2+k)=k3+2k2−2k. We show k2+k∈ Ai,i=1,2,3, for otherwise k2+k⊆Ai∩f(Ai). 4. Assigning the color 3 to k2 We suppose ∆(k2)=3, therefore A1⊇ {1},A2⊇ {k}and A3⊇ {k2}.We have that k×k2=k3so to avoid a monochromatic solution in A1, we assume that ∆(k3)∈ {1,2}. 4.1. Assigning the color 1 to k3 We consider ∆(k3)=1, so that A1⊇ {1,k3},A2⊇ {k}and A3⊇ {k2}.To avoid k3+(k−1) ×1=k3+k−1, being a monochromatic solution in A1, we assume that ∆(k3+k−1) ∈ {2,3}. Case 1: A1⊇ {1,k3},A2⊇ {k,k3+k−1}and A3⊇ {k2}.Apply Claim I to 1 +(k−1) ×(k2+k+1) =k3and k+(k−1) ×(k2+k+1) =k3+k−1, to get ∆(k2+k+1) =3. Since (k3+k−1) +(k−1) ×k=k3+k2−1 and k2+(k−1) ×(k2+k+1) =k3+k2−1 we have ∆(k3+k2−1) =1. To avoid k3+(k−1) ×(k+1) =k3+k2−1, being a monochromatic solution in A1, we consider that ∆(k+1) ∈ {2,3}. Case 1.1: A1⊇ {1,k3,k3+k2−1},A2⊇ {k,k3+k−1,k+1}and A3⊇ {k2,k2+k+1}.Apply Claim I to (k3+k2−1) +(k−1) ×1=k3+k2+k−2 and (k3+k−1) +(k−1) ×(k+1) =k3+k2+k−2 we have ∆(k3+k2+k−2) =3. Consider k×(k+1) =k2+kand 2 ×(k2+k)+(k−2) ×(k2+k+1) =k3+k2+k−2 we deduce ∆(k2+k)=1. We now obtain a contradiction by noting that one of the following equations must be monochromatic (k2+k−1) +(k− 1) ×(k2+k)=k3+k2−1; k+(k−1) ×(k+1) =k2+k−1; and (k2+k−1) +(k−1) ×(k2+k+1) =k3+k2+k−2. We show k2+k−1∈ Ai,i=1,2,3, for otherwise k2+k−1⊆Ai∩f(Ai). Case 1.2: A1⊇ {1,k3,k3+k2−1},A2⊇ {k,k3+k−1}and A3⊇ {k2,k2+k+1,k+1}.To avoid (k3+k2−1)+(k−1)×1= k3+k2+k−2 being a monochromatic solution in A1, we assume that ∆(k3+k2+k−2) ∈ {2,3}. Case 1.2.1: ∆(k3+k2+k−2) =2.Apply Claim I to 1+(k−1)×(k2+2k+2) =k3+k2−1 and k+(k−1)×(k2+2k+2) = k3+k2+k−2, so we deduce that ∆(k2+2k+2) =3. Since (k3+k2+k−2) +(k−1) ×k=k3+2k2−2 and k2+(k−1)×(k2+2k+2) =k3+2k2−2 we have ∆(k3+2k2−2) =1. To avoid k3+(k2−k+1)+(k−2)×1=k3+k2−1, being a monochromatic solution in A1, we consider that ∆(k2−k+1) ∈ {2,3}. 1. ∆(k2−k+1) =2.Apply Claim I to k3+(2k2−k)+(k−2)×1=k3+2k2−2 and (2k2−k)+(k−1)×(k2−k+1) =k3+k−1, to get ∆(2k2−k)=3. Since (k3+k−1) +(2k−1) +(k−2) ×k=k3+k2+k−2 and k×(2k−1) =2k2−kwe have ∆(2k−1) =1. Consider (k3+k2−k)+(k−1) ×1=k3+k2−1 and (2k2−k)+(k−1) ×k=k3+k2−kwe deduce ∆(k3+k2−k)=2. We now obtain a contradiction by noting that one of the following equations must be monochromatic 1+(k−1)×2= 2k−1; (k3+k2−k)+(k−1)×2=k3+k2+k−2; and 1k2+2+(k−2)×(k+1) =2k2−k.We show 2k2−k∈ Ai,i=1,2,3, for otherwise 2k2−k⊆Ai∩f(Ai). 2. ∆(k2−k+1) =3.Apply Claim I to (k3−k+1) +(k−1) ×1=k3and (k2−k+1) +(k−1) ×k2=k3−k+1 we have ∆(k3−k+1) =2. To avoid (k3−k+1) +(k−1) ×2=k3+k−1, being a monochromatic solution in A2, we consider that ∆(2) ∈ {1,3}. (a) ∆(2k−1) =1.Apply Claim I to k3+(k−1)×2=k3+2k−2 and 1(k3+2k−2)+(k−1) ×k=k3+k2+k−2, to get ∆(k3+2k−2) =3. We now obtain a contradiction by noting that one of the following equations must be monochromatic 1 +(k− 1)×2=2k−1; (k3+k−1)+(2k−1)+(k−2)×k=k3+k2+k−2; and (2k−1)+(k−1)×(k2+k+1) =k3+2k−2. We show 2k−1∈ Ai,i=1,2,3, for otherwise 2k−1⊆Ai∩f(Ai). (b) ∆(2k−1) =1.Apply Claim I to (k3+k−1) +(2k−1) +(k−2) ×k=k3+k2+k−2 and (2k−1) +2×2+(k−3) ×(k+1) =k2, we have ∆(2k−1) =1. We now obtain a contradiction by noting that one of the following equations must be monochromatic (2k−1)+ (k−1) ×(k2+k−1) =k3;k+(k−1) ×(k2+k−1) =k3−k+1; and (k2−k+1) +(k−1) ×2=k2+k−1. We show k2+k−1∈ Ai,i=1,2,3, for otherwise k2+k−1⊆Ai∩f(Ai). Case 1.2.2: ∆(k3+k2+k−2) =3.To avoid (k2+k−1) +(k−1) ×(k2+k+1) =k3+k2+k−2, being a monochromatic solution in A3, we consider that ∆(k2+k−1) ∈ {1,2}. 1. ∆(2k−1) =1.After applying Claim I to 1(k2+k−1) +(k−1) ×(k2+k)=k3+k2−1 and k×(k+1) =k2+k, we obtain ∆(k2+k)=2.Since 1 +(k−1) ×(k+2) =k2+k−1 and (k+2) +(k−1) ×(k+1) =k2+k+1, we deduce that ∆(k+2) =2. We have (2k−1) +(k−1) ×(k2+k−1) =k3and (2k−1) +(k−1) ×(k2+k)=k3+k−1 so we obtain ∆(2k−1) =3. We now obtain a contradiction by noting that one of the following equations must be monochromatic (k2+k−1) + (k−1) ×1=k2+2k−2; k+(k−1) ×(k+2) =k2+2k−2; and (2k−1) +(k−1) ×(k+1) =k2+2k−2.We show k2+2k−2∈ Ai,i=1,2,3, for otherwise k2+2k−2⊆Ai∩f(Ai). 2. ∆(2k−1) =1.Apply Claim I to (k3−k+1) +(k−1) ×1=k3and k+(k−1) ×(k2+k−1) =k3−k+1, to get ∆(k3−k+1) =3. We now obtain a contradiction by noting that one of the following equations must be monochromatic (k3+k2−k)+ (k−1) ×1=k3+k2−1; k×(k2+k−1) =k3+k2−k; and (k3−k+1) +(k−1) ×(k+1) =k3+k2−k.We show k3+k2−k∈ Ai,i=1,2,3, for otherwise k3+k2−k⊆Ai∩f(Ai). Case 2: A1⊇ {1,k3},A2⊇ {k}and A3⊇ {k2,k3+k−1}.To avoid (k2+k−1) +(k−1) ×k2=k3+k−1, being a monochromatic solution in A3, we consider that ∆(k2+k−1) ∈ {1,2}. Case 2.1: A1⊇ {1,k3,k2+k−1},A2⊇ {k}and A3⊇ {k2,k3+k−1}.To avoid (k2+k−1) +(k−1) ×1=k2+2k−2, being a monochromatic solution in A1, we assume ∆(k2+2k−2) ∈ {2,3}. Case 2.1.1 A1⊇ {1,k3,k2+k−1},A2⊇ {k,k2+2k−2}and A3⊇ {k2,k3+k−1}.Apply Claim I to 1+(k−1)×(k+2) =k2+k−1 and k+(k−1) ×(k+2) =k2+2k−2, we have ∆(k+2) =3. Since (2k−1) +(k−1) ×(k2+k−1) =k3and 2×(2k−1) +(k−2) ×k=k2+2k−2, we deduce ∆(2k−1) =3. We have (k2+2k−2) +(k−1) ×k=2k2+k−2 and k2+(k−1) ×(k+2) =2k2+k−2, so we obtain ∆(2k2+k−2) =1. We now obtain a contradiction by noting that one of the following equations must be monochromatic 1 +2×(2k2+k− 2) +(k−3) ×(k2+k−1);k×(k2+2k−2) =k3+2k2−2k; and (k3+k−1) +(k−1) ×(2k−1) =k3+2k2−2k.We show k3+2k2−2k∈ Ai,i=1,2,3, for otherwise k3+2k2−2k⊆Ai∩f(Ai). Case 2.1.2: A1⊇ {1,k3,k2+k−1},A2⊇ {k}and A3⊇ {k2,k3+k−1,k2+2k−2}.Apply Claim I to (k2+k−1)+(k−1)×(k2−1) = k3and (k2+2k−2) +(k−1) ×(k2−1) =k3+k−1, to get ∆(k2−1) =2. To avoid, k×(k2+k−1) =k3+k2−k, being a monochromatic solution in A1, we consider that ∆(k3+k2−k)∈ {2,3}. 1. ∆(2k−1) =1.Apply Claim I to 1(k3+k2−k)+(k−1) ×k=k3+2k2−2kand k×(k2+2k−2) =k3+2k2−2k, we have ∆(k3+2k2−2k)=1. Since (2k2−1)+(k−1) ×(k2+k−1) =k3+2k2−2kand (2k2−1)+(k−1)×(k2−1) = k3+k2−kwe deduce ∆(2k2−1) =3. We have k3+(k2+k−1) +(k−2) ×1=k3+k2+2k−3 and (k2+2k−2) +(2k2−1) +(k−2) ×k2=k3+k2+2k−3, so we deduce ∆(k3+k2+2k−3) =2. Apply Claim I to (k−1) +(k−1) ×k=k2−1 and (k2+2k−2) +(k−1) ×(k−1) =2k2−1, to get ∆(k−1) =1. Since (k3+k2−1)+(k−1)×(k−1) =k3+2k2−2kand (2k2−1)+(k−1)×k2=k3+k2−1, we deduce ∆(k3+k2−1) =2. Consider (k3+k2−1) +(k−1) ×2=k3+k2+2k−3 and k2+(k−1) ×2=k2+2k−2 we obtain ∆(2) =1. Apply Claim I to 2 +(k−1) ×1=k+1 and k2+(k−1) ×(k+1) =2k2−1, to get ∆(k+1) =2. We now obtain a contradiction by noting that one of the following equations must be monochromatic (k3+2k2−2k)+ (k−1)×2=k3+2k2−2; (k3+k2−1)+(k−1)×(k+1) =k3+2k2−2; and 2×(2k2−1)+(k−2)×k2=k3+2k2−2. We show k3+2k2−2∈ Ai,i=1,2,3, for otherwise k3+2k2−2⊆Ai∩f(Ai). 2. ∆(2k−1) =1.Apply Claim I to (k−1) +(k−1) ×k=k2−1 and ×(k3+k−1) +(k−1) ×(k−1) =k3+k2−k, we have ∆(k−1) =1. Since (k2+k−1) +(k−1) ×(k−1) =2k2−kand (2k2−k)+(k−1) ×k2=k3+k2−kwe deduce ∆(2k2−k)=2. Once we apply Claim I to (2k−1) +(k−1) ×(k2+k−1) =k3and k×(2k−1) =2k2−k we have ∆(2k−1) =3. We now obtain a contradiction by noting that one of the following equations must be monochromatic k3+(k−1)×(k− 1) =k3+k2−2k+1; (2k2−k)+(k−1)×(k2−1) =k3+k2−2k+1; and (2k−1)+(k−1)×(k2+2k−2) =k3+k2−2k+1. We show k3+k2−2k+1∈ Ai,i=1,2,3, for otherwise k3+k2−2k+1⊆Ai∩f(Ai). Case 2.2: A1⊇ {1,k3},A2⊇ {k,k2+k−1}and A3⊇ {k2,k3+k−1}.Apply Claim I to (k3−k+1) +(k−1) ×1=k3and k+(k−1) ×(k2+k−1) =k3−k+1 we have ∆(k3−k+1) =3. To avoid (k2+k−1) +(k−1) ×k=2k2−1 being a monochromatic solution in A2we considered that ∆(2k2−1) ∈ {1,3}. Case 2.2.1) A1⊇ {1,k3,2k2−1},A2⊇ {k,k2+k−1}and A3⊇ {k2,k3−k+1}.Apply Claim I to (k3−k+1)+(k−1)×1=k3 and k+(k−1) ×(k2+k−1) =k3−k+1 to get ∆(k3−k+1) =3. To avoid (2k−1) +(k−1) ×k=k2+k−1 being a monochromatic solution in A2we assume ∆(2k−1) ∈ {1,3}. 1. ∆(2k−1) =1.Apply Claim I to 1 +(k−1) ×2=2k−1 and (k3−k+1) +(k−1) ×2=k3+k−1 to get ∆(2) =2. Since (k2−k+1) +(k−1) ×2=k2+k−1 and (k2−k+1) +(k−1) ×k2=k3−k+1, we have ∆(k2−k+1) =1. Consider (2k−1) +(k−1) ×2k=2k2−1 and k×2=2k, so we deduce that ∆(2k)=3. After applying Claim I to (2k2−1)+(k2−k+1)+(k−2)×1=3k2−2 and 2×(k2+k−1) +(k−2)×k=3k2−2, we obtain ∆(3k2−2) =3. We have (2k−1) +(k2−k+1) +(k−2) ×1=k2+2k−2, (k2+2k−2) +(k−1) ×2k=3k2−2, applying Claim I we deduce ∆(k2+2k−2) =2. Since 2 +(k2+2k−2) +(k−2) ×k=2k2,k×2k=2k2, we have ∆(2k2)=1. Apply Claim I to (k+1) +2×(k2−k+1) +(k−3) ×1=2k2and k+(k−1) ×(k+1) =k2+k−1, to get ∆(k+1) =3. We now obtain a contradiction by noting that one of the following equations must be monochromatic k3+(k2−k+1)+ (k−2)×1=k3+k2−1; (k2+2k−2)+(k−1)×(k2+k−1) =k3+k2−1; and (k3−k+1)+2k+(k−2)×(k+1) =k3+k2−1. We show k3+k2−1∈ Ai,i=1,2,3, for otherwise k3+k2−1⊆Ai∩f(Ai). 2. ∆(2k−1) =1.Apply Claim I to k×(2k−1) =2k2−kand k×(2k−1) =2k2−k, we have ∆(2k2−k)=2. Since (k2+k−1) +(k−1) ×(k−1) =2k2−kand (2k−1) +(k−1) ×(k−1) =k2, we deduce ∆(k−1) =1. We now obtain a contradiction by noting that one of the following equations must be monochromatic (2k−1)+(k2+ k−2)+(k−2)×(k−1) =2k2−1; 2+(k2+k−2)+(k−2)×k=2k2−k; and (2k−1)+(k−1)×(k2+k−2) =k3−k+1. We show k2+k−2∈ Ai,i=1,2,3, for otherwise k2+k−2⊆Ai∩f(Ai). Case 2.2.2: A1⊇ {1,k3},A2⊇ {k,k2+k−1}and A3⊇{k2,k3−k+1,2k2−1}.Apply Claim I to k+(k−1)×(k+1) =k2+k−1 and k2+(k−1)×(k+1) =2k2−1, we have ∆(k+1) =1. Consider 2+(k−1)×1=k+1 and (k3−k+1)+(k−1)×2=k3+k−1, we deduce ∆(2) =2. Since (k+1) +(k−1) ×1=2kand k×2=2k, so we obtain ∆(2k)=3.Apply Claim I to k3+(k−1) ×(k+1) =k3+k2−1 and (2k2−1) +(k−1) ×k2=k3+k2−1, to get ∆(k3+k2−1) =2. We now obtain a contradiction by noting that one of the following equations must be monochromatic k×(k+1) =k2+k; (k2+k−1) +(k−1) ×(k2+k)=k3+k2−1; and (2k2−1) +2×2k+(k−3) ×(k2+k)=k3+k−1.We show k2+k∈ Ai,i=1,2,3, for otherwise k2+k⊆Ai∩f(Ai). 4.2. Assigning the color 2 to k3 We consider ∆(k3)=2, so that A1⊇ {1},A2⊇ {k,k3}and A3⊇ {k2}.To avoid k+(k−1) ×(k2+k)=k3, being a monochromatic solution in A2, we considered ∆(k2+k)∈ {1,3}. Case 1: A1⊇ {1,k2+k},A2⊇ {k,k3}and A3⊇ {k2}.To avoid k3+(k−1)×k=k3+k2−k, we assume ∆(k3+k2−k)∈ {1,3}. Case 1.1: A1⊇ {1,k2+k,k3+k2−k},A2⊇ {k,k3}and A3⊇ {k2}.To avoid k×(k2+k−1) =k3+k2−kbeing a monochromatic solution in A1we considered ∆(k2+k−1) ∈ {2,3}. Case 1.1.1: A1⊇ {1,k2+k,k3+k2−k},A2⊇ {k,k3,k2+k−1}and A3⊇ {k2}.Apply Claim I to k×(k+1) =k2+kand k+(k−1)×(k+1) =k2+k−1, to get ∆(k+1) =3.Since 1+(k−1)×(k2+k)=k3−k+1 and k+(k−1)×(k2+k−1) =k3−k+1 we deduce ∆(k3−k+1) =3.We have 1(k2+k−1) +(k−1) ×(k2−1) =k3and k2+(k−1) ×(k2−1) =k3−k+1, so we obtain ∆(k2−1) =1. We now obtain a contradiction by noting that one of the following equations must be monochromatic (2k2−1) +(k− 1) ×(k2−1) =k3+k2−k; (k2+k−1) +(k−1) ×k=2k2−1; and k2+(k−1) ×(k+1) =2k2−1.We show 2k2−1∈ Ai,i=1,2,3, for otherwise 2k2−1⊆Ai∩f(Ai). Case 1.1.2: A1⊇ {1,k2+k,k3+k2−k},A2⊇ {k,k3}and A3⊇ {k2,k2+k−1}.Apply Claim I to (k3+k2−2k+1)+(k−1)×1= k3+k2−kand k2+(k−1) ×(k2+k−1) =k3+k2−2k+1, we have ∆(k3+k2−2k+1) =2.Consider (k2+k)+(k−1) ×1=k2+2k−1 and k+(k−1) ×(k2+2k−1) =k3+k2−2k+1, we deduce ∆(k2+2k−1) =3.Since 1+(k−1)×(k2+k)=k3−k+1 and (k3−k+1)+(k−1)×k=k3+k2−2k+1, we have ∆(k3−k+1) =3.Apply Claim I to k3+(k−1)×(k−1) =k3+k2−2k+1 and k2+(k2+2k−1)+(k−1)+(k−3)×(k2+k−1) =k3−k+1, we have ∆(k−1) =1. Since 1+(k−1)×(k−1) =k2−2k+2 and (k2+k−1)+(k2−2k+2)+(k−2)×k2=k3−k+1, we deduce ∆(k2−2k+2) =2. After Applying Claim I to 2 ×(2k−1) +(k−2) ×(k−1) =k2+kand k2+(2k−1) +(k−2) ×(k2+k−1) =k3−k+1, we obtain ∆(2k−1) =2.Consider (k3+k2−k)+(k−1) ×1=k3+k2−1 and k3+(2k−1) +(k−2) ×k=k3+k2−1, we have ∆(k3+k2−1) =3. We now obtain a contradiction by noting that one of the following equations must be monochromatic (2k2−k)+(k− 1) ×(k2+k)=k3+2k2−2k;k×(2k−1) =2k2−k; and (k2+k−1) +(2k2−k)+(k−2) ×k2=k3+k2−1.We show 2k2−k∈ Ai,i=1,2,3, for otherwise 2k2−k⊆Ai∩f(Ai). Case 1.2: A1⊇ {1,k2+k},A2⊇ {k,k3}and A3⊇ {k2,k3+k2−k}.To avoid 1 +(k−1) ×(k2+k)=k3−k+1 being a monochromatic solution in A1we considered ∆(k3−k+1) ∈ {2,3}. Case 1.2.1: A1⊇ {1,k2+k},A2⊇ {k,k3,k3−k+1}and A3⊇ {k2,k3+k2−k}.Apply Claim I to k+(k−1)×(k2+k−1) =k3−k+1 and k×(k2+k−1) =k3+k2−kto get ∆(k2+k−1) =1. To avoid k×(k+1) =k2+k, we considered ∆(k+1) ∈ {2,3}. 1. ∆(2k−1) =1.Apply Claim I to (k2+k−1) +(k−1) ×1=k2+2k−2 and k+(k−1) ×(k+2) =k2+2k−2, to get ∆(k2+2k−2) =3. Since (k2+k−1)+(k−1)×(k2+k)=k3+k2−1 and (k3−k+1)+(k−1)×(k+2) =k3+k2−1, we have ∆(k3+k2−1) =3. To avoid k2+(k−1) ×2=k2+2k−2, being monochromatic solution en A3, we assume ∆(2) ∈ {1,2}. (a) ∆(2k−1) =1.Apply Claim I to (k2+k)+2+(k−2)×1=k2+2kand k×(k+2) =k2+2k, we have ∆(k2+2k)=3. Since 1 +(k−1) ×2=2k−1 and (2k−1) +(k−1) ×(k2+2k)=k3+k2−1, we deduce ∆(2k−1) =2. Consider k+(k−1) ×(2k−1) =2k2−2k+1 and (k2+2k−2) +(2k2−2k+1) +(k−2) ×k2=k3+k2−1, we have ∆(2k2−2k+1) =1. We now obtain a contradiction by noting that one of the following equations must be monochromatic (2k2− 2k+1) +(k−1) ×1=2k2−k;k×(2k−1) =2k2−k; and (2k2−k)+(k−1) ×k2=k3+k2−k.We show 2k2−k∈ Ai,i=1,2,3, for otherwise 2k2−k⊆Ai∩f(Ai). (b) ∆(2k−1) =1.Apply Claim I to k+2+(k−2)×(k+2) =k2+k−2 and (k2+2k−2)+(k−1) ×(k2+k−2) = k3+k2−k, we have ∆(k2+k−2) =1. Since k3+(k−1)×2=k3+2k−2 and (k2+2k−2)+(k−1)×k2=k3+2k−2, we deduce ∆(k3+2k−2) =1. Consider 2 ×(k2+k−1) +(k−2) ×(k2+k)=k3+k2−2 and k3+2+(k−2) ×(k+2) =k3+k2−2, we obtain ∆(k3+k2−2) =3. Once Apply Claim I to (k2+k−1)+(k−1)×(k2+k−2) =k3+k2−2k+1 and (k3−k+1)+(k−1)×k=k3+k2−2k+1, we deduce ∆(k3+k2−2k+1) =3. Since k×(k+1) =k2+kand (k3−2k+2) +(k−1) ×(k+1) =k3+k2−2k+1, we have ∆(k+1) =2. Consider k+2×2+(k−3) ×(k+2) =k2−2 and k2+(k−1) ×(k2−2) =k3−2k+2, we deduce ∆(k2−2) =1. We now obtain a contradiction by noting that one of the following equations must be monochromatic (k2−2)+ (k−1)×1=k2+k−3; 3×k+(k−3)×(k+1) =k2+k−3; and (k2+2k−2)+(k−1)×(k2+k−3) =k3+k2−2k+1. We show k2+k−3∈ Ai,i=1,2,3, for otherwise k2+k−3⊆Ai∩f(Ai). 2. ∆(2k−1) =1.Apply Claim I to 1+(k−1)×(k2+k−1) =k3−2k+2 and (k3−2k+2)+(k−1)×(k+2) =k3+k2−k, to get ∆(k3−2k+2) =2. Consider (k3−2k+2) +(k−1) ×2=k3and 2 ×2+(k−2) ×(k+2) =k2, we have ∆(2) =1. Since (k2+k)+2+(k−2)×1=k2+2kand k×(k+2) =k2+2k, so we deduce that ∆(k2+2k)=2. After applying Claim I to k×(k+1) =k2+kand 2×(k+1)+(k−2)×(k2+2k)=k3−2k+2, we have ∆(k+1) =3. Since (k3−k+1)+(k2+2k)+(k−2)×k=k3+2k2−k+1 and (k3+k2−k)+2×(k+2)+(k−3)×(k+1) =k3+2k2−k+1, we obtain ∆(k3+2k2−k+1) =1. Apply Claim I to (k2+k−1) +(k−1) ×1=k2+2k−2 and 2×(k+1) +(k−2) ×(k+2) =k2+2k−2, we have ∆(k2+2k−2) =2. We now obtain a contradiction by noting that one of the following equations must be monochromatic (2k2+k− 2) +2×(k2+k)+(k−3) ×(k2+k−1) =k3+2k2−k+1; (k2+2k−2) +(k−1) ×k=2k2+k−2; and k2+(k−1) ×(k+2) =2k2+k−2.We show 2k2+k−2∈ Ai,i=1,2,3, for otherwise 2k2+k−2⊆Ai∩f(Ai). Case 1.2.2: A1⊇ {1,k2+k},A2⊇ {k,k3}and A3⊇ {k2,k3+k2−k,k3−k+1}.Apply Claim I to k×(k+1) =k2+kand (k3−k+1)+(k−1)×(k+1) =k3+k2−k, we have ∆(k+1) =2. Consider k+(k−1)×(k+1) =k2+k−1 and k×(k2+k−1) = k3+k2−k, we deduce ∆(k2+k−1) =1. Since (k2+1)+(k−1)×1=k2+kand 1(k+1)+(k−1)×k=k2+1, so we obtain ∆(k2+1) =3. After Applying Claim I to (k2+k)+(k−1)×(k2+k−1) =k3+k2−k+1 and k3+(k+1)+(k−2)×k=k3+k2−k+1, we have ∆(k3+k2−k+1) =3. Since 2×(k2+k−1)+(k−2)×(k2+k)=k3+k2−2 and k+k3+(k−2)×(k+1) =k3+k2−2, we deduce ∆(k3+k2−2) =3. Apply Claim I to (k2+k−1)+(k−1)×(k2+k)=k3+k2−1 and k3+(k−1)×(k+1) =k3+k2−1, to get ∆(k3+k2−1) =3. Consider 1 +(k−1) ×(k+2) =k2+k−1 and (k3−k+1) +(k−1) ×(k+2) =k3+k2−1, we have ∆(k+2) =2. Since (k+2) +(k−1) ×(k+1) =k2+k+1 and k2+(k−1) ×(k2+k+1) =k3+k2−1, we deduce ∆(k2+k+1) =1. We have 2×(k+2)+(k−2)×(k+1) =k2+k+2 and 2×(k2+1)+(k−2)×(k2+k+2) =k3+k2−2, so we obtain ∆(k2+k+2) =1. Since (k2+k)+(k−1)×1=k2+2k−1 and (k+1)+(k−1)×(k+2) =k2+2k−1, we deduce ∆(k2+2k−1) =3. Consider k×(k2+k)=k3+k2and k3+(k+2) +(k−2) ×(k+1) =k3+k2, we have ∆(k3+k2)=3. Once we apply claim I to 1+2×(k2+k+2)+(k−3)×(k2+k+1) =k3+2 and 2×(k2+1)+(k−2)×k2=k3+2, we obtain ∆(k3+2) =2. Apply Claim I to 2×k+(k−2)×(k+1) =k2+k−2 and (k2+2k−1)+(k−1)×(k2+k−2) =k3+k2−k+1, to get ∆(k2+k−2) =1. Since (k2−1) +(k−1) ×1=k2+k−2 and k2+(k−1) ×(k2−1) =k3−k+1, we have ∆(k2−1) =2. Consider k+(2k2)+(k−2) ×(k2−1) =k3+2 and (2k2)+(k−1) ×k2=k3+k2, we deduce ∆(2k2)=1. We now obtain a contradiction by noting that one of the following equations must be monochromatic (2k2−k+1) + (k−1) ×1=2k2; (k+2) +(k2−1) +(k−2) ×k=2k2−k+1; and (2k2−k+1) +(k−1) ×k2=k3+k2−k+1.We show 2k2−k+1∈ Ai,i=1,2,3, for otherwise 2k2−k+1⊆Ai∩f(Ai). Case 2: A1⊇ {1},A2⊇ {k,k3}and A3⊇ {k2,k2+k}.Apply Claim I to k3+(k−1) ×k=k3+k2−kand k2+(k−1) ×(k2+k)=k3+k2−k, to get ∆(k3+k2−k)=1.To avoid k×(k2+k−1) =k3+k2−k, being a monochromatic solution in A1, we consider that ∆(k2+k−1) ∈ {2,3}. Case 2.1: A1⊇ {1},A2⊇ {k,k3,k2+k−1}and A3⊇ {k2,k2+k}.Apply Claim I to k+(k−1) ×(k+1) =k2+k−1 and k×(k+1) =k2+kwe deduce ∆(k+1) =1. Consider (k3−k+1) +(k−1) ×(k+1) =k3+k2−kand k+(k−1)×(k2+k−1) =k3−k+1, we have ∆(k3−k+1) =3.Since (k3+k2−k)+(k−1)×(k+1) =k3+2k2−k−1 and k3+(k2+k−1)+(k−2)×k=k3+2k2−k−1, we obtain ∆(k3+2k2−k−1) =3.Apply claim I to (k2+k−1)+(k−1)×k=2k2−1 and (2k2−1) +(k−1) ×(k2+k)=k3+2k2−k−1, we have ∆(2k2−1) =1. We now obtain a contradiction by noting that one of the following equations must be monochromatic (2k2−1) +(k− 1) ×(k2−1) =k3+k2−k; (k2+k−1) +(k−1) ×(k2−1) =k3; and k2+(k−1) ×(k2−1) =k3−k+1.We show k2−1∈ Ai,i=1,2,3, for otherwise k2−1⊆Ai∩f(Ai). Case 2.2: A1⊇ {1},A2⊇ {k,k3}and A3⊇ {k2,k2+k,k2+k−1}.Apply Claim I to (k3+k2−k)+(k−1) ×1=k3+k2−1 and (k2+k−1) +(k−1) ×(k2+k)=k3+k2−1, to get ∆(k3+k2−1) =2.Since (k−1) ×(k2+2k+1) =k3+k2−k and k+(k−1) ×(k2+2k+1) =k3+k2−1, we have ∆(k2+2k+1) =3.Consider k3+(k−1) ×(k+1) =k3+k2−1 and k×(k+1) =k2+k, we deduce ∆(k+1) =1. We now obtain a contradiction by noting that one of the following equations must be monochromatic (k3+k2−k)+(k− 1)×(k+1) =k3+2k2−k−1; (k3+k2−1)+(k−1)×k=k3+2k2−k−1; and k2+(k−1)×(k2+2k+1) =k3+2k2−k−1. We show k3+2k2−k−1∈ Ai,i=1,2,3, for otherwise k3+2k2−k−1⊆Ai∩f(Ai). 4.3. Reformulation as a SAT problem To prove that the equation x1+···+xk=xk+1has a monochromatic solution for every 3-coloring of the integer interval [1,k3+2k2−2], it is necessary to prove the following result. Lemma 4.1. Let k ≥3and the set Xk= {1,2,k,k+1,k+2,2k,k2−k+1,k2−1,k2,k2+1,k2+k−1,k2+k,k2+k+1,2k2−2k+1,2k2− k,2k2−k+1,2k2−1,2k2+k−2,3k2−2k,3k2−k−1,3k2−2,k3,k3+1,k3+k−1,k3+k,k3+k2−k, k3+k2−1,k3+k2+k−2,k3+2k2−k−1,k3+2k2−2}, then it is verified that: 1. For every x ∈Xk,1≤x≤k3+2k2−2. 2. For every 3-coloring of the set Xkthere exists a monochromatic solution to the equation x1+x2+x3+(k−3)x4=x5. Proof. 1. This is trivial. 2. We have checked the result transforming the problem into a Boolean satisfiability problem and solving it with a SAT solver [10]. Y= {y1, . . . , y30}={(a,b,c,d):ak3+bk2+ck +d∈Xkfor any k≥3}, i.e., Y= {(0,0,0,1), (0,0,0,2), (0,0,1,0), (0,0,1,1), (0,0,1,2), (0,0,2,0), (0,1,−1,1), (0,1,0,−1), (0,1,0,0), (0,1,0,1), (0,1,1,−1), (0,1,1,0), (0,1,1,1), (0,2,−2,1), (0,2,−1,0), (0,2,−1,1), (0,2,0,−1), (0,2,1,−2), (0,3,−2,0), (0,3,−1,−1), (0,3,0,−2), (1,0,0,0), (1,0,0,1), (1,0,1,−1), (1,0,1,0), (1,1,−1,0), (1,1,0,−1), (1,1,1,−2), (1,2,−1,−1), (1,2,0,−2)}. Let ∆: [1,k3+2k2−2] −→ {1,2,3}be a 3-coloration of [1,k3+2k2−2]. We consider two Boolean variables φ, ψ : [1,30] −→ {True,False}defined as follow: φ(n)={True if ∆(yn)=1 or 2, False if ∆(yn)=3. ψ(n)={True if ∆(yn)=1 or 3, False if ∆(yn)=2. Thus, for any n∈ [1,30]we have that φ(n) is True or ψ(n) is True and D= 30 ⋀ n=1 (φ(n)∨ψ(n)) is satisfiable. Let Sbe the set of (n1,n2,n3,n4,n5)∈ [1,30]5, with n1≤n2≤n3,yni=(ai,bi,ci,di), a4=0 and yn5= yn1+yn2+yn3+(b4,c4,d4,0)−3yn4=(a1+a2+a3+b4,b1+b2+b3+c4−3b4,c1+c2+c3+d4−3c4,d1+d2+d3−3d4). For any s=(n1,n2,n3,n4,n5)∈S, we consider three clauses: p(s)= 5 ⋁ i=1 (¬φ(ni)∨¬ψ(ni)), q(s)= 5 ⋁ i=1 (¬φ(ni)∨ψ(ni)),and r(s)= 5 ⋁ i=1 (φ(ni)∨¬ψ(ni)). Then, p(s) is satisfiable if and only if ∆(xn)= 1 for some n∈s,q(s) is satisfiable if and only if ∆(xn)= 2 for some n∈s; and r(s) is satisfiable if and only if ∆(xn)= 3 for some n∈s. Thus ∆does not induce on sa monochromatic solution of the equation x1+x2+x3+(k−3)x4=x5if and only if p(s)∧q(s)∧r(s) is satisfiable. Let C=⋀ s∈S (p(s)∧q(s)∧r(s)). Clearly C∧Dis satisfiable if and only if the restriction of ∆to Xkis a 3-coloring without monochromatic solution to the equationx1+x2+x3+(k−3)x4=x5.