\Question{Bijective or not?}
Decide whether the following functions are bijections or not. Please prove your claims.
\begin{Parts}
\Part $f(x) = 10^{-5}x$
\begin{enumerate}[(i)]
\item for domain $\mathbb R$ and range $\mathbb R$
\item for domain $\mathbb Z \cup \{\pi\}$ and range $\mathbb R$
\end{enumerate}
\Part $f(x) = p \bmod x$, where $p > 2$ is a prime
\begin{enumerate}[(i)]
\item for domain $\mathbb N \setminus \{0\}$ and range $\{0, \dots, p\}$
\item for domain $\{(p+1)/2, \dots, p\}$ and range $\{0, \dots,
(p-1)/2\}$
\end{enumerate}
\Part $f(x) = \{x\}$, where the domain is $D = \{0,\dots, n\}$ and the range
is $\mathcal P(D)$, the powerset of $D$ (that is, the set of all subsets of
$D$).
\Part Consider the number $X = 1234567890$, and obtain $X'$ by shuffling the
order of the digits of $X$. Is $f(i) = (\text{i} + 1)^{\text{st}}$ \textit{digit
of} $X'$ a bijection from $\{0,\dots, 9\}$ to itself?
\end{Parts}
\Question{Counting Tools}
Are the following sets countable or uncountable? Please prove your claims.
\begin{Parts}
\Part $A \times B$, where $A$ and $B$ are both countable.
\Part $\bigcup_{i\in A} B_i$, where $A, B_i$ are all countable.
\Part The set of all functions $f$ from $\N$ to $\N$ such that $f$ is
non-decreasing. That is, $f(x) \leq f(y)$ whenever $x \leq y$.
\Part The set of all functions $f$ from $\N$ to $\N$ such that $f$ is
non-increasing. That is, $f(x) \geq f(y)$ whenever $x \leq y$.
% \Part The set of all injective functions from $\N$ to $\N$.
% \Part The set of all surjective functions from $\N$ to $\N$.
\Part The set of all bijective functions from $\N$ to $\N$.
\end{Parts}
\Question{Impossible Programs}
Show whether the following programs can exist or not.
\begin{Parts}
\Part A program $P$ that takes in any program $F$, input $x$ and output $y$ and returns
true if $F(x)$ outputs $y$ and false otherwise.
%\Part A program $P$ that takes in any program $F$, input $x$ and line number
%$L$, and returns true if line $L$ is ever executed when $F$ is run on $x$, and
%false otherwise.
\Part A program $P$ that takes in two programs $F$ and $G$ and returns true if $F$ and $G$
halt on the same inputs, and false otherwise.
\end{Parts}
\Question{Undecided?}
Let us think of a computer as a machine which can be in any of $n$ states
$\{s_1, \dots, s_n\}$. The state of a $10$ bit computer might for instance be
specified by a bit string of length $10$, making for a total of $2^{10}$ states
that this computer could be in at any given point in time. An algorithm
$\mathcal A$ then is a list of $k$ instructions $(i_0, i_2, \dots, i_{k-1})$, where each
$i_l$ is a function of a state $c$ that returns another state $u$ and a number $j$.
Executing $\mathcal A(x)$ means computing
\[ (c_1,j_1) = i_0(x), \hspace{10mm} (c_2,j_2) = i_{j_1}(c_1), \hspace{10mm} (c_3, j_3) =
i_{j_2}(c_2), \hspace{10mm} \dots \]
until $j_{\ell} \geq k$ for some $\ell$, at which point the algorithm halts and returns
$c_{\ell-1}$.
\begin{Parts}
\Part How many iterations can an algorithm of $k$ instructions perform on an $n$-state
machine (at most) without repeating any computation?
\Part Show that if the algorithm is still running after $2n^2k^2$
iterations, it will loop forever.
\Part Give an algorithm that decides whether an algorithm $\mathcal A$ halts
on input $x$ or not. Does your contruction contradict the undecidability of
the halting problem?
\end{Parts}
\Question{Clothing Argument}
\begin{Parts}
\Part There are four categories of clothings (shoes, trousers, shirts,
hats) and we have ten distinct items in each category. How many distinct
outfits are there if we wear one item of each category?
\Part How many outfits are there if we wanted to wear exactly two categories?
\Part How many ways do we have of hanging four of our ten hats in a row on
the wall? (Order matters.)
\Part We can pack four hats for travels. How many different possibilities for packing
four hats are there? Can you express this number in terms of your answer
to part (c)?
\Part If we have exactly $3$ red hats, $3$ green hats and $4$ turquoise
hats, and hats of the same colour are indistinguishable, how many distinct
sets of three hats can we pack?
\end {Parts}