On the n-Color Weak Rado Numbers for the Equation x1 + x2 + ··· + xk + c = xk +1
Abstract
For integers k, n, c with k, n ≥ 1, and c ≥ 0, the n-color weak Rado number WRk (n, c) is defined as the least integer N, if it exists, such that for every n-coloring of the integer interval [1, N], there exists a monochromatic solution x1 ,..., xk, xk+1 in that interval to the equation x1 + x2 +···+ xk + c = xk+1 , with xi = xj , when i = j. If no such N exists, then WRk (n, c) is defined as infinite. In this paper, we determine the exact value of some of these numbers for n = 2 and n = 3, namely WR3 (2, c) = 5c + 24, WR4(2, c) = 6c + 52 for all c ≥ 0 and WR2 (3, c) = 13c + 22 for all c > 0. Our method consists in translating the problem into a Boolean satisfiability problem, which can then be handled by a SAT solver or by backtrack programming in the language C.
Full text
On he n-Colo Weak Rado Numbe s o he Equa ion x1 + x2 + ··· + xk + c = xk
+1
L. Boza, J.M.Ma ín, M.P.Re uel a, and M.I.Sanz
Depa amen o de Ma emá ica Aplicada I, Uni e sidad de Se illa, A enida Reina Me cedes s/n, Se illa, Spain
KEYWORDS
Schu numbe s; sum- ee
se s; weak Schu numbe s;
weakly sum- ee se s; Rado
numbe s; weak Rado
numbe s
MATHEMATICS SUBJECT
CLASSIFICATION
C; D; -; A
ABSTRACT
Fo in ege s k,n,cwi h k,n≥1,and c≥0, he n-colo weak Rado numbe WRk(n,c)is de ined as he
leas in ege N, i i exis s, such ha o e e y n-colo ing o he in ege in e al [1,N], he e exis s a
monoch oma ic solu ion x1,...,xk,xk+1in ha in e al o he equa ion
x1+x2+···+xk+c=xk+1,
wi h xi= xj,wheni= j.I no such Nexis s, hen WRk(n,c)is de ined as in ini e.
In his pape , we de e mine he exac alue o some o hese numbe s o n=2andn=3, namely
WR3(2,c)=5c+24, WR4(2,c)=6c+52 o all c≥0andWR2(3,c)=13c+22 o all c>0.Ou
me hod consis s in ansla ing he p oblem in o a Boolean sa is iabili y p oblem, which can hen be
handled by a SAT sol e o by back ack p og amming in he language C.
1. In oduc ion
Fo in ege s a≤b,weshalldeno e[a,b] hein ege in e -
al consis ing o all ∈N+={1,2,...}such ha a≤
≤b.A unc ion
:[1,N]−→ { d1,...,dn},
whe e d1,...,dn∈N+ ep esen di e en colo s, is a
n-colo ing o he in e al [1,N].
Gi en a n-colo ing and he equa ion x1+···+
xk=xk+1in k+1 a iables, henwesay ha asolu ion
x1,...,xk,xk+1 o he equa ion is monoch oma ic i and
only i (x1)=(x2)=···=(xk+1).
Fo in ege s k,n,cwi h k,n≥1,and c≥0, he n-colo
weak Rado numbe WRk(n,c)is de ined as he leas in e-
ge N, i i exis s, such ha o e e y n-colo ingo hein e-
ge in e al [1,N], he e exis s a monoch oma ic solu ion
x1,...,xk,xk+1in ha in e al o he equa ion
x1+x2+···+xk+c=xk+1,
wi h xi= xjwhen i= j.I no such Nexis s, hen
WRk(n,c)is de ined as in ini e.
1.1. Schu numbe s and weak Schu numbe s
Ase Ao in ege s is called sum- ee i i con ains no
elemen s x1,x2,x3∈Asa is ying x1+x2=x3,whe e
x1,x2need no be dis inc . I is called weakly sum- ee i
CONTACT M. P. Re uel a pas o [email protected] Depa amen o de Ma emá ica Aplicada I, Uni e sidad de Se illa, A enida Reina Me cedes s/n, C.P. Se illa,
Spain.
i con ains no pai wise dis inc elemen s x1,x2,x3∈A
sa is ying x1+x2=x3.
[Schu 16] p o ed ha , gi en a posi i e in ege n, he e
exis s a g ea es posi i e in ege S2(n)=Nwi h he p op-
e y ha he in ege in e al [1,N−1] can be pa i ioned
in o nsum- eese s. The numbe s S2(n)a e called Schu
numbe s. The cu en knowledge on hese numbe s o
1≤n≤7isgi eninTable 1.
The exac alue o S2(4)was ob ained by [Baume 61].
The lowe and uppe bounds on S2(5)a e due o [Exoo
94]and[Sanz 10], espec i ely. Finally, he lowe bounds
on S2(6)and S2(7)we e ob ained by [F ed icksen and
Swee 00] by conside ing symme ic sum- ee pa i ions.
Many gene aliza ions o Schu numbe s ha e appea ed
since hei in oduc ion.Wedeno ebyWS2(n), heg ea -
es in ege N, o which he in ege in e al [1,N−
1] can be pa i ioned in o nweakly sum- ee se s
{A1,A2,...,An}.
The numbe s WS2(n)a e called he weak Schu num-
be s.TheknownweakSchu numbe sa egi eninTable 2.
Thecu en s a eo knowledgeconce ningWS2(n)is
qui e con used.
The p oblem seems o ha e been i s conside ed in
[Walke 52], which is Walke ’s solu ion o P oblem E985
p oposed a yea ea lie , in 1951, by Mose . Walke con-
side ed he cases n=3,4,and 5, and claimed he alues
WS2(3)=24,WS2(4)=67 andWS2(5)=197. Un o u-
na ely, hesho accoun w i enbyMose onWalke ’s
Table . The fi s ew Schu numbe s S2(n).
n
S2(n)161 ≤···≤306 ≥537 ≥1681
solu ion only gi es sui able pa i ions o [1,23] o n=
3,andnode ailsa all o hecasesn=4and5.
Walke ’s claimed alues o WS2(3)and WS2(4)we e la e
con i med by [Blancha d e al. 06]. The lowe bound
WS2(5)≥197 has been con i med in [Eliahou e al. 12].
Whe he equali y holds in s ill an open p oblem. A lowe
bound on WS2(6)was ob ained by [Eliahou e al. 12]and
la e imp o ed o WS2(6)≥583 in [Eliahou 13].
1.2. Rado numbe s and weak Rado numbe s
In e ms o colo ing, he Schu numbe S2(n)[Schu
16] is he leas posi i e in ege Nsuch ha o e e y
n-colo ing o [1,N],
:[1,N]−→ { d1,...,dn},
whe e d1,...,dn ep esen ndi e en colo s, he e exis s
a monoch oma ic solu ion o he equa ion x1+x2=x3,
such ha (x1)=(x2)=(x3)whe e x1and x2need
no be dis inc .
In 1933, [Rado 33,Rado 36] gene alized he wo k o
Schu oa bi a ysys emso linea equa ions.Gi enasys-
em o linea equa ions Land a na u al numbe n, heleas
in ege N(i i exis s) such ha o e e y colo ing o he
in ege in e al [1,N]wi hncolo s he e is a monoch o-
ma ic solu ion o L,iscalled hen-colo Rado numbe o
L.I nosuchin ege Nexis s, hen he n-colo Rado num-
be o he sys em Lis aken o be in ini e.
A e hose i s esul s o Rado, e y li le p og ess has
been ob ained o some sys ems o linea equa ions. [Bu
and Loo 92] we e able o de e mine he 2-colo Rado
numbe o he equa ions x1+x2+c=x3and x1+x2=
kx3 o e e y in ege cand o e e y posi i e in ege k.
In 1993, [Schaal 93] de e mined he 2-colo Rado
numbe Rk(2,c) o he equa ion x1+x2+···+xk+
c=xk+1.Healsoob ained[Schaal 95] he3-colo Rado
numbe R2(3,c) o he equa ion x1+x2+c=x3.The e
a e se e al esul s due o Schaal and o he au ho s con-
ce ning 2-colo and 3-colo Rado numbe s o pa icula
equa ions, see [Jones and Schaal 04], [Kosek and Schaal
01], [Rendall and Schaal 06], and o he au ho s [Guo
and Sun 08]. In addi ion, ecen ly we ha e s udied when
Rk(n,c)is ini eo in ini eandweha eob ainednew
exac alues [Adhika i 16,Adhika i 17].
Table . The fi s ew weak Schu numbe s WS2(n).
n
WS2(n)≥197 ≥583
Fo e e y in ege c≥0, n≥1, le WR2(n,c)be he
leas in ege N(i i exis s) such ha , o e e y colo ing
o he in ege in e al [1,N]wi hncolo s, he e exis s
a monoch oma ic solu ion o he equa ion x1+x2+c=
x3,whe ex1= x2. The numbe s WR2(n,c)a e called he
weak Rado numbe s.
The numbe WR2(n,c)can be de ined equi alen ly as
he g ea es Nsuch ha he in ege in e al [1,N−1] can
be pa i ioned in o nse s A1,A2,...,Anwhich a e ee o
solu ions o he equa ion x1+x2+c=x3wi h x1= x2.
Recen ly,Schaale al.[Flin 13]ha eob ained he
numbe WR2(2,c) o e e y in ege c.
1.3. Con en s
In Sec ion 2, we de e mine he exac alue o he 3-colo
weak Rado numbe o he equa ion x1+x2+c=x3.
Compu a ional Theo em 2.1. Fo e e y c >0,weha e
WR2(3,c)=13c+22.
In Sec ion 3, we e i y he exac alues o he 2-colo
weak Rado numbe s o k=3,4.
Compu a ional Theo em 3.1. Fo e e y c ≥0,we
ha e
WR3(2,c)=∞i codd,
5c+24 i ce en.
Compu a ional Theo em 3.2. Fo e e y c ≥0,weha e
WR4(2,c)=6c+52.
In addi ion, we p o e WR5(2,2)=109 and
WR5(2,4)=123.
These exac alues we e ob ained in wo independen
ways. One o hem, by ans o ming he p oblem in o a
Boolean sa is iabili y p oblem and sol ing i wi h a SAT
sol e [Heule 11], and he o he one using back ack p o-
g amming in he language C [Helsgaun 95].
In Sec ions 4 and 5, he wo compu a ional p ocedu es
used in he p oo s a e shown.
2. Exac alue o he weak Rado numbe s
WR2(3,c)
In his sec ion, we shall p o e ha WR2(3,c)=13c+22
o e e y posi i e in ege c>0.
2.1. Lowe bound
We now p o e he lowe bound.
Lemma 2.1. We ha e WR2(3,c)≥13c+22 o any in e-
ge c >0.
P oo . Le c>0 be a posi i e in ege . We shall p o e
WR2(3,c)≥13c+22. Le be a 3-colo ing:
:[1,13c+22] −→ { d1,d2,d3},
whe e d1,d2,d3 ep esen 3 di e en colo s. Le Ai=
−1(di) o i=1,2,3 hus[1,13c+22] =A1A2
A3.
Conside he ollowing pa i ion o he in ege in e al
[1,13c+21]:
⎧
⎪
⎪
⎨
⎪
⎪
⎩
A1=[1,c+2] ∪[3c+7,4c+7]
∪[9c+17,10c+17] ∪[12c+21,13c+21],
A2=[c+3,3c+6] ∪[10c+18,12c+20],
A3=[4c+8,9c+16].
Hence {A1,A2,A3}is a pa i ion o [1,13c+21].
We now p o e ha o each i,1≤i≤3, i x1,x2∈Ai
wi h x1= x2 hen x1+x2+c/∈Ai.Weassume,wi hou
any loss o gene ali y, ha x1<x2.
Case 1: x1,x2∈A1
I x2≤c+2, hen c+3≤x1+x2+c≤3c+3,
he e o e x1+x2+c/∈A1.
I 3c+7≤x2≤4c+7 hen4c+8≤x1+x2+
c≤9c+13, he e o e x1+x2+c/∈A1.
I 9c+17 ≤x2≤10c+17, we ha e:
–I x1≤c+2 hen10c+18 ≤x1+x2+c≤
12c+19, he e o e x1+x2+c/∈A1.
–I 3c+7≤x1 hen 13c+24 ≤x1+x2+c,
he e o e x1+x2+c/∈A1.
I x2≥12c+21 hen x1+x2+c≥13c+22,
he e o e x1+x2+c/∈A1.
Case 2: x1,x2∈A2and x1≥c+3
I x2≤3c+6, hen 3c+7≤x1+x2+c≤7c+
11, he e o e x1+x2+c/∈A2.
I x2≥10c+18 hen 12c+21 ≤x1+x2+c,
he e o e x1+x2+c/∈A2.
Case 3: x1,x2∈A3
Since 9c+17 ≤x1+x2+c, henx1+x2+c/∈A3.
2.2. Uppe bound
Le c>0 be a posi i e in ege . We shall p o e
WR2(3,c)≤13c+22. This uppe bound was es ab-
lishedin hedoc o al hesis[Sanz 10] h oughan
exhaus i e analysis o nea ly 500 cases. We p o ide he e
aske cho ha p oo , o hisend,weshallp o e ha
o e e y 3-colo ing o he in ege in e al [1,13c+22],
he eexis samonoch oma icsolu ion o heequa ion
x1+x2+c=x3,x1= x2.
Assume, o a con adic ion, ha he e exis s a 3-
colo ing:
:[1,13c+22] −→ { d1,d2,d3},
whe e d1,d2,d3 ep esen h ee di e en colo s, wi hou
any monoch oma ic solu ion o he equa ion x1+x2+
c=x3,x1= x2.
Le Ai=−1(di) o i=1,2,3 hus[1,13c+22] =
A1A2A3.
We conside ed i e main cases, depending on he col-
o sassigned o henumbe s1,2and3:
Case 1. A1⊇{1,2,3}.
Case 2. A1⊇{1,2}and A2⊇{3}.
Case 3. A1⊇{1,3}and A2⊇{2}.
Case 4. A1⊇{1}and A2⊇{2,3}.
Case 5. A1⊇{1},A2⊇{2}and A3⊇{3}.
Gi en a subse X⊆[1,13c+22], we deno e
(X)=(XX+c)∩[1,13c+22]
=({x1+x2+c|x1,x2∈X,x1= x2})
∩[1,13c+22].
By hypo hesis on , o 1≤i≤3, we ha e
Ai∩ (Ai)=∅.(1)
The p oo es s on he ollowing claims, which a e bo h
di ec consequences o (1). Fo e e y in ege s i,j,ksuch
ha {i,j,k}={1,2,3},weha e:
Claim I. (Ai)∩ (Aj)⊆Ak.
Claim II. (Ai)∩ (Aj)∩ (Ak)=∅
Wenows a ou analysiswi hCase1andexplo e a -
ious subcases.
Case 1: A1⊇{1,2,3}
As c+3=1+2+c,wi hou anylosso gene ali y,we
may assume ha (c+3)=d2. In addi ion, since c+
4=1+3+c hen (c+4)= d1, and he e o e (c+
4)=d2o (c+4)=d3.
Case 1.1: (c+4)=d2
A1⊇{1,2,3},A2⊇{c+3,c+4}.
Since {3c+7, c+3, c+4} would be a monoch oma ic
solu ion in A2,wemus ha e(3c+7)=d1o (3c+
7)=d3.
Case 1.1.1: (3c+7)=d1
A1⊇{1,2,3,3c+7},A2⊇{c+3,c+4}.
As {4c+10, 3c+7, 3} would be a monoch oma ic solu-
ion in A1,wemus ha e(4c+10)=d2o (4c+
10)=d3.
Case 1.1.1a: (4c+10)=d2.
Hence A1⊇{1,2,3,3c+7},A2⊇{c+3,c+4,
4c+10}.We now show 2c+6∈A3.Indeed, we can-
no ha e 2c+6∈A1, o o he wisewewouldha e
3c+7∈A1∩ ({1,2c+6})⊆A1∩ (A1),acon-
adic ion since A1∩ (A1)=∅ by (1). Simila ly, we
canno ha e 2c+6∈A2, o o he wisewewouldha e
4c+10 ∈A2∩ ({c+4,2c+6})⊆A2∩ (A2),acon-
adic ionagain.I ollows ha 2c+6∈A3, i.e. (2c+
6)=d3,asclaimed.
The elemen 2c+5doesno belong oA1, since o h-
e wise 3c+7∈A1∩ ({2,2c+5})⊆A1∩ (A1)=∅.
Hence (2c+5)=d2o (2c+5)=d3.
Case 1.1.1a1: (2c+5)=d2
Hence A1⊇{1,2,3,3c+7},A2⊇{c+3,c+4,
4c+10,2c+5}and A3⊇{2c+6}. We now show
4c+9∈A3.In ac ,wecanno ha e4c+9∈A1, o o h-
e wise we would ha e 4c+9∈A1∩ ({2,3c+7})⊆
A1∩ (A1), a con adic ion since A1∩ (A1)=∅ by
(1). The same way, he elemen 4c+9doesno belong o
A2, o o he wise4c+9∈A2∩ ({c+4,2c+5})⊆
A2∩ (A2), a con adic ion again. I ollows ha
4c+9∈A3, i.e. (4c+9)=d3,asclaimed.
The e o e, A1⊇{1,2,3,3c+7},A2⊇{c+3,c+
4,4c+10,2c+5},and A3⊇{2c+6,4c+9}.Wenow
show 7c+15 ∈A1. Indeed, i does no hold ha
7c+15 ∈A2, o o he wisewewouldha e7c+15 ∈
A2∩ ({4c+10,2c+5})⊆A2∩ (A2), a con adic-
ion since A2∩ (A2)=∅by (1). Simila ly, we canno
ha e 7c+15 ∈A3, o o he wisewewouldha e7c+
15 ∈A3∩ ({2c+6,4c+9})⊆A3∩ (A3), a con a-
dic ion again. I ollows ha 7c+15 ∈A1, i.e. (7c+
15)=d1,asclaimed.
Acco dingly, A1⊇{1,2,3,3c+7,7c+15},A2⊇
{c+3,c+4,4c+10,2c+5},and A3⊇{2c+6,4c+
9}.Wenowshow6c+14 ∈A3.Ce ainly,wecanno ha e
6c+14 ∈A1, o o he wisewewouldha e7c+15 ∈
A1∩ ({1,6c+14})⊆A1∩ (A1), a con adic ion
since A1∩ (A1)=∅by (1). Analogously, he elemen
6c+14 does no belong o A2, o o he wisewewould
ha e 6c+14 ∈A2∩ ({c+4,4c+10})⊆A2∩ (A2),
a con adic ion again. I ollows ha 6c+14 ∈A3, i.e.
(6c+14)=d3,asclaimed.
Hence, A1⊇{1,2,3,3c+7,7c+15},A2⊇{c+
3,c+4,4c+10,2c+5},and A3⊇{2c+6,4c+9,
6c+14}. We now show c+5/∈A1,c+5/∈A2and
c+5/∈A3. In ac , i does no hold ha c+5∈A1,
o o he wise we would ha e c+5∈A1∩ ({2,3})⊆
A1∩ (A1), a con adic ion since A1∩ (A1)=∅ by
(1). We canno ha e c+5∈A2, o o he wise we would
ha e 4c+10 ∈A2∩ ({2c+5,c+5})⊆A2∩ (A2),
a con adic ion since A2∩ (A2)=∅by (1). We canno
ha e c+5∈A3, o o he wisewewouldha e6c+14 ∈
A3∩ ({4c+9,c+5})⊆A3∩ (A3), a con adic ion
since A3∩ (A3)=∅by (1).
This subcase is o e .
He e is an ou line o he p oo in Case 1:
Case 1.1
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩
(3c+7)=d1
⎧
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎩
(4c+10)=d2(2c+5)=d2
(2c+5)=d3
(4c+10)=d3(4c+9)=d2
(4c+9)=d3
(3c+7)=d3⎧
⎪
⎪
⎨
⎪
⎪
⎩
(c+5)=d2(3c+9)=d1
(3c+9)=d3
(c+5)=d3(5c+12)=d1
(5c+12)=d2
Case 1.2
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩
(c+5)=d1
⎧
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎩
(3c+8)=d1(4c+11)=d2
(4c+11)=d3
(3c+8)=d3(5c+12)=d1
(5c+12)=d2
(c+5)=d3⎧
⎪
⎪
⎨
⎪
⎪
⎩
(3c+9)=d1(4c+10)=d2
(4c+10)=d3
(3c+9)=d2(5c+12)=d1
(5c+12)=d3
The o he ou cases we e ob ained in a simila way.
We now p esen wo independen compu a ional
p oo s o he uppe bound.
Compu a ional Lemma 2.1. Le c>1andXc=
{1,2,3,c+2,c+3,c+4,2c+4,2c+5,2c+6,3c+
5,3c+6,3c+7,4c+7,4c+8,4c+9,5c+9,5c+
10,5c+11,6c+10,6c+11,6c+12,7c+13,8c+14,
8c+15,9c+16,9c+17,10c+18,10c+19,11c+20,
12c+21,13c+22} hen:
(1) We ha e Xc⊆[1,13c+22] and |Xc|=31.
(2) Fo e e y pa i ion o Xcin o h ee subse s
A1,A2,A3,someAicon ains a monoch oma ic
solu ion o x1+x2+c=x3,x1= x2.
P oo .
1. This is i ial.
2. We ha e checked he esul ans o ming he p ob-
lem in o a Boolean sa is iabili y p oblem and sol -
ing i wi h a SAT sol e [Heule XX]andusing
CBack [Helsgaun 95].
Compu a ional Lemma 2.2. Fo c=1, le X=
{1,2,...,18,20,22,25,26,28,29,31,33,35} hen:
1. We ha e X⊆[1,35].
2. Fo e e y pa i ion o Xin o h ee subse s
A1,A2,A3,someAicon ains a monoch oma ic
solu ion o x1+x2+c=x3,x1= x2.
The p oo is simila o Lemma 2.1.
In Sec ion 4, he p oo o he ollowing esul is gi en
in de ail.
Compu a ional Theo em 2.1. Fo e e y c>0,we ha e
WR2(3,c)=13c+22.
3. Exac alues o weak Rado numbe s WRk(2,c)
o some k>2
In his sec ion, we p o e ha WR3(2,c)=5c+24 i
cis e en, WR4(2,c)=6c+52, WR5(2,2)=109,and
WR5(2,4)=123.In addi ion, we o mula e Co olla y
3.1,which ela esWRk(2,c)and a lowe bound on he
weak Schu numbe WSk(2),leadingus o o mula e
Conjec u e 3.1.
3.1. The weak Rado numbe sWR3(2,c)
Fo c=0, [Blancha d e al. 06]ob ained heweakSchu
numbe WS3(2)=WR3(2,0)=24. A pa i ion which
is ee o monoch oma ic solu ions o he equa ion
x1+x2+x3+c=x4is A1=[1,5] ∪[21,23] and A2=
[6,20].
Fo c≥0andodd,WR3(2,c)≥R3(2,c)=∞[Schaal
93].
Le us i s conside helowe bound o anyc≥0and
e en.
Lemma 3.1. We ha e WR3(2,c)≥5c+24 o any c ≥0
and e en.
P oo . Fo e e y e en in ege c≥0, i is easy o e i y ha
he 2-colo ing
:[1,5c+23] −→ { d1,d2},
whe e d1,d2 ep esen 2 di e en colo s, de ined by
(x)=⎧
⎨
⎩
d1i 1 ≤x≤c+5,
d2i c+6≤x≤4c+20,
d1i 4c+21 ≤x≤5c+23
has no monoch oma ic solu ions o he equa ion x1+
x2+x3+c=x4such ha xi= xjwhen i= j.
Compu a ional Lemma 3.1. We ha e WR3(2,2)=34.
A pa i ion which is ee o monoch oma ic solu ions
o he equa ion x1+x2+x3+c=x4is A1=[1,7] ∪
[29,33] and A2=[8,28].
Ino de op o e heuppe bounds,weshalluse he
ollowing esul :
Compu a ional Lemma 3.2. Le c≥4 and e en. I
l=c/2, hen he se Yl={1,2,3,4,2+l,3+l,4+
l,3+2l,4+2l,5+2l,6+2l,7+2l,8+2l,6+3l,
7+3l,8+3l,6+4l,9+4l,11 +5l,10 +6l,12 +6l,
13 +7l,14 +8l,15 +8l,16 +8l,18 +8l,21 +8l,
23 +10l,24 +10l} e i ies:
1. We ha e Yl⊆[1,24 +10l].
2. Fo e e y pa i ion o Ylin o wo subse s A1,A2,
some Aicon ains a monoch oma ic solu ion o
x1+x2+x3+c=x4,xi= xj,wi hi= j.
In he p oo o Lemma 3.2, we p oceed simila ly o
Lemma 2.1.
The e o e, we conclude wi h he ollowing esul :
Compu a ional Theo em 3.1. Fo e e y c≥0, we ha e
WR3(2,c)=∞i codd,
5c+24 i ce en.
3.2. The weak Rado numbe sWR4(2,c)
Fo c=0, he weak Schu numbe WS4(2)=
WR4(2,0)=52 was ob ained [Sanz 10]. A pa i ion
which is ee o monoch oma ic solu ions o he equa ion
x1+x2+x3+x4+c=x5is A1=[1,9] ∪[46,51] and
A2=[10,45].
Wenowconside helowe bound o anyc≥0.
Lemma 3.2. We ha e WR4(2,c)≥6c+52 o any c ≥0.
P oo . Fo e e y in ege c≥0, i is easy o e i y ha he
2-colo ing
:[1,6c+51] −→ { d1,d2}
de ined by
(x)=⎧
⎨
⎩
d1i 1 ≤x≤c+9,
d2i c+10 ≤x≤5c+45,
d1i 5c+46 ≤x≤6c+51
has no monoch oma ic solu ions o he equa ion x1+
x2+x3+x4+c=x5such ha xi= xjwhen i= j.
In o de o p o e he opposi e inequali y, we shall use
he ollowing esul :
Compu a ional Lemma 3.3. Le c≥1. The se
Zc={1,2,3,4,5,6,8,c+9,c+10,c+11,c+12,
c+13,c+14,c+15,2c+16,2c+17,2c+18,2c+
19,2c+20,2c+21,2c+22,2c+24,3c+32,4c+33,
5c+43,5c+44,5c+45,5c+46,6c+52} e i ies:
1. Zc⊆[1,6c+52].
2. Fo e e y pa i ion o Zcin o wo subse s A1,A2,
some Aicon ains a monoch oma ic solu ion o
x1+x2+x3+x4+c=x5,xi= xj,wi hi= j.
In he p oo o Lemma 3.3, we use simila easonings
o hose es ablished in Lemma 2.1 and Lemma 3.2.
The e o e, we conclude wi h he ollowing esul :
Compu a ional Theo em 3.2. Fo e e y c≥0, we ha e
WR4(2,c)=6c+52.
3.3. The weak Rado numbe sWR5(2,2)and
WR5(2,4)
The weak Rado numbe s WR5(2,2)and WR5(2,4)
ha e been ob ained h ough back ack p og amming
[Helsgaun 95]andby ans o ming hep oblemin oa
Boolean sa is iabili y p oblem and sol ing i wi h a SAT
sol e . In he Sec ions 4.4,5.4,and5.5, he esul s a e
shown.
In hecaseo WR5(2,2), back ack p og amming
shows h ee pa i ions, which a e ee o monoch oma ic
solu ions o he equa ion x1+x2+x3+x4+2=x5,
xi= xj,wi hi= j.Thesea e
A1=[1,16] ∪[97,108],A2=[17,96].
A1=[1,20] ∪[94,108],A2={2}∪[21,93].
A1={1}∪[21,92],A2=[2,20] ∪[93,108].
The e o e, we ha e ha 109 is he lowe bound o
WR5(2,2).InSec ion 4.4,weshow ha WR5(2,2)≤109.
In he case o WR5(2,4),apa i ion eeo monoch o-
ma ic solu ions o he equa ion x1+x2+x3+x4+4=
x5,xi= xj,wi hi= j,is:
A1=[1,18] ∪[109,122],A2=[19,108].
The e o e, we ha e ha 123 is he lowe bound o
WR5(2,4).InSec ion 5.4,weshow ha WR5(2,4)≤123.
Hence, we conclude wi h he ollowing esul s:
Compu a ional Theo em 3.3. We ha e WR5(2,2)=109.
Compu a ional Theo em 3.4. We ha eWR5(2,4)=123.
3.4. Weak Schu numbe sWS5(2)and lowe bounds
In his subsec ion, we ob ain he weak Schu numbe
WS5(2)=101 and we show a lowe bound o he weak
Schu numbe s WSk(2).
To ob ain he lowe bound WS5(2)≥101, he ollow-
ing pa i ion o [1,100] is conside ed A1={1}∪[20,86]
and A2=[2,19] ∪[87,100].
In o de o ob ain he uppe bound WS5(2)≤101, we
shall use he ollowing esul :
Compu a ional Lemma 3.4. The se U=[1,7] ∪
{9,11,13}∪[15,17] ∪[19,23] ∪[25,27] ∪{29,31,35,
39}∪[43,45] ∪{51,75,87,101}⊆[1,101] e i ies ha
o e e y pa i ion o Uin o wo subse s A1,A2,some
Aicon ains a monoch oma ic solu ion o x1+x2+x3+
x4+x5=x6,xi= xj,wi hi= j.
In he p oo o Lemma 3.4, we use simila easonings
o hose es ablished in Lemma 2.1 and Lemma 3.2.
The e o e, we conclude wi h he ollowing esul :
Compu a ional Theo em 3.5. We ha e WS5(2)=101.
He e,belowcanbeseeinganewlowe bound o he
weak Schu numbe s WSk(2).
Lemma 3.3. We ha e WSk(2)≥(k+2)Tk−2k, wi h
Tk=(1+k)
2k.
P oo . I is easy o e i y ha he 2-colo ing
:[1,(k+2)Tk−2k−1] −→ { d1,d2}
de ined by
(x)=⎧
⎨
⎩
d1i 1≤x≤Tk−1,
d2i Tk≤x≤(k+1)Tk−k−1,
d1i (k+1)Tk−k≤x≤(k+2)Tk−2k−1
has no monoch oma ic solu ion o he equa ion x1+x2+
···+xk=xk+1such ha xi= xjwhen i= j.
Conside he lowe bound LWS k(2)=(k+2)Tk−2k.
We o mula e he ollowing Co olla ies ha ela e he
weak Rado numbe s WRk(2,c)wi h he lowe bound
LWS k(2).
Co olla y3.1. Le c be a in ege wi h c ≥0and k =2,3,4.
Then, WRk(2,c)=(k+2)c+LWS k(2).
Co olla y 3.2. Le c =2o c =4and k =5.Then,
WRk(2,c)=(k+2)c+LWS k(2).
The exac alues WR2(2,c), WR3(2,c), WR4(2,c),
WR5(2,2), and WR5(2,4)ha e been ob ained. All o
hem e i y he ollowing Conjec u e 3.1.
Conjec u e 3.1. Le cand kbe in ege s wi h c≥0andk≥
2, we ha e WRk(2,c)=(k+2)c+LWS k(2),whenco k
is e en.
4. Re o mula ion as a SAT p oblem
Ou idea o cons uc ing he abo e pa i ions is o
exp ess he co esponding combina o ial cons ain s as
Boolean sa is iabili y p oblems, o be hen ed in o a SAT
sol e . See [D ans ield e al. 04,Eliahou e al. 12,He wig
e al. 07,Kou il and Paul 08,Robillia d e al. 10] o ea lie
success ul uses o SAT sol e s in combina o ial numbe
heo y. The speci ic SAT sol e used he e, is he Ma ch
w, he gold medal winne o he 2011 In e na ional SAT
Compe i ion [Heule XX]. Recall ha a logical exp ession
o e Boolean a iables x1,...,xnis said o be sa is iable i
he e is an assignmen o he xi’s o T ue o False in such
a way ha he alue e alua es o T ue.
4.1. Seeking WR2(3,c)by compu e
Le c>1andconside hese Xco Lemma 2.1.Tha
is, Xc={1,2,3,c+2,c+3,c+4,2c+4,2c+5,2c+
6,3c+5,3c+6,3c+7,4c+7,4c+8,4c+9,5c+9,
5c+10,5c+11,6c+10,6c+11,6c+12,7c+13,
8c+14,8c+15,9c+16,9c+17,10c+18,10c+19,
11c+20,12c+21,13c+22}.
Le cbe a 3-colo ing o [1,13c+22]:
c:[1,13c+22] −→ { d1,d2,d3},
and le X∗={(a,b):ac +b∈Xc o any c≥1}, i.e.
X∗={(0,1), (0,2), (0,3), (1,2), (1,3), (1,4), (2,4),
(2,5), (2,6), (3,5), (3,6), (3,7), (4,7), (4,8), (4,9),
(5,9), (5,10), (5,11), (6,10), (6,11), (6,12), (7,13),
(8,14), (8,15), (9,16), (9,17), (10,18), (10,19), (11,
20), (12,21), (13,22)}.
Fo any (a,b)∈X∗,weconside woBoolean a iables
φ((a,b)) and ψ((a,b)) de ined as ollow:
φ((a,b)) =T ue i c(ac +b)=d1o d2,
False i c(ac +b)=d3.
ψ((a,b)) =T ue i c(ac +b)=d1o d3,
False i c(ac +b)=d2.
Thus, o any n∈X∗we ha e ha φ(n)is T ue o ψ(n)is
T ue.
Le S={(n1,n2,n3)|ni=(ai,bi)∈X∗, e i ying
ha a1+b1<a2+b2,a1+a2+1=a3,b1+b2=
b3}.
Fo any s=(n1,n2,n3)∈S,weconside h ee
clauses:
p(s)=(¬φ(n1)∨¬ψ(n1)∨¬φ(n2)∨¬ψ(n2)
∨¬φ(n3)∨¬ψ(n3)),
q(s)=(¬φ(n1)∨ψ(n1)∨¬φ(n2)∨ψ(n2)
∨¬φ(n3)∨ψ(n3)), and
(s)=(φ(n1)∨¬ψ(n1)∨φ(n2)∨¬ψ(n2)
∨φ(n3)∨¬ψ(n3)).
Then, p(s)is sa is iable i and only i c(n)= d1 o some
n∈s,q(s)is sa is iable i and only i c(n)= d2 o some
n∈sand (s)is sa is iable i and only i c(n)= d3 o
some n∈s, husp(s)∧q(s)∧ (s)a esa is iablei and
only i cdoes no induce on sa monoch oma ic solu ion
o he equa ion x1+x2+c=x3.
Le C=
s∈S
(p(s)∧q(s)∧ (s)) and
D=
n∈X∗
(φ(n)∨ψ(n)).
Clea ly, C∧Dis sa is iable i and only i he es ic ion o
c o Xcis a 3-colo ing wi hou monoch oma ic solu ion
o he equa ion.
The SAT-Sol e shows ha C∧Dis no sa is iable,
he e o e he e does no exis a 3-colo ing o he se s
Xcand [1,13c+22] wi hou monoch oma ic solu ion.
Thus, WR2(3,c)≤13c+22.
4.2. Seeking WR3(2,c)by compu e
Le c=2l≥4and hese Ylo Lemma 3.2.Tha is,Yl=
{1,2,3,4,2+l,3+l,4+l,3+2l,4+2l,5+2l,6+
2l,7+2l,8+2l,6+3l,7+3l,8+3l,6+4l,9+4l,
11 +5l,10 +6l,12 +6l,13 +7l,14 +8l,15 +8l,
16 +8l,18 +8l,21 +8l,23 +10l,24 +10l}.
Le lbe a 2-colo ing o [1,24 +10l],
l:[1,24 +10l]−→ { d1,d2},
and le Y∗={(a,b):al +b∈Yl o any l≥2}, i.e.
Y∗={(0,1), (0,2), (0,3), (0,4), (1,2), (1,3), (1,4),
(2,3), (2,4), (2,5), (2,6), (2,7), (2,8), (3,6), (3,7),
(3,8), (4,6), (4,9), (5,11), (6,10), (6,12), (7,13), (8,
14), (8,15), (8,16), (8,18), (8,21), (10,23), (10,24)}.
Fo any (a,b)∈Y∗,weconside aBoolean a iable
φ((a,b)) de ined as ollows:
φ((a,b)) =T ue i l(2al +b)=d1,
False i l(2al +b)=d2.
Le S={(n1,...,n4)|ni=(ai,bi)∈Y∗, e i ying
ha 4a1+b1<4a2+b2<4a3+b3,a1+a2+a3+
2=a4,b1+b2+b3=b4}Fo any s=(n1,...,n4)∈
S,weconside woclauses:
p(s)=(φ(n1)∨φ(n2)∨φ(n3)∨φ(n4))
and
q(s)=(¬φ(n1)∨¬φ(n2)∨¬φ(n3)∨¬φ(n4)).
Then p(s)is sa is iable i and only i l(n)= d2 o some
n∈sand q(s)is sa is iable i and only i l(n)= d1 o
some n∈s, husp(s)∧q(s)a e sa is iable i and only i
ldoes no induce on sa monoch oma ic solu ion o he
equa ion x1+x2+x3+x4+c=x5.
Le C=
s∈S
(p(s)∧q(s)).
Clea ly Cis sa is iable i and only i he es ic ion o l
o Ylis a 2-colo ing wi hou monoch oma ic solu ion o
he equa ion.
The SAT-Sol e shows ha Cis no sa is iable, he e-
o e he e does no exis a 2-colo ing o he se s Yl
and [1,24 +10l] wi hou monoch oma ic solu ion. Thus
WR3(2,2l)≤24 +10l.
4.3. Seeking WR4(2,c)by compu e
Le Zcbe he se o Lemma 3.3.Tha is,Zc=
{1,2,3,4,5,6,8,c+9,c+10,c+11,c+12,c+13,
c+14,c+15,2c+16,2c+17,2c+18,2c+19,2c+
20,2c+21,2c+22,2c+24,3c+32,4c+33,5c+
43,5c+44,5c+45,5c+46,6c+52}Le cbe a 2-
colo ing o [1,6c+52],
c:[1,6c+52] −→ { d1,d2}
and le Z∗={(a,b):ac +b∈Zc o any c≥0}, i.e.
Z∗={(0,1), (0,2), (0,3), (0,4), (0,5), (0,6), (0,8),
(1,9), (1,10), (1,11), (1,12), (1,13), (1,14), (1,15),
(2,16), (2,17), (2,18), (2,19), (2,20), (2,21), (2,22),
(2,24), (3,32), (4,33), (5,43), (5,44), (5,45), (5,46),
(6,52)}.Fo any(a,b)∈Z∗we conside a Boolean
a iable φ((a,b)) de ined as ollow:
φ((a,b)) =T ue i c(ac +b)=d1,
False i c(ac +b)=d2.
Le S ={(n1,...,n5)|ni=(ai,bi)∈Z∗, e i ying
ha b1<b2<b3<b4,a1+a2+a3+a4+1=
a5,b1+b2+b3+b4=b5}.
Fo any s=(n1,...,n5)∈S,weconside wo
clauses:
p(s)=(φ(n1)∨φ(n2)∨φ(n3)∨φ(n4)∨φ(n5))
and
q(s)=(¬φ(n1)∨¬φ(n2)∨¬φ(n3)∨¬φ(n4)
∨¬φ(n5)).
Then, p(s)is sa is iable i and only i c(n)= d2 o some
n∈sand q(s)is sa is iable i and only i c(n)= d1 o
some n∈s, husp(s)∧q(s)a esa is iablei andonlyi
cdoes no induce on sa monoch oma ic solu ion o he
equa ion x1+x2+x3+x4+c=x5.
Le C =
s∈S
(p(s)∧q(s)).
Clea ly, C is sa is iable i and only i he es ic ion o c
o Zcis a 2-colo ing wi hou monoch oma ic solu ion o
he equa ion.
The SAT-Sol e shows ha C is no sa is iable, he e-
o e he e does no exis a 2-colo ing o he se s Zc
and [1,6c+52] wi hou monoch oma ic solu ion. Thus
WR4(2,c)≤6c+52.
4.4. Seeking WR5(2,2)by compu e
Le T2=[1,109]. Le be a 2-colo ing o T2.Fo any
n∈T2,weconside aBoolean a iableφ(n)de ined as
ollow:
φ(n)=T ue i (n)=d1,
False i (n)=d2.
Le S ={(n1,...,n6)|1≤n1<n2<···<n6≤
109, and n1+n2+n3+n4+n5+2=n6}.
Fo any s=(n1,...,n6)∈S,weconside wo
clauses:
p(s)=(φ(n1)∨φ(n2)∨φ(n3)∨φ(n4)∨φ(n5)
∨φ(n6))
and
q(s)=(¬φ(n1)∨¬φ(n2)∨¬φ(n3)∨¬φ(n4)
∨¬φ(n5)∨¬φ(n6)).
Then, p(s)is sa is iable i and only i (n)= d2 o some
n∈sand q(s)is sa is iable i and only i (n)= d1 o
some n∈s, husp(s)∧q(s)a e sa is iable i and only i
does no induce on sa monoch oma ic solu ion o he
equa ion x1+x2+x3+x4+x5+2=x6.
Le C =
s∈S
(p(s)∧q(s)).
Clea ly, C is sa is iable i and only i is a 2-
colo ing wi hou monoch oma ic solu ion o he
equa ion.
The SAT-Sol e shows ha C is no sa is iable, he e-
o e he e does no exis a 2-colo ing o he se T2
wi hou monoch oma ic solu ion. Thus, WR5(2,2)≤
109.
This esul can be gene alized o p o e WR5(2,4) ࣘ
123.
5. Back ack p og amming in language C
5.1. Seeking WR2(3,c)by compu e
#include "CBack.c"
in i, j, k, l, N, Coun , Solu;
FILE * p;
oid P in Sol()
{ p in ( p,"N =%d is he maximum wi h %d solu ions. n",Coun ,Solu); }
in P oblem()
{
in , , c, a, , ;
in R[4][600]={0};
in T[4][600]={0};
in L[4]={0};
in VR[31]={0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5, 5, 5, 6, 6, 6, 7, 8, 8, 9, 9,10,
10,11,12,13};
in VT[31]={1,2,3,2,3,4,4,5,6,5,6,7,7,8,9,9,10,11,10,11,12,13,14,15,16,17,18,
19,20,21,22};
Solu=0;
Fiasco=P in Sol;
N=Selec (30,31);
o ( =0; <=N-1; ++)
{
c=Choice(3);
o (i =0; i <=L[c]-1; i++)
o (j =0; j <i; j++)
{
i (VR[ ]==R[c][i]+R[c][j]+1&&VT[ ]==T[c][i]+T[c][j])
Back ack();
}
R[c][L[c]] =VR[ ];
T[c][L[c]] =VT[ ];
L[c]++;
}
Coun =0;
Solu++;
o (c =1; c <=3; c++)
{
Coun +=L[c];
o ( =0; <=L[c]-1; ++)
{
i (R[c][ ]==0) p in ( p,"(%d)",T[c][ ]);
else
i (R[c][ ]==1) p in ( p,"(%c%c%d)",’a’,’+’,T[c][ ]);
else p in ( p,"(%d%c%c%d)",R[c][ ],’a’,’+’,T[c][ ]);
}
/* p in ( p,"((%d)) n",L[c]); */
p in ( p," n");
}
p in ( p,"%c",’ n’);
p in (" Solu ions : %d n",Solu);
Back ack();
}
main(in a gc, cha *a g [])
{
cha s [80];
s cpy (s ,a g [0]);
s ca (s ,". x ");
p = open(s ,"w");
Back acking(P oblem())
close( p);
}