\documentclass{amsart}
\usepackage{amssymb,amsfonts,amsmath}
\begin{document}
\title{
               Partition of Integers
}
\maketitle



\textbf{Sophie}  Let $a$ and $b$ be positive integers.  Is it
possible to partition the set of all integers into three disjoint
subsets in such a way that, for every integer $x$, each component
of $(x-a,x,x+b)$ exclusively belongs to one of the three
partitions?

\textbf{Gena}  Speaking of partition of integers into three sets,
all integers can be classified into three types, $3m$, $3m+1$,
$3m+2$.  This is well known, isn't it?  In this classification,
that is the  partition into the sets $\{3m\}=\{\cdots, -6, -3, 0,
3, 6, 9, \cdots \}$, $\{3m+1\}=\{\cdots , -5, -2, 1, 4, \cdots 
\}$, $\{3m+2\}=\{\cdots , -4, -1, 2, 5, \cdots \}$, $x$ and $y$
are in the same set, if and only if $x-y = 3n$ for some $n$.  In
our present  problem, $x-(x-a) = a$, $(x+b)-(x-a)= a+b$, and
$(x+b)-x= b$.  Therefore, if $a \in \{3m+1\}$ and $b \in
\{3m+1\}$, or $a \in \{3m+2\}$ and $b \in \{3m+2\}$, then the
partition into $\{3m\}$, $\{3m+1\}$, and $\{3m+2\}$ satisfies the
desired condition of this problem.  In other cases, this
partition does not satisfy the condition.  Our problem is,
therefore, whether there exist other partitions that satisfy the
condition.
    
\textbf{Luis}  Let me start with an easy case where $a = b$.  If
$a= 1$ or $2$ then Gena has already showed  a desired partition
exists. I try to construct a desired partition into $A$, $B$, and
$C$.  If $a =3$, we have
$$
\begin{array}{cccccccccccccccc}  
 \cdots &  -18&  -15&  -12&  -9&  -6&  -3&  0&  3&  6& 
9&  12&  15& 18& 21& \cdots  \\
 \cdots &  B&    C&    A&   B&  C&  A& B&  C&  A&  B& 
C&  A&  B&   C& \cdots 
\end{array}
$$
This sequence covers all the integers in $\{3m\}$.  For
$\{3m+1\}$, and $\{3m+2\}$, we can assign $A$, $B$, and $C$ in
the same way.  For example,
$$
\begin{array}{cccccccccccccccc}
  \cdots &  -17&  -14&  -11&  -8&  -5&  -2&   1&  4&  7& 
10& 13&  16& 19&  22& \cdots \\ 
 \cdots&   B&  C& A& B& C& A& B& C& A& B& C& A& B& 
C& \cdots \\
\cdots & -16&  -13&  -12&  -7& -4& -1& 2&  5& 8& 11&
14&  17& 20& 23& \cdots \\  
 \cdots& B&  C&  A& B& C& A& B& C& A& B& C&  A&  B& 
 C& \cdots
\end{array}
$$
This method is applicable to every case of $a = b$. 

\textbf{Gena}  Now, for $a \ne b$, let me try $a = 1$ and $b =
2$.
Let $A$, $B$, and $C$ be the partitions of the set of all
integers,  Let  $-1 \in A$, $0 \in B$, and  $2 \in C$ for
$(-1,0,2)$.  I
shift $(-1,0,2)$ to $(0,1,3)$ like Luis did.  In this case
$1 \in C$, $3 \in A$ or $1 \in A$, $3 \in C$.  I can not decide
which is correct.  Let me see.  To get more information, let me
shift $(-1,0,2)$ to $(-2,-1,1)$.  Then $1 \in B$ or $C$.  Yes.
I've got it.
$1$ must belong to $C$.  Now I shift $(0,1,3)$ to $(1,2,4)$. 
Then we have already $1 \in C$ and $2 \in C$, but this is a
contradiction to the given condition.  For $a = 1$ and $b =2$, it
is impossible to construct a desired partition.  This is our
first case where there does not exist a desired partition. 


\textbf{Sophie}  We assume $b > a$ without loss of generality,
because our problem is symmetric with respect to $0$.  Let  $-a
\in A$, $0 \in B$, and $b \in C$.  From $(-a, 0, b)$, I consider
$(-a, b-a, b)$ in place of shifting, because this results in an
overlap of two numbers.  It is a reflection with respect to the
middle of the interval $[-a, b]$.  Then $b-a$ and $-a$ cannot
belong to the same subset, and $b-a$ and $b$ cannot belong to the
same subset.  This is clear from $(-a-a,-a,b-a)$ and $(-a+b,b,
b+b)$ respectively. 
Therefore, $b-a \in B$.  Further, considering $(b-a-a, b-a,
b-a+b)$ we obtain the following diagram.
$$
\begin{array}{ccccc}
                -a&       0&   &       b& \\
                  A&        B&  &       C&\\
                   &   b-a-a&      b-a  &   &       b-a+b\\ 
                   &      &        B&    &               
\end{array}
$$

The second row is a shift of the first row.  Therefore, $b-a-a  
\in A$ and $b-a+b \in C$ or $b-a-a \in C$ and $b-a+b \in A$.  In
either case, 
$2(b-a) \in B$.  Therefore, $(b-a)m \in B$ for any non-negative
$m$. 
Similarly, starting from $(-b, 0, a)$, $(b-a)m \in B$ for any
negative $m$.  Therefore,
$$
     (b-a)m \in B \quad \mbox{for every}\; m.
\eqno (1)
$$
On the other hand, considering $(0,b,b+a)$, $(b,b+a,b+a+b)$, ...,
successivly, we obtain 
$$
\begin{array}{cccccccc}
\cdots& -a&    0 &    b&     b+a&    b+a+b& b+a+b+a&  
  b+a+b+a+b \cdots \\ 
\cdots A &   B &   C &   A  &   B &    C &   A& \cdots
\end{array}
\eqno (2)
$$
Therefore,
$$
      -a+3(a+b)n \in A \quad \mbox{and} \quad (b+a)+3(a+b)n
\in A
\eqno (3)
$$
 for any integer n, and
$$
     -b+3(a+b)n \in C, \quad \mbox{and} \quad 2(b+a)+3(a+b)n
\in A
\eqno (4)
$$
for any integer n.
Therefore, in order for some number in (1) to coincide with a
number in (3),
$$
            (b-a)m = -a +3(a+b)n \quad \mbox{or} \quad (b-a)m
= (b+a)+3(a+b)n
\eqno (5)
$$
In order for some number in (1) to coincide with a number in (4),
$$
      (b-a)m = -b+3(a+b)n or (b-a)m = 2(b+a)+3(a+b)n
\eqno (6)
$$
Are you familiar with these equations.

\textbf{Luis}  I have read about the equation
 $$
         ax+by = c.
\eqno  (7)
$$
But I have forgot the theorem.

\textbf{Gena}  The necessary and sufficient condition for the
equation (7) to have a solution in integers is that the greatest
common divisor of $a$ and $b$ divides $c$.   I learned it from
the book by Oystein Ore.   I will fetch the book.  Here it is.
Number theory and its history.  you can find the proof in 
Chapter 7.

\textbf{Luis}.  Yes I remember it now.  Then let's check the
second equation (5) at first, because it looks easier to handle
than others.
$$     
               (b-a)m - 3(a+b)n = a+b
$$
The common divisor $k$ of $b-a$ and $a+b$ obviously divides
$a+b$. Therefore, let
$$
          b-a = kd,  a+b =ke,
$$
and $d$ and $e$ be relatively prime.  Then we have
$$
                             dm - 3en = e.
$$
To find a desired partition in our present problem, we must find
the condition for the equation to have no solution.  The
necessary and sufficient condition is $d \in \{3m\}$, because $d$
and $e$ are relatively prime.  Therefore we have obtained $b-a
\in \{3m\}$ for a necessary condition.  In the beginning, Gena
described the two cases where $a \in \{3m+1\}$, $b \in \{3m+1\}$
and $a \in \{3m+2\}$, $b \in \{3m+2\}$.  Therefore we are left
with the other case $a \in \{3m\}$, $b \in \{3m\}$ with an
additional condition $d \in \{3m\}$. 

\textbf{Gena}  If $a = 3$ and $b = 6$, then $b-a = 3$ and
$a+b=9$, so that $k = 3$ and $d = 1$. which is not the case.  If
$a = 3$ and $b = 9$,
then $b-a = 6$ and $a+b=12$, so that $k = 6$ and $d=1$, which is
not either.  If $a =3$ and $b=12$, then $b-a=9$ and $a+b=15$, so
that $k=3$ and $d=3$.  Here it is. we have one such case.  This
is worth our consideration.  Let's check the other equations of
(5) and (6).
[They check the equations.]

\textbf{Sophie}  Well, none of the equations has a solution. 
What will you do next?

\textbf{Gena}  Let's try to construct.  From (1) and (2),
$$
\begin{array}{cccccccccccccccccccccccccc}
\cdots & -3& 0& 3&  6& 9& 12& 15& 18& 21& 24& 27& 30& 33& 36& 39&
42& 45& 48& 51&  54&  57&  60&  63&  66& \cdots \\
\cdots& A& B& & & B& C& A& B& & & B& C&&  B& & 
A&   B& & & B& C& A& B& & \cdots
\end{array}
$$
I can fill all these numbers of \{3m\} with $A$, $B$, or $C$ like
this.
$$
\begin{array}{cccccccccccccccccccccccc}
-3& 0& 3& 6& 9& 12& 15& 18& 21& 24& 27& 30& 33&  36& 39&
42& 45&  48& 51& 54& 57& 60& 63& 66& \\
A& B& C& A& B& C& A& B& C& A& B& C& A& B& C& A& B& C& A& B& C& A&
B& C&
\end{array}
$$
Further,
$$
\begin{array}{cccccccccccccccccccccccc}
-2& 1& 4& 7& 10& 13& 16& 19& 22& 25& 28& 31& 34& 37& 40& 
43& 46& 49& 52& 55& 58& 61& 64& 67& \\
A& B& C& A& B& C& A& B& C& A& B& C& A& B& C& A& B& C& A&
B& C& A& B& C& \\
-1& 2& 5&  8& 11& 14& 17& 20& 23& 26& 29& 32& 35& 38& 41& 44& 
47& 50& 53& 56& 59& 62& 65& 68& \\
A&   B&   C&   A&  B&   C&   A&   B&   C&   A&   B&   C&  
A&  B&   C&   A&   B&  C&   A&   B&   C&   A&  B&   C&
\end{array}
$$
This partition is the same as the one Luis created for $a=b=3$,
and it works.        

\textbf{Sophie}  Wait a second!  We are so stupid that we have
not seen that a desired partition is possible for $a = kg$ and
$b= kh$, if and only if a desired partition is possible for $a =
g$ and $b = h$.  Therefore, we don't have to newly consider the
case $a \in \{3m\}$ and $b \in \{3m\}$.  In conclusion, if $a$
and $b$ are relatively prime, then the partition to $\{3m\}$,
$\{3m+1\}$ and $\{3m+2\}$ is the only possiblility. 


\end{document}