\problemdata      
        {functions-relations-4} % latex-friendly label for the prob.
        {equivalence classes} % The topic(s) of the problem content.
        {similar to Rosen 6.5.10} % Source (if known)
        {S02 cp3W, F99 tutorial} % Usage (list ones you are aware of).
        {Radhika Nagpal, S02} % Last revision info (author, date).

\begin{problem}
Define $(a,b) R (c,d)$ iff $a+d = b+c$.

\begin{problemparts}
\problempart  
Prove that $R$ is an equivalence relation on
$\integers\cross\integers$.  

\solution{

\begin{itemize}
\item 
{\em Reflexivity}. 
$(a,b) R (a,b)$ since $a + b = b + a$.
\item 
{\em Symmetry}.
$(a,b) R (c,d) \implies (c,d) R (a,b)$ 
since $a + d = b + c \implies c + b = d + a$.
\item 
{\em Transitivity}. 
Assume $(a,b) R (c,d)$, i.e., $ a + d = b + c$.
And, $(c,d) R (e,f)$, i.e., $c + f = d + e$. Adding we get 
$a + d + c + f = b + c + d + e$ or $a + f = b + e$, i.e., 
$(a,b) R (e,f)$.  Hence 
$(a,b)R(c,d)\wedge(c,d)R(e,f)\implies(a,b)R(e,f)$. 
\end{itemize}

Since $R$ is reflexive, symmetric, and transitive, it is an 
equivalence relation.
}

\problempart  
Partition the set $\set{0,1,2} \cross \set{0,1,2}$ into the
distinct equivalence classes under $R$.

\solution{
The trick is to rewrite $(a,b) R (c,d)$ iff $a+d = b+c$ as
$(a,b) R (c,d)$ iff $a-b = c -d$.  This shows that with any
equivalence class ${\cal C}$ we can associate a 
{\em difference~$d\in\integers$} such that 
$(a,b) \in {\cal C} \iff a - b = d$.  This gives us an easy way 
to list the equivalence classes of $\set{0,1,2} \cross \set{0,1,2}$.
\begin{itemize}
\item $d = -2$: $\{(0,2)\}$.
\item $d = -1$: $\{(0,1),(1,2)\}$.
\item $d = 0$:  $\{(0,0),(1,1),(2,2)\}$.
\item $d = 1$:  $\{(1,0),(2,1)\}$.
\item $d = 2$:  $\{(2,0)\}$.
\end{itemize}
}

\problempart 
How many distinct equivalence classes under $R$ are there on the
set $\set{0,1,\dots, n} \cross \set{0,1,\dots, n}$? Explain why.

\solution{
$2n+1$, since the difference can be any value in $\{-n,\ldots, n\}$.
}

\end{problemparts}
\end{problem}
