\documentstyle[12pt,twoside,macpsfig,amssymb]{article}
\input{macros-course}

	\addtolength{\topmargin}{-.35in}
	\setlength{\textheight}{8.5in}

\begin{document}

\pset{4}{September 27, 1994}{In tutorial, October 3 and 4}

{\bf Reading:\ } Chapter 0 from [MR].

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem We write $x\equiv y \pmod{10}$, read ``$x$ is congruent to
$y$ modulo 10,'' if we have $(x\bmod 10) = (y\bmod 10)$, or 
equivalently, $10\divides (x-y)$.
Show that for any $n\in\naturals$, the relation $R_n=\{ (a,b)
\in\integers\times\integers : a^n \equiv b^n \pmod{10}\}$ is an
equivalence relation.

What are the equivalence classes of $R_0$, of
$R_1$, of $R_2$, of $R_3$?  State and prove a general theorem about
the equivalence classes of $R_n$ for each $n\in\naturals$.
%	Show that 
%	$R=\{ (a,b) \in\integers\times\integers :a^2 \bmod 10 = b^2 \bmod 10\}$
%	is an equivalence relation.  What are the equivalence classes?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
Verify or falsify the following proof that if a binary relation
$R$ is symmetric and transitive, then it is also reflexive and, hence, an
equivalence relation.  
\begin{quotation}
We have $aRb \Rightarrow bRa$ by symmetry, and
thus, by transitivity, it follows that $aRa$, so $R$ is reflexive.
\end{quotation}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
Suppose that $R$ is a reflexive and transitive 
%	(but not necessarily antisymmetric) 
relation on a set~$X$.  
\begin{problemparts}

\problempart Show that $\sim$, defined by $x\sim y$ if $x R y$ and $y
R x$, is an equivalence relation on $X$.

\problempart Show that the family of equivalence classes is partially
ordered by the relation $\preceq$ defined by $[x]\preceq [y]$ if $x R y$.

\problempart Identify the equivalence classes if 
$X=\integers$ and $R$ is the divisibility relation.
%	for the relation of divisibility on~$\integers$.
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Determine whether each of the following functions is
an injection, a surjection, a bijection, or none of the these.
%	If the function is not a bijection, indicate subsets
%	of the domain and range so that the function is a bijection between
%	these subsets.

\begin{problemparts}

\problempart
$f: \reals\rightarrow\reals$ where  $f(x)= 3x$.
\problempart
$f: \nats\to\nats$ where $f(x)= x^2$.
\problempart
$f: \reals\to\{x\in\reals \mid x\geq 0\}$ where $f(x)= x^2$.
%	($\reals^+$ denotes the set of positive real numbers.)
\problempart
$f: \reals\to\reals$ where $f(x)= x^3$.
%	$f:\integers\rightarrow\integers$ such that
%	\[ f:a \mapsto \floor{{a\over3}} \]
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
A \defi{permutation matrix} is a square matrix with entries in $\{0,1\}$
such that each column and each row has exactly one~1.
Show that the adjacency matrix of a relation $R$ is a permutation matrix
if and only if $R$ is a bijection.
\remove{
  Let $A$ be the set of all $n\times n$ permutation matrices;
  let $[n]=\{1,\ldots,n\}$ and 
  $B=\{p:[n]\to [n] \mid p \mbox{ is a bijection}\}$.
  There is a correspondence between $A$ and $B$ that respects composition;
  that is, there is a bijection $f:A\to B$ such that 
  if $A_1 A_2 = A_3$ then $f(A_1)\circ f(A_2) = f(A_3)$.
  Note that there are different notions of ``composition'' for the two sets:
  two matrices are composed by matrix multiplication; 
  two functions are composed by functional composition:
  $(f\circ g)(x) = f(g(x))$.
  Find the correspondence $f$ and prove that it is a bijection 
  and that it respects composition.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\problem
The directed graph 
$G = \left(\rule{0pt}{12pt}
\left\{ \rule{0pt}{10pt} 1,2,3,4,5\right\}, 
\left\{ \rule{0pt}{10pt} (1,1), (1,2), (1,3), (3,2), 
	(3,3), (2,4) \right\}\right)$
is depicted below.
%
\begin{figure}[htb]
\setlength{\unitlength}{.6in}	%{.6in}
%
\begin{picture}(5,0)(-8,1.1)	%(-8,2.3)	
%
\put(0,0){\circle*{.1}}
\put(0,-.3){1}
\put(1,0){\circle*{.1}}
\put(1,-.3){2}
\put(2,0){\circle*{.1}}
\put(2,-.3){4}
\put(1,1){\circle*{.1}}
\put(1.2,.8){3}

\thicklines
\put(0,0){\vector(1,1){1}}
\put(0,0){\vector(1,0){1}}
\put(1,0){\vector(1,0){1}}
\put(1,1){\vector(0,-1){1}}
\put(-.2,0){\circle{.4}}
\put(-.01,.06){\vector(1,-1){.02}}
\put(1,1.2){\circle{.4}}
\put(1.06,1.02){\vector(-1,-1){.02}}

\end{picture}
\end{figure}
%
\begin{problemparts}
\problempart 
What is the adjacency matrix for $G$?
\problempart 
What is the square of $G$?
\problempart 
What is the transitive closure of $G$?
\problempart 
By cubing the adjacency matrix of $G$, compute
the number of paths of length exactly 3 between each pair of vertices in $G$.
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Define the function $u(n):\nats\to\nats$ recursively by the rules
\[
u(0)=9, \hspace*{.5in}
u(n+1) = \left\{ \begin{array}{ll} 
		u(n)/2 & \mbox{ if $u(n)$ is even;} \\
		3u(n) + 1 & \mbox{ if $u(n)$ is odd.}
		\end{array}
	\right.
\]
Compute a few values of $u(n)$.  Is $u(n)$ an injection?  A
surjection?  Justify your answers.

\noindent
{\bf Extra extra credit, and possibly a PhD:}
For $m\in\nats$, define $u_m(n)$ as $u(n)$ except $u_m(0) = m$.
Is it true that 
%	$\forall m \exists n :  u_m(n)=1$? \\
for every $m$ there is an $n$ such that $u_m(n)=1$?  (Try $u_{27}(n)$.)\\
This famous open problem is called {\em Ulam's $(3n+1)$-Problem}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem	%% friendly graphs from [CLR], Problem 5-2 on p. 97.
Reword each of the following statements as a theorem about undirected
graphs.  Assume that friendship is symmetric but
not reflexive.  For extra credit, prove each theorem.
\begin{problemparts}
%	\problempart 
%	In any group of $n\geq 2$ people, there are two people
%	with the same number of friends in the group.
\problempart In any group of $n\geq 2$ people, there are two people with
the same number of friends in the group.
\problempart \label{ramseyfriends}
Every group of six people contains either three mutual
friends or three mutual strangers.  
\problempart 
Any group of people can be partitioned into two subgroups
such that at least half the friends of each person belong to the
subgroup of which that person is {\em not\/} a member.
\problempart
If everyone in a group is the friend of at least half the
people in the group, then the group can be seated around a table in
such a way that everyone is seated between two friends.
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\remove{
  \problem 
  A \defi{Hamiltonian cycle} is a cycle that visits each node exactly once.
  Show that any graph with degree at least $n/2$ (that is, each of the $n$ 
  nodes has degree at least $n/2$) has a Hamiltonian cycle.
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\remove{
  \problem 
  Prove that in any set of $101$ distinct integers chosen from
  $\set{1,2,\ldots,200}$, there exist two such that one is an integer
  multiple of the other.  Produce a set of $100$ distinct integers in
  $\set{1,2,\ldots,200}$ such that no number in this set divides
  another.
}

\remove{
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \problem 
  A {\defi clique} is a graph with edges between all pairs of vertices.
  An {\defi independent set} is a graph with no edges.
  %	Generalize problem \ref{ramseyfriends}(b) by 
  Prove that for
  any pair of nonnegative integers $(k,\ell)$, there exists an $n$ 
  such that every graph on $n$ nodes has (as an induced subgraph) 
  either a clique on $k$ nodes or an independent set on $\ell$ nodes.
  (\hint Do this by induction:  prove it's true for $(k,\ell)$ by assuming
  it's true for $(k-1,\ell)$ and $(k,\ell-1)$.)
  %%	Ramsey Theorem:
  %%  	A good written problem would be to prove Ramsey's general theorem
  %% 	that for any (k,l), there is some n s.t. any graph on n nodes has
  %%	either a k-clique or an l-ind.set.
  %%	Do this by induction--assume true for (k-1,l) and (k,l-1).

}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%	DONE BY CHARLES IN LECTURE 6, 9/27/94.
\remove{
  \problem 
  Let $G=(V,E)$ be an $n$-vertex dag (directed acyclic graph).  First
  show that there exists a vertex with out-degree~0.  Now use this
  to show that each vertex $v\in V$ can be assigned a distinct number
  $r(v)$ from the set $\set{1,2,\ldots,n}$ such that if $(u,v)\in E$,
  then $r(u)<r(v)$.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
Prove that the edges of any connected, undirected graph with 
an even number of edges can be oriented---that is, assigned a 
direction---so that every vertex has even out-degree.
(\hint  What happens to the out-degrees of vertices when you reverse
the orientation of each edge along an undirected path in the graph?)
%     Take any orientation and ``fix'' any pair of nodes with odd out-degrees.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\remove{
  \problem 
  A graph that contains no cycles but has fewer than $n-1$ edges (on $n$ nodes)
is sometimes called a \defi{forest} because it contains several disjoint trees.
  Show that any forest with $m$ edges is comprised of exactly $n-m$ trees---%
  that is, the graph can be partitioned into $n-m$ sets such that 
  for any nodes $u$ and $v$, if $u$ and $v$ are in the same set
  then there is a path from $u$ to~$v$.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\remove{
  \problem Let $G=(V,E)$ be an undirected graph, and let $r:V\to\reals$
  be a function associating a real number with each vertex.  Suppose $r$
  satisfies the property that for each $v\in V$, the value $r(v)$ is the
  average of the values of $v$'s neighbors.  Prove that if the graph is
  connected, then $r(u)=r(v)$ for all $u,v\in V$.

  Again, make sure your proof does not suffer from ``build-up error''.
  An easy way to check whether it does is to see if your proof still 
  holds if $r(v)$ is assumed to be the \defn{median}\footnote{%
   The \defi{median} of an ordered list of $n$ elements is the element at the 
   ``halfway point'' of the list.  
   In other words, if $n$ is odd, it is the element
   $(n+1)/2$ up the list; and if $n$ is even, it is either the element $n/2$ up 
   the list or the element $n/2 +1$ up the list.
   For example, the median of $\langle 1, 1, 2, 2, 2, 3\rangle$ is $2$ and
   the median of $\langle 1, 1, 2, 3, 3, 4\rangle$ is either $2$ or~$3$.},
  rather than the average, of its neighbors' values.
  Give a counterexample for the formulation with median.
}

\end{problems}

\end{document}
