\documentclass[11pt]{article}

\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{psfig}
\input{../handouts/macros-course}

\begin{document}

\begin{problems}

\problem
% difficulty: easy to hard

For each of the following sets, state whether it is finite, countably
infinite or uncountably infinite.  Prove your claim.

\ppart The set 
$\mathcal{P}(\mathbb{N}) \cap \mathcal{P}(\{ 2^{-i} \ | \ i \in
\mathbb{N} \})$.

\ppart The set of $\Theta(1)$ functions from $\mathbb{N}$ to 
$\mathbb{N}$.

\ppart The set of $O(1 / n)$ functions from $\mathbb{N}$ to
$\mathbb{N}$.

\ppart The set of sequences of rational numbers which converge to zero.

\ppart The set of functions 
$\{ R_f: \mathbb{N} \to \mathbb{N} \ | \  f : \mathbb{N} \to \mathbb{N} \}$,
where 
\begin{eqnarray*}
R_f(n) & = & \left\{
\begin{array}{ll}
f(R_f(n-1)), & \text{for $n \neq 0$} \\
0, & \text{for $n = 0$}
\end{array}
\right.
\end{eqnarray*}


\problem
% difficulty: medium-hard

Let $S = \{ n \in \mathbb{N}^+ \ | \ \{ n\sqrt{2} \} < 0.01 \}$. 
(Note: $\{ x \} = x - \floor{x}$)

\ppart Use the pigeonhole principle to show that $S$ is nonempty.

\ppart Show that $S$ is infinite.


\problem
% difficulty: easy-medium

Let $s = s_1s_2\ldots s_{2n}$ be a string of 0s and 1s.  The
{\em reverse} of $s$ is the string $R(s) = s_{2n}s_{2n-1}\ldots s_1$.

\ppart A string that is equal to its reverse is called a $palindrome$.
How many palindromes of length $2n$ are there?

\ppart How many strings of length $2n$ have exactly $2r$ bits in common 
with their reverse?

\ppart A string $s$ is {\em 1-derful} if all the common bits of $s$ and
$R(s)$ are 1 bits.  How many of the strings from part (b) are 1-derful? 

\ppart What is the total number of 1-derful strings of length $2n$?

\end{problems}

\end{document}








