\documentstyle[12pt  ,twoside,amsfonts,amstex]{article}
\input{macros-course-tutorials}

\parskip1.5ex
\parindent0pt

\begin{document}

\tutorial{tutorial3}{Problems for Tutorial 3}{September 30, 1996}

\section {Running in the Family}

\noindent Prove that in the last 1000 years you have had an ancestor A and an
ancestor B such that A is decended from B on both sides, i.e. both of
A's parents are descendants of B.\\ 

\section {Uncomputable Functions}

\noindent A computable function from the naturals to the naturals is a finite piece of code (in your
favourite programming language). The code takes as input a natural
number and outputs a natural number. Prove that not all functions $f$
from the naturals to the naturals are computable.\\ 

\section {A Number Theory Application}

\noindent Suppose I have a collection of switches numbered $0$ through
$n$, all initially off.  Someone comes and flips every switch (so they
are all on).  Another person then flips every second switch, starting
with $0,2,\ldots$.  The next person flips every third switch, and so
on until the last person flips only the flips numbered $0$ and $n$.
Which switches are on at the end?  Prove it.



\end{document}
