%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-23/document.tex.
%%%%
%% Standard package list
\documentclass[letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage[top=3cm, bottom=3cm, left=3.5cm, right=3.5cm]{geometry}
\usepackage[onehalfspacing]{setspace}
\usepackage{amsmath,amssymb,amsthm,wasysym}
\usepackage{nicefrac,booktabs}
\usepackage{mathptmx}
\usepackage{cite}
\usepackage[colorlinks=true]{hyperref}
%% Various helpers for Tom's papers
\newcommand{\gs}{\textnormal{gs}}
\newcommand{\ord}{\textnormal{ord}}
\newcommand{\Exp}{\textnormal{Exp}}
\newcommand{\Log}{\textnormal{Log}}
\newcommand{\lcm}{\textnormal{lcm}}
\newcommand{\range}{\textnormal{range}}
\newcommand{\NR}{\textnormal{NR}}
\newcommand{\Mod}[1]{\left(\textnormal{mod}~#1\right)}
\newcommand{\ap}[2]{\left\langle #1;#2 \right\rangle}
\newcommand{\summ}[1]{\sum_{k=1}^m{#1}}
\newcommand{\bt}[1]{{{#1}\mathbb{N}}}
\newcommand{\fp}[1]{{\left\lbrace{#1}\right\rbrace}}
\newcommand{\intv}[1]{{\left[1,{#1}\right]}}
%% Lifted from http://stackoverflow.com/questions/2767389/referencing-a-theorem-like-environment-by-its-name
%% This lets me do things like "Theorem A" and have the references work properly.
\makeatletter
\let\@old@begintheorem=\@begintheorem
\def\@begintheorem#1#2[#3]{%
\gdef\@thm@name{#3}%
\@old@begintheorem{#1}{#2}[#3]%
}
\def\namedthmlabel#1{\begingroup
\edef\@currentlabel{\@thm@name}%
\label{#1}\endgroup
}
\makeatother
% end lift
\newtheoremstyle{namedthrm}
{}{}{}{}{}{}{ } % This last space needs to be there
{\bf\thmname{#1} \thmnote{#3}.}
%% End reference hack
%% Document start
\date{}
\begin{document}
%% Content start
\newtheorem{thrm}{Theorem}
\title{Monochromatic Homothetic Copies of $\{1, 1+s, 1+s+t\}$ }
\author{Tom C. Brown, Bruce M. Landman and
Marni Mishna\footnote{The first and third authors were partially supported by NSERC.}}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, Bruce~M. Landman, and Marni Mishna, \emph{Monochromatic
homothetic copies of $\lbrace s, 1+s, 1+s+t \rbrace$ }, Canad. Math. Bull.
\textbf{40} (1997), 149--157.}\bigskip\end{center}
\newcommand{\floor}[1]{{\left\lfloor{#1}\right\rfloor}}
\newcommand{\ceil}[1]{{\left\lceil{#1}\right\rceil}}
\begin{abstract}
For positive integers $s$ and $t$, let $f(s,t)$ denote the smallest
positive integer $N$ such that every 2-coloring of $[1,N] = \{1,2,\ldots,N\}$
has a monochromatic homothetic copy of $\{1,1+s,1+s+t\}$.
We show that $f(s,t) = 4(s+t)+1$ whenever $s/g$ and $t/g$ are not congruent
to 0 (modulo 4), where $g = \gcd(s,t)$. This can be viewed as a generalization
of part of van der Waerden's theorem on arithmetic progressions, since the
3-term arithmetic progressions are the homothetic copies of $\{1,1+1,1+1+1\}$.
We also show that $f(s,t) = 4(s+t)+1$ in many other cases (for example,
whenever $s>2t>2$ and $t$ does not divide $s$), and that $f(s,t)\leq4(s+t)+1$
for all $s,t$.
Thus the set of homothetic copies of $\{1,1+s,1+s+t\}$ is a set of triples with
a particularly simple Ramsey function (at least for the case of two colours),
and one wonders what other ``natural'' sets of triples, quadruples, etc.,
have simple (or easily estimated) Ramsey functions.
\end{abstract}
\section{Introduction}
Van der Waerden's Theorem on Arithmetic Progressions \cite{vanderwaerden1927}
states that for every positive integer $k$ there exists a smallest positive
integer $w(k)$ such that for every 2-coloring of $[1,w(k)] = \{1,2,\ldots,
w(k)\}$, there is a monochromatic $k$-term arithmetic progression. (In other
words, if $[1,w(k)]$ is partitioned in any way into two parts $A$ and $B$,
then either $A$ or $B$ must contain a $k$-term arithmetic progression.) The
only known non-trivial values of $w(k)$ are $w(3) = 9$, $w(4) = 35$, $w(5)
= 178$. Furthermore the estimation of the function $w(k)$ for large $k$ is
one of the most outstanding (and presumably one of the most difficult)
problems in Ramsey theory. For a discussion of this, see \cite{graham+rothschild+spencer1990}.
The function $w(k)$ is often called the \emph{Ramsey function} for the set
of $k$-term arithmetic progressions. Landman and Greenwell \cite{landman+greenwell1988,
landman+greenwell1990-1} considered the Ramsey function $g(n)$ of the set
of all $n$-term sequences that are homothetic copies (see the definition
below) of $\{1,2,2+t,2+t+t^2,\ldots,2+t+t^2+\cdots+t^{n-2}\}$ for some
positive integer $t$. They obtained a lower bound for $g(n)$ and an upper
bound for $g^{(r)}(3)$, where the $(r)$ indicates that $r$ colours are
used. Other ``substitutes'' for the set of $k$-term arithmetic progressions
were introduced in \cite{brown+erdos+freedman1990}.
In contrast, in this paper we consider the Ramsey function associated with
a much smaller set of sequences, namely the set of homothetic copies of
$\{1,1+s,1+s+t\}$ for given positive integers $s$ and $t$.
A \emph{homothetic copy} of $\{1,1+s,1+s+t\}$ is any set of the form
$\{x,x+ys,x+ys+yt\}$, where $x$ and $y$ are positive integers. From now
on, let us agree to use the term ``$(s,t)$-progression'' to refer to a
homothetic copy of $\{1,1+s,1+s+t\}$.
Instead of considering 3-term arithmetic progressions, as in the case
$k=3$ of van der Waerden's theorem, we consider the set of $(s,t)$-progressions
for given positive integers $s$ and $t$. (Note that the $(1,1)$-progressions
are the 3-term arithmetic progressions.)
For positive integers $s$ and $t$ we define $f(s,t)$ to be the smallest
positive integer $N$ such that every 2-colouring of $[1,N]$ has a monochromatic
$(s,t)$-progression. Note that $f(s,t) = f(t,s)$. We will use this fact
several times.
We show that for all positive integers $s$ and $t$, if $s/g\not\equiv0$ and $t/g\not\equiv0$
(mod 4), where $g = \gcd(s, t)$, then $f(s,t) = 4(s + t) + 1$. A special case
of this is $w(3) = f(1,1) = 9$. Thus this result can be viewed as a
generalization of the case $k = 3$ of van der Waerdenâ€™s theorem.
We also show that $f(s,t)\leq4(s + t) + 1$ for all $s$ and $t$, and we show
that even if $s/g\equiv0$ or $t/g\equiv0$ (mod 4), the equality $f(s,t) =
4(s + t) + 1$ still holds, except for a small number of possible exceptions.
For example, we are unable to find the exact value of $f(4m,1)$, although we
show in Theorem \ref{t4} that $4(4m + 1)\leq f(4m,1)\leq 4(4m + 1) + 1$.
The remaining cases where $f(s,t)$ is unknown are described in Section \ref{s4}.
\section{Upper bounds}
First we give a simple proof of the weak bound $f(s,t) \leq 9s + 8t$,
which is subsequently refined (in Theorem \ref{t2} below) to give the stronger
bound $f(s,t)\leq4(s + t) + 1$. The equality $w(3) = 9$ will be used in our
proof of this weak bound, but will not be used again.
We prove $f(s,t)\leq 9s + 8t$ by contradiction. Assume that $f(s,t)>9s + 8t$,
and let $[1,9s + 8t]$ be 2-coloured, using the colours Red and Blue, in such
a way that there is no monochromatic $(s,t)$-progression. Since $w(3) = 9$,
the set $\{s, 2s, 3s, \ldots, 9s\}$ contains a monochromatic (say in the
colour Red) 3-term arithmetic progression. Let us suppose, in order to
simplify our notation, that this Red progression is $\{s, 5s,9s\}$. (In all
other cases, the argument is essentially the same.)
Consider the $(s,t)$-progressions $\{s,5s,5s+4t\}$, $\{5s,9s,9s + 4t\}$,
$\{s, 9s, 9s + 8t\}$. Since by assumption none of these is monochromatic,
and $s$, $5s$, $9s$ are all Red, it follows that $\{5s + 4t, 9s + 4t, 9s + 8t\}$
is a Blue $(s,t)$-progression, a contradiction, completing the proof.
The following theorem will be useful in obtaining both upper and lower bounds for
$f(s,t)$.
\begin{thrm}\label{t1} Let $s,t,c$ be positive integers. Then $f(cs,ct) =
c(f(s,t)-1)+1$. \end{thrm}
\begin{proof} Let $M = f(s,t)$. Let $B$ be a 2-colouring of $[1,c(M-1)+1]$. Since
every 2-colouring of $[0,M-1]$ contains a monochromatic $(s,t)$-progression, every
2-colouring of $\{1,c+1,2c+1,\ldots,(M-1)c+1\}$ contains a monochromatic $(cs,ct)$-progression.
Thus, $f(cs,ct)\leq c(M-1)+1$.
On the other hand, we know there is a 2-colouring, B, of $[1,M-1]$ that
contains no monochromatic $(s,t)$-progressions. Define $B'$ on $[1, c(M-1)]$ by
$B'([c(i-1)+1,ci]) = B(i)$, for $i = 1,\ldots,M-1$. We will show that $B'$ avoids
monochromatic $(cs,ct)$-progressions, which will complete the proof.
Assume, by way of contradiction, that $x_1, x_2, x_3$ is a $(cs,ct)$-progression,
contained in $[1, c(M-1)]$, that is monochromatic under $B'$. Then there exists
$r>0$ such that $x_3- x_2 = rct$, $x_2-x_1 = rcs$. Let $y_j = \ceil{x_j/c}$ for
$j = 1,2,3$. Then $y_3 - y_2 = \ceil{x_3/c} - \ceil{x_2/c} = rt$, and similarly
$y_2 - y_1 = rs$.
Hence $y_1, y_2, y_3$ is an $(s, t)$-progression. Also, $B(y_j) = B(\ceil{x_j/c})
= B' (x_j)$, for each j. This contradicts our assumption that there is no
monochromatic $(s,t)$-progression relative to the colouring $B$.
\end{proof}
Note that this proof easily extends to a proof that if $f(a_1,\ldots,a_k) = M$,
then $f(ca_1,\ldots,ca_k) = c(M-1)+1$, where $f(a_1,\ldots,a_k)$ denotes the
least positive integer $N$ such that every 2-coloring of $[1,N]$ will contain
a monochromatic homothetic copy of $\{1,1+a_1,1+a_1+a_2,\ldots,1+a_1+a_2+\cdots+a_k\}$.
\begin{thrm}\label{t2} For all positive integers $s$ and $t$, $f(s,t)\leq 4(s+t)+1$.
\end{thrm}
\begin{proof} Let $s,t$ be given. We may assume without loss of generality that
$s\leq t$. We may also assume that $\gcd(s,t) = 1$, for if we knew the result in
this case then, with $g=\gcd(s,t)$, Theorem \ref{t1} would give $f(s,t)=g\ceil{f(s/g,t/g)-1}
+1\leq g[4(s/g+t/g)+1-1]+1 = 4(s+t)+1$.
Consider the following set of 20 triples contained in $[1,4(s+t)+1]$, which
are all $(s,t)$-progressions:
\[ \{ 1, s + 1, s + t + 1\}, \{ s + 1, 2s + 1, 2s + t + 1\} \]
\[ \{ 2s + 1, 3s + 1, 3s + t + 1\}, \{ 3s + 1, 4s + 1, 4s + t + 1\} \]
\[ \{ 1, 2s + 1, 2s + 2t + 1\}, \{ s + 1, 3s + 1, 3s + 2t + 1\} \]
\[ \{ 2s + 1, 4s + 1, 4s + 2t + 1\}, \{ 1, 3s + 1, 3s + 3t + 1\} \]
\[ \{ s + 1, 4s + 1, 4s + 3t + 1\}, \{ 1, 4s + 1, 4s + 4t + 1\} \]
\[ \{ s + t + 1, 2s + t + 1, 2s + 2t + 1\}, \{ 2s + t + 1, 3s + t + 1, 3s + 2t + 1\} \]
\[ \{3s + t + 1, 4s + t + 1, 4s + 2t + 1\}, \{ s + t + 1, 3s + t + 1, 3s + 3t + 1\} \]
\[ \{2s + t + 1, 4s + t + 1, 4s + 2t + 1\}, \{ s + t + 1, 4s + t + 1, 4s + 4t + 1\} \]
\[ \{2s + 2t + 1, 3s + 2t + 1, 3s + 3t + 1\}, \{ 3s + 2t + 1, 4s + 2t + 1, 4s + 3t + 1\} \]
\[ \{2s + 2t + 1, 4s + 2t + 1, 4s + 4t + 1\}, \{ 3s + 3t + 1, 4s + 3t + 1, 4s + 4t + 1\} \]
It is straightforward to check (under the assumptions that $s\leq t$ and $\gcd(s,t)
= 1$) that except in the cases $s = 1, 1 \leq t\leq 3$, the 15 integers which
appear in these 20 triples are distinct. It is then a simple matter to check all
2-colourings of these 15 integers and verify that each 2-colouring has a
monochromatic triple from the above list of 20 triples. (If one identifies these
15 integers with the numbers 1,2,\ldots,15 via the correspondence
\[ 1 \leftrightarrow 1, s + 1 \leftrightarrow 2, 2s + 1\leftrightarrow 3, 3s+1\leftrightarrow4, 4s+1\leftrightarrow5, \]
\[ s+t+1\leftrightarrow6, 2s+t+1\leftrightarrow7, 3s+t+1\leftrightarrow8, 4s+t+1\leftrightarrow9, \]
\[ 2s+2t+1\leftrightarrow10, 3s+2t+1\leftrightarrow11, 4s+2t+1\leftrightarrow12, \]
\[ 3s + 3t + 1\leftrightarrow13, 4s+3t+1\leftrightarrow14, 4s+4t+1\leftrightarrow15, \]
the resulting set of 20 triples contained in $[1,15]$ has a particularly pleasing
form.) The cases $s=1,1\leq t\leq 3$ can be checked separately. In all cases we
obtain $f(s,t)\leq 4(s+t)+1$.\end{proof}
\section{Lower bounds and exact values for $f(s,t)$}
\begin{thrm}\label{t3} Let $s,t$ be positive integers, and let $g=\gcd(s,t)$. If $s/g\not\equiv0$
and $t/g\not\equiv0$ (mod 4) then $f(s,t) = 4(s+t)+1$.\end{thrm}
\begin{proof} The proof splits naturally into two cases.
\paragraph{Case 1.} Assume that $s/g$ and $t/g$ are both odd. In view of Theorem \ref{t2},
we only need to show that $f(s,t) \geq 4(s+t)+1$.
First, assume $g=1$. Now colour $[1,4(s+t)]$ as
\[ 101010\cdots10~010101\cdots01, \]
where each of the two long blocks has length $2(s+t)$. Assume $x,y,z$ is a monochromatic
$(s,t)$-progression. Then $y=x+ds$ and $z=y+dt$, for some positive integer $d$. Let $B_1$
and $B_2$ represent $[1,2(s+t)]$ and $[2(s+t)+1,4(s+t)]$, respectively.
In case $d$ is odd, then $x$ and $y$ have opposite parity, and $y$ and $z$ have
opposite parity. Since $x$ and $y$ have the same colour and opposite parity, $x$
is in $B_1$, while $y$ is in $B_2$. Hence $z$ is in $B_2$, so that $y$ and $z$ cannot
have the same colour, a contradiction.
If $d$ is even, then $x$, $y$ and $z$ all have the same parity, so they all
must be in the same $B_i$. But then $d(s+t) = z - x \leq 2(s+t)$, and hence
$d=1$, a contradiction.
If $g$ is unequal to 1, then by Theorem \ref{t1} and the case in which $g=1$,
$f(s,t) = g[f(s/g,t/g)-1]+1\geq g[4(s/g+t/g)+1-1]+1=4(s+t)+1$. This finishes
the proof of Case 1.
\paragraph{Case 2.} Assume without loss of generality that $s/2\equiv2$ (mod 4).
First we assume that $g=1$. Then $s\equiv2$ (mod 4) and $t$ is odd.
By Theorem \ref{t2}, we only need to provide a 2-colouring of $[1,4(s+t)]$ that
contains no monochromatic $(s,t)$-progression. Let $C$ be the colouring
$11001100\cdots1100$ (i.e., $s+t$ consecutive blocks each having the form 1100).
We proceed by contradiction. Assume that $x,y,z$ is a monochromatic
$(s,t)$-progression. So there exists a $d>0$ such that $y-x = ds$ and $z-y = dt$.
By the way $C$ is defined, if $C(i) = C(j)$ and $j - i$ is even, then 4 divides
$j - i$. Now since $z - x = d(s+t) \leq 4(s+t) - 1$, we must have that $d < 4$.
The case $d = 2$ is impossible, for if $d = 2$, then $C(z) = C(x)$, $z - x =
d(s + t)$ is even, but 4 does not divide $z - x$, a contradiction. Hence $d$ is
odd. But then, since $s\equiv2$ (mod 4), $y - x$ is even yet 4 doesn't divide
$y - x$, again a contradiction.
This shows that $f(s,t) \geq 4(s+t)+1$ in the case $g=1$.
If $g$ is unequal to 1, we proceed just as at the end of Case 1.\end{proof}
Suppose that $s/g\equiv0$ (mod 4), where $g = \gcd(s,t)$. Then $t/g$ is odd,
and in the case $t/g = 1$, that is, $t$ divides $s$, we have the following
result.
\begin{thrm}\label{t4} Let $m,t$ be positive integers. Then either
\[ f(4mt,t) = 4(4mt +t) - t + 1 \text{ or } f(4mt,t) = 4(4mt+t)+1. \]
\end{thrm}
\begin{proof} By Theorem \ref{t1}, it is sufficient to show that $4(4m+1)\leq f(4m,1)
\leq 4(4m+1)+1$. By Theorem \ref{t2}, we only need to show that $4(4m+1)\leq f(4m,1)$.
Thus it suffices to find a 2-colouring of $[1,16m+3]$ that avoids monochromatic
$(4m,1)$-progressions. Let $\chi$ be the colouring $1A0B0C1D0$, where
\begin{align*}
A &= 00110011\cdots0011 \text{ has length } 4m \\
B &= 11001100\cdots11 \text{ has length } 4m-2 \\
C &= 11001100\cdots1100 \text{ has length } 4m \\
D &= 00110011\cdots0011 \text{ has length } 4m.
\end{align*}
Assume $x,y,z$ is a monochromatic $(4m,1)$-progression. We shall reach a contradiction.
We know there exists a positive integer $d$ such that $y-x = 4md$ and $z-y=d$. Hence,
$d(4m+1)\leq16m+2$, so that $d\leq3$. Let
\begin{align*}
S_1 &= [2,4m+1] \text{ (corresponds to $A$ above)} \\
S_2 &= [4m+3,8m] \text{ (corresponds to $B$ above)} \\
S_3 &= [8m+2,12m+1] \text{ (corresponds to $C$ above)} \\
S_4 &= [12m+3,16m+2] \text{ (corresponds to $D$ above).}
\end{align*}
\paragraph{Case 1.} $d = 1$. Then $y,z$ belong to the same $S_i$, for some $1\leq i\leq4$.
Denote by $S(i,j)$ the $j$th element of $S_i$. We see that $y = S(i,j)$ for some odd $j$.
Note that for each even $p$, if $i = 2$ or 4, then $\chi(S(i-1),p)$ is unequal to $\chi
(S(i,p-1))$. Now if $i=2$ or $i=4$, then $x = y-4m = S(i-1,j+1)$, so that (by the preceding
remark), $\chi(x)$ is different from $\chi(y)$, a contradiction. Now if $i = 3$ and $j>1$,
then $y - 4m = S(2, j-1)$, and $\chi(x) = \chi(y - 4m)$ is unequal to $\chi(y)$, a
contradiction. If $i = 3$ and $j = 1$, then $x = 4m + 2$ and $y = 8m + 2$, and these again
have different colours.
\paragraph{Case 2.} $d = 2$. Then $y - x = 8m$ and $z-y = 2$. If $\chi(y) = \chi(z)$ then
$y$ must be one of the following: $4m+1,8m,12m+1$; and since $y-x=8m$, this reduces the
possibilities for $y$ to only $12m+1$. However we see that $\chi(4m+1)$ is unequal to
$\chi(12m+1)$, a contradiction.
\paragraph{Case 3.} $d = 3$. Then $y-x = 12m$ and $z-y = 3$. Clearly $x$ belongs to $[1,4m]$,
so that $y$ belongs to $[12m+1,16m]$. Now $[1,4m]$ has colouring $1~0011\cdots001100~1$
while $[12m+1,16m]$ has colouring $0100110011\cdots001100$. Hence, since $\chi(x) = \chi(y)$,
$y$ belongs to the set $\{12m+3,12m+5,12m+7,\ldots,16m-1\}$. Now $z$ belongs to $[12m+4,
16m+3]$, so let's compare the colouring of $[12m+1,16m]$ to that of $[12m+4,16m+3]$:
$[12m+1,16m]$ has colouring as noted above, while $[12m+4,16m+3]$ has colouring $0~11001100
\cdots11~0$. Hence, in order for $\chi(y) = \chi(z)$, $y$ must belong to the set $\{12m+1,
12m+2,12m+4,12m+6,\ldots,16m\}$, a contradiction.\end{proof}
\begin{thrm}\label{t5} Let $s,t$ be positive integers such that $s>t>1$ and $t$ does
not divide $s$. If $\floor{s/t}$ is even or $\floor{2s/t}$ is even, where $\floor{\cdot}$
is the floor function, then $f(s,t)=4(s+t)+1$. If $\floor{s/t}$ and $\floor{2s/t}$ are
both odd, then $f(s,t) = 4(s+t)+1$ provided $s$,$t$ satisfy the additional condition
$s/t\notin(1.5,2)$.\end{thrm}
\begin{proof} Let $s,t$ satisfy the hypotheses of the theorem. By Theorems \ref{t1} and
\ref{t2}, it suffices to show that $f(s,t)\geq 4(s+t)+1$ under the additional assumption
that $\gcd(s,t) = 1$, hence throughout the proof we assume $\gcd(s,t) = 1$.
Let $a = \floor{s/t}$ and $b = \floor{2s/t}$. Then $s=at+r$, where $0 t$, and $2(s + t) = 2(at + r) + 2t = (b - 1)t + 2r + 2t = (b + 2)t + (2r-t)$.
Hence we can colour $[1,4(s+t)]$ as follows. Let
\[ C = QRQR\cdots QRQJ~RQRQ\cdots RQRJ', \]
where $Q = 11\cdots1$ and $R = 00\cdots0$ each have length $t$, $J = 00\cdots0$ and
$J' = 11\cdots1$ each have length $2r-t$, and where each of $Q$ and $R$ appears $b+2$
times.
Suppose $x,y,z$ is any $(s,t)$-progression in $[1,4(s+t)]$ with $y-x = ds$, $z-y=dt$.
We will show that $\{x,y,z\}$ is not monochromatic. Clearly $d\leq3$, since $d(s+t)
z-x\leq 4(s+t)-1$.
If $d=2$, then $z-x=2(s+t)$, so $C(z)\neq C(x)$. (This is because the colouring on the
second half of $[1,4(s+t)]$ is the reversal of the colouring on the first half.)
If $d=3$, then, since $z=y+3t$ and $C(i) \neq C(i+t)$ for all $i>2(s+t)$, if $C(y)
= C(z)$ we must have $y\leq 2(s+t)$; but then $x = y - 3s \leq 2t - s$. However,
the conditions $s>t$, $s = at + r$, $02t$, hence
$x<0$, a contradiction.
Now assume that $d=1$ and $C(y)=C(z)$. Since $z=y+t$, $y$ must occur in the block $J$,
so $C(y) = 0$. Since $J$ has length $2r-tt$.
We define the colouring $E$ on $[1,4(s+t)]$ as follows. Let us use the notation
$\sim0 = 1$ and $\sim1 = 0$. Then we define, in turn,
\begin{enumerate}
\item[(1)] $E(i) = 1$, $1\leq i\leq r$,
\item[(2)] $E(i) = \sim E(i-r)1$, $r*1$. For example, Theorem
\ref{t5} shows that $f(4m,3) = 4(4m + 3) + 1$ whenever 3 does not divide $m$. By
examining the cases not covered by Theorem \ref{t5}, one sees that these are exactly
the cases $f(t + r,t)$ where $0*