\documentclass[11pt, twoside]{article}
\usepackage{epsf}

\input{macros-course}

\newcommand{\nand}{|}
\renewcommand{\implies}{\longrightarrow}

\askaboutsolutions

\begin{document}
\psol{7}{October 24, 2000}{2:35pm in lecture, Tuesday, October 31, 2000}

\textbf{Be sure to indicate your TA's name clearly on the solutions
your turn in}.

-----------------------------------------------------------------------------\\

\textbf{Self-study}
Read: Rosen Sections 1.6, 4.1, 4.2, and 4.3\\
Self-study problems (not to be handed in): Section 1.6: 19   Section 4.1: 1, 8, 29   Section 4.2: 4, 14    
%[[[Miniquiz for tut5: 11]]]

-----------------------------------------------------------------------------\\

\textbf{Reading:}
Lecture notes;  Rosen 4.1, 4.2, and 4.3

\paragraph{Policy on collaboration}
If you collaborated with someone on the problem sets, you should mention their names on top of the problem set. If you did not collaborate with anyone, you should explicitly say so. As a reminder, the write-up of your solutions should be entirely your own.
 
\medskip
\begin{problems}


\problem Find closed-form solutions to the following homogenous linear
recurrences.

\begin{problemparts}
\problempart $x_{n} = 5 x_{n-1} - 6 x_{n-2} \quad (x_0 = 0, x_1 = 1)$

\solution{ The characteristic equation is $r^2 - 5 r + 6 = 0$.  The
roots can be found with the quadratic formula:

\begin{eqnarray*}
r_1 & = & 2 \\
r_2 & = & 3
\end{eqnarray*}

This implies a solution of the form

\begin{eqnarray*}
x_n & = & A 2^n + B 3^n.
\end{eqnarray*}

Substituting the initial conditions into this general form gives a
system of linear equations:

\begin{eqnarray*}
0 & = & A + B \\
1 & = & 2 A + 3 B
\end{eqnarray*}

The solution to this system is $A = -1$ and $B = 1$.  Therefore, the
final solution to the recurrence is

\begin{eqnarray*}
x_n & = & 3^n - 2^n.
\end{eqnarray*}
}

\problempart $x_{n} = 5 x_{n-1} - 8 x_{n-2} + 4 x_{n-3} \quad
	(x_0 = 1, x_1 = 2, x_2 = 3)$

\solution{ The characteristic equation is $r^3 - 5 r^2 + 8 r - 4 = 0$.
Solving a cubic equation can be messy process, but in this case the
roots are easy to find:

\begin{eqnarray*}
r_1 & = & 2 \\
r_2 & = & 2 \\
r_3 & = & 1
\end{eqnarray*}

The general form of the solution is therefore

\begin{eqnarray*}
x_n & = & A 2^n + B n 2^n + C.
\end{eqnarray*}

Substituting the initial conditions into this general form gives a
system of linear equations.

\begin{eqnarray*}
1 & = & A + C \\
2 & = & 2 A + 2 B + C \\
3 & = & 4 A + 8 B + C
\end{eqnarray*}

The solution to this linear system is $A = 2$, $B = -\frac{1}{2}$, and
$C = -1$.  The complete solution to the recurrence is therefore

\begin{eqnarray*}
x_n & = & 2^{n+1} - n 2^{n-1} - 1.
\end{eqnarray*}
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Find closed-form solutions to the following inhomogenous
linear recurrences.

\begin{problemparts}

\problempart (Fibonacci Plus) $x_{n} = x_{n-1} + x_{n-2} + 1 \quad
(x_0 = 0, x_1 = 1)$

\solution{ First, we find the general solution to the homogenous
recurrence.  The characteristic equation is $r^2 - r - 1 = 0$.  The
roots of this equation are:

\begin{eqnarray*}
r_1	& = &	\frac{1 + \sqrt{5}}{2} \\
r_2	& = &	\frac{1 - \sqrt{5}}{2}
\end{eqnarray*}

Therefore, the solution to the homogenous recurrence is of the form

\begin{eqnarray*}
x_n	& = &	A \left( \frac{1 + \sqrt{5}}{2} \right)^n +
		B \left( \frac{1 - \sqrt{5}}{2} \right)^n.
\end{eqnarray*}

Next, we need a particular solution to the inhomogenous recurrence.
Since the inhomogenous term is constant, we guess a linear solution.

\begin{eqnarray*}
an + b	& = &	a(n-1) + b + a(n - 2) + b + 1 \\
	& = &	2an - 3a + 2b + 1 \\
0	& = &	an - 3a + b + 1
\end{eqnarray*}

This equation holds if we set $a = 0$ and $b = -1$.  Therefore, the
inhomogeous recurrence has the simple particular solution $x_n = -1$.
The complete solution to the recurrence is the homogenous solution
plus the particular solution:

\begin{eqnarray*}
x_n	& = &	A \left( \frac{1 + \sqrt{5}}{2} \right)^n +
		B \left( \frac{1 - \sqrt{5}}{2} \right)^n - 1
\end{eqnarray*}

All that remains is to find the constants $A$ and $B$.  Substituting
the initial conditions gives a system of linear equations.

\begin{eqnarray*}
0	& = &	A + B - 1 \\
1	& = &	A \left( \frac{1 + \sqrt{5}}{2} \right) +
		B \left( \frac{1 - \sqrt{5}}{2} \right) - 1
\end{eqnarray*}

The solution to this linear system is:

\begin{eqnarray*}
A	& = &	\frac{5 + 3 \sqrt{5}}{10} \\
B	& = &	\frac{5 - 3 \sqrt{5}}{10}
\end{eqnarray*}

Therefore, the complete solution to the recurrence is

\begin{eqnarray*}
x_n	& = &	\left( \frac{5 + 3 \sqrt{5}}{10} \right) \cdot
			 \left( \frac{1 + \sqrt{5}}{2} \right)^n +
		\left( \frac{5 - 3 \sqrt{5}}{10} \right) \cdot
			\left( \frac{1 - \sqrt{5}}{2} \right)^n - 1.
\end{eqnarray*}
}

\problempart $x_{n} = 3x_{n-1} - 2 x_{n-2} + n \quad (x_0 = 0, x_1 = 1)$

\solution{
First, we find the general solution to the homogenous recurrence.  The
characteristic equation is $r^2 - 3r + 2 = 0$.  The roots of this
equation are $r_1 = 1$ and $r_2 = 2$.  Therefore, the general solution
to the homogenous recurrence is

\begin{eqnarray*}
x_n & = & A + B 2^n.
\end{eqnarray*}

Now we must find a particular solution to the recurrence, ignoring the
boundary conditions.  Since the inhomogenous term is linear, we guess
a solution that is quadratic:

\begin{eqnarray*}
an^2+bn+c	& = &	3(a(n-1)^2+b(n-1)+c) - 2(a(n-2)^2+b(n-2)+c) + n \\
		& = &	an^2+2an-5a+bn+b+c+n \\
0		& = &	2an - 5a + b + n
\end{eqnarray*}

This equation is solved by setting $a = -\frac{1}{2}$ and $b =
-\frac{5}{2}$.  Apparently, any value of $c$ gives a valid particular
solution; for simplicity, we choose $c = 0$.  Therefore, the
particular solution is:

\begin{eqnarray*}
x_n	& = &	-\frac{1}{2}n^2 - \frac{5}{2} n
\end{eqnarray*}

The complete solution to the recurrence is the homogenous solution
plus the particular solution:

\begin{eqnarray*}
x_n	& = &	A + B 2^n -\frac{1}{2}n^2 - \frac{5}{2} n
\end{eqnarray*}

Substituting the initial conditions gives a system of linear
equations:

\begin{eqnarray*}
0	& = &	A + B \\
1	& = &	A + 2 B - 3
\end{eqnarray*}

The solution to this linear system is $A = -4$ and $B = 4$.
Therefore, the complete solution to the recurrence is

\begin{eqnarray*}
x_n	& = &	2^{n+2} -\frac{1}{2}n^2 - \frac{5}{2} n - 4.
\end{eqnarray*}
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem The 6.042 staff recently received the following email.

\begin{verbatim}
From: grzzwk@xoros19.gammaquad.plnt
To: 6042-staff@theory.lcs.mit.edu
Subject: Pset 5 issue

Thank you for contributing the MergeSortX19 algorithm to our
``intellectually challenged'' society.  My, my-- we feel mentally
bloated by this sudden infusion of technological wizardry!

As a token of thanks, we launched a Doritofier missile on a straight
line toward Earth.  Suppose that p(t) denotes the distance between
Xoros 19 and the Doritofier after t days of flight.  At the moment of
launch, the Doritofier was here on Xoros 19, and so p(0) = 0.  After a
single day, the Doritofier had already traveled 100 units toward
Earth, so p(1) = 100.  In general, the position of the missle is given
by the following recurrence:

       p(t+1) = 1.99 * p(t) - p(t-1)

Earth happens to be 1010 units from Xoros 19.  Gotta run!  Seeya!

/Grzzwk
\end{verbatim}


Find a closed-form solution to the recurrence for the
distance between Xoros 19 and the Doritofier after $t$ days of flight.

\solution{ Let $c = 1.99$.  The characteristic equation of Grzzwk's
recurrence is then $r^2 - c r +1 = 0$.  The roots of this equation
are:

\begin{eqnarray*}
r_1	& = &	\frac{c + \sqrt{c^2 - 4}}{2} \\
r_2	& = &	\frac{c - \sqrt{c^2 - 4}}{2} \\
\end{eqnarray*}

Therefore, the general solution to the recurrence is:

\begin{eqnarray*}
p(t)	& = &	A \left( \frac{c + \sqrt{c^2 - 4}}{2} \right)^t +
		B \left( \frac{c - \sqrt{c^2 - 4}}{2} \right)^t
\end{eqnarray*}

Subtituting the initial conditions into this general form gives a
system of linear equations.

\begin{eqnarray*}
0	& = &	A + B \\
100	& = &	A \left( \frac{c + \sqrt{c^2 - 4}}{2} \right) +
		B \left( \frac{c - \sqrt{c^2 - 4}}{2} \right)
\end{eqnarray*}

The solution to this linear system is

\begin{eqnarray*}
A	& = &	\frac{100}{\sqrt{c^2 - 4}} \\
B	& = &	- \frac{100}{\sqrt{c^2 - 4}}
\end{eqnarray*}

Therefore, the complete solution to the recurrence is

\begin{eqnarray*}
p(t)	& = &	\frac{100}{\sqrt{c^2 - 4}} \cdot
		\left(	\left( \frac{c + \sqrt{c^2 - 4}}{2} \right)^t -
		\left( \frac{c - \sqrt{c^2 - 4}}{2} \right)^t \right)
\end{eqnarray*}

where $c = 1.99$.  Note that $\sqrt{c^2 - 4}$ is imaginary.
}


%%%%%%%%%%%%%%%
%\problempart The characteristic equation approach gives a solution to
%this recurrence involving complex numbers.  This makes evalutation
%awkward.  Give a closed-form solution that does not involve complex
%numbers.  DeMoivre's Identity may be helpful:
%
%\begin{eqnarray*}
%(\cos \theta + i \sin \theta)^n & = & \cos n \theta + i \sin n \theta
%\end{eqnarray*}
%
%\solution{
%We start with the solution obtained previously.
%
%\begin{eqnarray*}
%p(t)	& = &	\frac{100}{\sqrt{c^2 - 4}} \cdot
%		\left(	\left( \frac{c + \sqrt{c^2 - 4}}{2} \right)^t -
%		\left( \frac{c - \sqrt{c^2 - 4}}{2} \right)^t \right)
%\end{eqnarray*}
%
%Note that
%
%\begin{eqnarray*}
%\frac{c + \sqrt{c^2 - 4}}{2}
%	& = &	\frac{c}{2} + i \cdot 
%			\sqrt{1 - \left(\frac{c}{2}\right)^2} \\
%	& = &	\cos \theta + i \sin \theta
%\end{eqnarray*}
%
%where $\theta = \arccos \frac{c}{2}$.  With this substitution, we can
%eliminate complex numbers from the solution.
%
%\begin{eqnarray*}
%p(t)	& = &	\frac{100}{\sqrt{c^2 - 4}} \cdot \left(
%		\left(\cos \theta + i \sin \theta \right)^t -
%		\left(\cos \theta - i \sin \theta \right)^t
%		\right) \\
%	& = &	\frac{100}{\sqrt{c^2 - 4}} \cdot \left(
%		\left(\cos t \theta + i \sin t \theta \right) -
%		\left(\cos t \theta - i \sin t \theta \right)
%		\right) \\
%	& = &	\frac{100}{\sqrt{c^2 - 4}} \cdot
%		\left( 2 i \sin t \theta \right) \\
%	& = &	\frac{100}{\sqrt{1 - \left(\frac{c}{2}\right)^2}} \cdot
%		\left( \sin t \theta \right) \\
%	& = &	\frac{100 \sin t \theta}{\sin \theta}
%\end{eqnarray*}
%
%The final solution is
%
%\begin{eqnarray*}
%p(t)	& = &	\frac{100 \sin t \theta}{\sin \theta}
%\end{eqnarray*}
%
%where $\theta = \arccos(\frac{1.99}{2})$.
%}
%
%\problempart Does the Doritofier missle hit earth?
%
%\solution{
%
%The solution indicates that the path of the Doritofier is a sine wave
%with amplitude
%
%\begin{eqnarray*}
%\frac{100}{\sin \theta}
%	& = &	\frac{100}{\sin \arccos\left(\frac{c}{2}\right)} \\
%	& = &	\frac{100}{\sqrt{1 - \left(\frac{c}{2}\right)^2}} \\
%	& = &	\frac{100}{\sqrt{1 - \left(\frac{1.99}{2}\right)^2}} \\
%	& = &	1001.253\ldots
%\end{eqnarray*}
%
%Since Earth is 1010 units from Xoros 19, we're safe.
%
%\bigskip
%
%On the other hand, since the path of the missle is a sine wave, it
%{\em will} be returning to Xorox 19 presently...}
%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  


\problem For each of the functions below, determine
whether the function is injective, whether it is surjective, and
whether it is bijective.  No proofs are required.

\begin{problemparts}
\problempart The function $f : \mathbb{R} \mapsto \mathbb{R}$ defined by
$f(x)=e^x$

\solution{ The function is injective because $e^x = e^y$ if and only
if $x = y$.  The function is not surjective, because $e^x$ never takes
on non-positive values.  The function is not bijective, because it is
not surjective.  }

\problempart The function $f : \mathbb{R} \mapsto \mathbb{R}^+$
defined by $f(x)=e^x$.  (Here $\mathbb{R}^+$ denotes the set of
positive real numbers.)

\solution{The function is injective as before, but is now also surjective
because for every $y \in \mathbb{R}^+$, there exists an $x$ (namely $x
= \ln y$) such that $y = e^x$.  Therefore, the function is bijective.}

\problempart The function $f : \mathbb{R} \mapsto \mathbb{R}$ defined
by $(x+1)/(x^2+1)$

\solution{ The function is not injective, because $f(0) = f(1) = 1$.
The function is not surjective, because the function never takes on
large positive or negative values.  The function is not bijective
because it is neither injective nor surjective.}

\problempart The function $f : \mathbb{R} \mapsto \mathbb{R}$ defined
by

\begin{eqnarray*}
f(x) & = & \left\{
\begin{array}{cl}
1/x & \text{for $x \neq 0$} \\
0 & \text{for $x = 0$.}
\end{array}
\right.
\end{eqnarray*}

\solution{ The function is injective, because $f(x) = f(y)$ if and
only if $x = y$.  The function is surjective, because for all $y \in
\mathbb{R}$, there exists an $x$ (namely $x = 1 / y$ or $x = 0$) such
that $f(x) = y$.  Therefore, the function is also bijective.}

\end{problemparts}

  

  \problem \textbf{Multiple linear recurrences} \\
  On a certain far away island, all men are either blond or
  brown-haired. Studies show that each man has exactly four sons. Every blond
  father has exactly three blond sons, while every brown-haired man
  has exactly two brown-haired sons.  As soon as the father has his four sons,
  he moves to Florida to retire, and never returns to the island. 
  
  \begin{problemparts}
    \problempart Let $a_n$ and $b_n$ denote the number of blond and
    brown-haired men, respectively, after $n$ generations. Write a
    system of recurrences for $a_n$ and $b_n$.

    \solution{
      \begin{equation*}
        \begin{split}
          a_n &= 3 a_{n-1} + 2 b_{n-1},\\
          b_n &= a_{n-1} + 2 b_{n-1}.
        \end{split}
      \end{equation*}
      }
    
    \problempart For which values of $c\ne 0$ and $d$ will we have a
    solution of the form $a_n = c^n$, $b_n = d c^n$?
    
    \solution{ Assume $a_n = c^n$ and $b_n = d c^n$ for some $c\ne 0$
      and $d$. Let's substitute this into the system of recurrences.
      We will obtain the equations
      \begin{align*}
        c^n &= 3 c^{n-1} + 2 d c^{n-1},\\
        d c^n &= c^{n-1} + 2 d c^{n-1}.
      \end{align*}
      Dividing out $c^{n-1}$ (which is allowed, since $c\ne 0$), we
      obtain
      \begin{equation}
        \label{eq:cd}
        \begin{split}
          c &= 3 + 2 d,\\
          d c &= 1 + 2 d.
        \end{split}
      \end{equation}
      Multiplying both sides of the first equation by $d$ and
      subtracting the second equation, we obtain
      \begin{equation*}
        0 = 3 d + 2 d^2 - 1 - 2d = 2 d^2 + d - 1.
      \end{equation*}
      Solving the quadratic equation, we obtain $d \in \{-1,
      \frac{1}{2}\}$. Substituting into~\eqref{eq:cd}, we obtain the
      solutions
      \begin{alignat*}{2}
        c &= 1, \quad &d &= -1;\\
        c &= 4, \quad &d &= \frac{1}{2}.
      \end{alignat*}
      }

    
    \problempart Show that there exist values for $c_1$, $c_2$, $d_1$,
    and $d_2$ such that
    \begin{equation*}
      \begin{split}
        a_n &= x c_1^n + y c_2^n,\\
        b_n &= x d_1 c_1^n + y d_2 c_2^n,
      \end{split}
    \end{equation*}
    is a solution for all $x$ and $y$.
    
    \solution{ Let $c_1 = 1$, $d_1 = -1$, $c_2 = 4$, $d_2 =
      \frac{1}{2}$ (i.e., the two pairs of $c$ and $d$ that were
      obtained in part~(a)).  From part~(a) we know that $a_n =
      c_i^n$, $b_n = d_i c_i^n$ is a solution to the recurrences, for
      each $i\in \{1, 2\}$. It is easy to verify that a constant
      multiple of a solution is a solution, and that a sum of two
      solutions is a solution.  }

%     \problempart Let $c_1$, $c_2$, $d_1$, and $d_2$ be the values you
%     obtained in part~(b). Show that every solution to the system of
%     recurrences~\eqref{eq:sys} can be written in the form
%     of~\eqref{eq:sol} for some $x$ and $y$.
%
%     \solution{Show that $x$ and $y$ can be found for any initial
%       conditions. Then use induction to show that two solutions with the
%       same initial conditions are equal everywhere.}
    
  
    \problempart Suppose that the first generation consisted of ten blond
    and twenty brown-haired men on the island. How many of each
    group will there be after the $n$th generation?
    
    \solution{We have $a_1 = 10$, $b_1 = 20$. Let's find $x$ and $y$
    such that a solution in the form of part~(d) would satisfy these
    initial conditions. We have
    \begin{align*}
      10 &= x \cdot 1^1 + y \cdot 4^1,\\
      20 &= x \cdot (-1) \cdot 1^1 + y \cdot \frac{1}{2} \cdot 4^1,
    \end{align*}
    which can be rewritten as
    \begin{align*}
      10 &= x + 4 y,\\
      20 &= -x + 2 y.
    \end{align*}
    This gives $x = -10$ and $y = 5$.

    Thus the solution is
    \begin{align*}
      a_n &= -10 + 5 \cdot 4^n,\\
      b_n &= 10 + \frac{5}{2} \cdot 4^n.
    \end{align*}
    }
  \end{problemparts}

\problem 
\begin{problemparts}
\problempart
Theory Pig has often complained that the
name ``Pigeonhole Principle'' is verbose and awkward.  He proposes the
more concise term ``Pig Principle'' for the same idea.  Recently, he
devised a problem involving this idea in order to promote his
terminology.\\
\\
Suppose that $m$ pigs are lined up, and each pig is given
one or more tasty treats.  Prove that there is always a set of pigs
that are consecutive in the lineup and that all together receive a
number of treats that is a multiple of $m$.

For example, suppose that there are $m = 5$ pigs, and that they
receive 1, 6, 2, 7, and 9 treats respectively.  Then the claim holds
in this case, because the second, third, and fourth pigs received $6 +
2 + 7 = 15$ treats altogether, and 15 is a multiple of 5.

\solution{ Let $P_i$ be the total number of treats given out to the
first $i$ pigs.  Thus in the above example, $P_1 = 1$, $P_2 = 7$,
$P_3=9$, etc. There are two cases.  In the first case, suppose that 
at least one of $P_1, P_2, \ldots, P_m$ is congruent to 0 modulo $m$.
In particular, suppose that $P_j$ is congruent to 0 modulo $m$.  This
implies that the number of treats received by the first $j$ pigs is a
multiple of $m$, and so the claim holds.  In the second case, suppose
that none of $P_1, P_2, \ldots, P_m$ is congruent to 0 modulo $m$.
Then each of the $m$ terms $P_1, P_2, \ldots, P_m$ is congruent to one
of the $m-1$ values $1, 2, \ldots, m-1$ modulo $m$.  By the Pig
Principle, there are at least two terms $P_j$ and $P_k$ that are
congruent to the same value modulo $m$.  Thus pigs $j+1, j+2, \ldots,
k$ received a total of $P_k - P_j$ treats, which is a multiple of $m$.
}

%%%%%%%%%%%%%
%\problempart Suppose that during each day of an 13-week term, a
%certain theoretically-inclined pig receives at least one affectionate
%pat.  However, suppose that this pig never receives more than 12 pats
%in any one of the 13 weeks, on account of his being underappreciated
%by the TA staff.  Prove that there exists a sequence of consecutive
%days during which the pig receives exactly 25 affectionate pats.
%
%\solution{ Let $P_i$ be the total number of pats that the pig receives
%in the first $i$ days.  Since he gets least one pat every day, the
%sequence $P_1, P_2, \ldots, P_{91}$ is strictly increasing.  Since he
%gets at most 12 pats per week, the final term, $P_{91}$, is at most $13
%\cdot 12 = 156$.  Now the sequence $P_1 + 25, P_2 + 25, \ldots, P_{91}
%+ 25$ is also strictly increasing, and the largest term, $P_{91} + 25$,
%is at most $156 + 25 = 181$.  Therefore, the 182 values $P_1, \ldots,
%P_{91}$ and $P_1 + 25, \ldots, P_{91} + 25$ all lie between 1 and 181.
%By the Pig Principle, at least two of these values must be the same.
%Since no two of the numbers $P_1, \ldots, P_{91}$ are equal, and no
%two of the numbers $P_1 + 25, \ldots, P_{91} + 25$ are equal, there
%must be an $i$ and a $j$ such that $P_i = P_j + 25$.  This implies
%that on days $j+1, j+2, \ldots i$, the pig receives exactly 25
%affectionate pats.
%
%\bigskip
%
%Fat chance.
%}
%
%\end{problemparts}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\problempart  A lattice point is a point in a coordinate plane for which
both coordinates are integers.  Prove that no matter what five lattice
points might be chosen in the plane at least one of the segments that joins
two of the chosen points must pass through some lattice point in the plane.


\solution{To show that one of the line segments connecting five lattice points
must pass through some lattice point in the coordinate plane, note that there four
"parity" classes for the coordinates of a lattice point: odd, odd; odd, even;
even, odd; and even, even. On the pigeonhole principle some two of the five lattice
points, say $(x_1, y_1)$ and $(x_2, y_2)$ must belong to the same class. This implies
that $x_1 + x_2$ and $y_1 + y_2$ are both even numbers, making the midpoint
of the segment joining the points, namely $[(x_1 + x_2)/2, (y_1 + y_2)/2]$, 
a lattice point.

}
\end{problemparts}
\end{problems}
\end{document}






























