\documentstyle[12pt]{article}
\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6.5in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}

\begin{document}

{\bf Tutorial 7 solutions.}

\date{}

\section{Team Problems}
\begin{enumerate}
\item Let $S$ be the set of numbers $7, 77, 777, \ldots$. Prove that there
is an element of $S$ that is divisible by $1997$.


We use the pigeonhole principle.
Let the pigeons be the elements $s \in S$, and 
the holes be the numbers $0 \ldots 1996$.  Let $s$ be placed in 
$s \bmod 1997$.

Since there are more than 1997 elements of $S$, some hole must have 
two numbers, say $s_i$ and $s_j$, with $i$ and $j$ 7's respectively.  
Without loss of generality, assume that $i<j$.

Then, 
$s_j - s_i = 77 \ldots 700\ldots0$ where there are $j-i$ 7's and $i$ 0's.
So, $s_j - s_i = s_{j-i} \cdot 10^i$.  
Since $s_j \bmod 1997 = r = s_i \bmod 1997$, 
$s_j - s_i \bmod 1997 = 0$, so $1997 \mid (s_j - s_i)$.  But 
$gcd(1997,10^i) = 1$, so 1997 must divide $s_{j-i}$.

\item
A boolean function from the naturals to $\{0,1\}$ is map
$f: {\cal N} \rightarrow \{0,1\}$ i.e., it assigns $0$ or $1$ to
each natural number. 
A computer program is a finite 
piece of code (in your favourite programming language). The code for a 
boolean function takes 
as input a natural number and outputs $0$ or $1$. Prove that not 
all boolean functions $f$ are computable (i.e., not every boolean function
can be programmed with a finite piece of code).
 \begin{enumerate}
  \item What is the cardinality of the set of finite programs ? Show that this
is a countable set.
  \item What is the cardinality of the set of boolean functions ? Show that
this is equal to $|2^{\cal N}|$. 
  \item From the above, deduce that there are uncomputable boolean functions.
 \end{enumerate}
\end{enumerate}


\begin{enumerate}
 \item The set of finite programs is a countable set. We can think
of any finite program as a string on a finite sized alphabet (the alphabet
is the set of possible instructions in the program). Let us
order the elements of the alphabet as $a_1,a_2,\ldots,a_k$. Then we order
the set of all strings on this alphabet as follows: first according to 
length (strings of length 1, followed by strings of length 2, .. and so on) 
and then lexicographically among strings of the same length.
Given a program
$P$ define $f(P)$ as the position of $P$ in lexicographic order. 
This is a map from the set of programs to the set of natural numbers.
It is easy to see that the map is an injection. No two programs are
mapped to the same natural number. Also every finite program is mapped
to some finite natural number. This is because the position
in lexicographic order of a program of length $n$ is at most $k^{n+1}$.

\item We will set up a bijection from the set of boolean functions
to the power set of the naturals. A boolean function $f$ maps each 
natural number to $0$ or $1$. Another way to specify
$f$ is to give the subset of the naturals which it maps to $0$. 
So define the mapping $g: Bool \rightarrow 2^{\cal N}$ which 
maps $f \in Bool$ to the subset of natrurals which $f$ maps to 
$0$. Then the map $g$ is an injection because if $f$ and $g$ map
to the same subset, then they agree on all their inputs (they
agree on the $0$ set, so they agree on the $1$ set). Further
given a subset of the naturals we can define the boolean function
which maps that subset to $0$ and every natural number not in the
subset to $1$. Clearly this is a surjection. All in all, we have
a bijection. The cardinality of the set of boolean functions is $|2^{\cal N}|$.

\item Since one set is countable and the other is uncountable, any
one-to-one mapping of the larger set will leave some elements unmapped.
That is some functions will not be computable (by any finite program).
\end{enumerate}

\end{document}