\documentclass[11pt, twoside]{article}
\input{macros-course}
\usepackage{graphicx}
\renewcommand{\implies}{\longrightarrow}
\newcommand{\ignore}[1]{}
\askaboutsolutions
\begin{document}
\handout{practice-ps2}{Practice Problem Set 2}{April 10, 2001}

\medskip
\begin{problems} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \problem In Miniquiz 8, you were asked to find in how many ways a
  set of five letters can be selected from the English alphabet. Of
  course, most of you assumed that the letters are all distinct and
  gave the answer $\binom{26}{5}=65,780$. How many different
  (multi)sets would there be if repetition was allowed?

\solution{
\medskip
\textbf{Solution:}
\medskip
       
From the lecture notes, the number of $r$-combinations with repetition of an $n$-element set
is

\[
\binom{n + r - 1}{r}.
\]
So the answer is
\[
\binom{26 + 5 - 1}{5}=\binom{30}{5}=142,506.
\]  
}            
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset7 problem2 spring98
%binomial coefficients and product rule
\problem Prove that

\[ \sum_{a=0}^n \sum_{b=0}^{n-a} \frac {n!}{a!b!(n-a-b)!} = 3^n \ . \]

\medskip

\hint find a formula for $(x+y+z)^n$ and then set $x=y=z=1$.

\solution{
\medskip
\textbf{Solution:}
\medskip
       
We can write $(x+y+z)^n$ as follows:

\begin {equation} 
 \label{eq1} \begin {array}{lcr}
 (x+y+z)^n & =& (x+y+z) (x+y+z) \cdots
(x+y+z)\\ &=& \displaystyle
\sum_{  \begin{array}{c} \scriptstyle a,b,c\\ 
\scriptstyle a\geq 0, b \geq 0, c\geq 0\\
\scriptstyle a + b+ c = n \end {array}} C_{a,b,c} x^a y^b z^c 
\end {array} \ . \end {equation}
where $C_{a,b,c}$ is the number of ways to partition a set
of $a+b+c$  elements into three 
subsets of size, respectively, $a$, $b$, and $c$. 

We compute $C_{a,b,c}$ using the product rule. A
partition can be obtained by first choosing $a$ elements
out of $a+b+c$ ones, and then choosing $b$ elements out of the remaining
$b+c$ ones. The number of ways to make such choices is

\begin {equation} \label{eq2}
 C_{a,b,c} = {a +b +c \choose a} \cdot {b+c \choose b} = 
\frac{ (a+b+c)!}{a!(b+c)!} \cdot \frac{(b+c)!}{b!c!} = \frac {(a+b+c)!}{a!
b!c!}\ .  \end {equation}
% We could have found the same expression using the division rule.
Substituting Equation~(\ref{eq2}) into Equation~(\ref{eq1}) we
have

\begin{eqnarray*} 
(x+y+z)^n & = &  \sum_{ \begin{array}{c} \scriptstyle a,b,c\\ 
\scriptstyle a\geq 0, 
b \geq 0, c\geq 0\\
\scriptstyle a + b+ c = n \end {array}} \frac {n!}{a!b!c!}
x^a y^b z^{c} \\
& = & \sum_{a=0}^n \sum_{b=0}^{n-a} \frac {n!}{a!b!(n-a-b)!}
x^a y^b z^{n-a-b} \ .
\end {eqnarray*}

If we set  $x=y=z=1$
we derive

\[ 3^n = (1+1+1)^n = \sum_{a=0}^n \sum_{b=0}^{n-a} \frac {n!}{a!b!(n-a-b)!}
1^a 1^b 1^{n-a-b}\ . \]
}
              
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem %(20 points)
% Binomial coefficient calculations, playing with the definition.
% Also Fibonacci numbers, induction

\ppart %(5 points)
Recall the double induction example from Lecture 4, which involved a
function $f \colon \nat \times \nat \to \nat$ defined by:  $f(n,0) =
1$ for all $n$, $f(0,k) = 1$ for all $k$, and $f(n+1,k+1) = f(n+1,k) +
f(n,k+1)$ for all $n$ and $k$.
We proved by double induction that $f(n,k) = \frac{(n+k)!}{n!k!}$
for all $n$ and $k$. \\
Recall the definition of binomial coefficients: $\binom{a}{b}=\frac{a!}{(a-b)!b!}$. Express $f(n,k)$ in terms of binomial coefficients.

\solution{

\medskip
\textbf{Solution:}
\medskip

Since \[\frac{(n+k)!}{n!k!}=\frac{(n+k)!}{(n+k-k)!k!}=\binom{n+k}{k}\] we see that 
$f(n,k)=\binom{n+k}{k}$
}


% A:  \binom{n+k}{n}

\ppart %(5 points)
What identity about binomial coefficients arises from what we proved
in Lecture 4? Hint: how can you express $\binom{n+1}{k+1}$ in terms of smaller binomial coefficients? 

\solution{
\medskip
\textbf{Solution:}
\medskip

By direct substitution from part (a) we get:
\[\binom{n+k+2}{k+1} = \binom{n+k+1}{k+1} + \binom{n+k+1}{k}\]
Note that this is just the Pascal's identity in disguise---with the
substitutions $n := n + k + 2$ and $r := k + 1$, it becomes:
\[\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}\]
}

\ignore{
\ppart %(15 points)
% From Velleman p. 278, problem 5(e)
Recall the definition of Fibonacci numbers:
\[
F_{0}=0;
F_{1}=1;
\text{for every }n\geq 2, F_{n}=F_{n-2}+F_{n-1}\]
Prove that for all $n\geq 0$
\[
F_{2n} = \sum_{i=0}^{n-1}{\binom{2n-i-1}{i}}\qquad  \text{AND}\qquad
F_{2n+1}=\sum_{i=0}^{n}{\binom{2n-i}{i}}
\]

\hint use induction, and the formula you derived above

%Should be a proof using strong induction, either directly from the
%defintions or using some version of the sum identity above.
%Give a hint?
%I found it useful to try small cases, and to look at where the
%corresponding entries were in the array from lecture 3.
\solution{
\medskip
\textbf{Solution:}
\medskip
We can prove this by induction on $n$. Let $P(n)$ be the statement that \[
F_{2n} = \sum_{i=0}^{n-1}{\binom{2n-i-1}{i}}\qquad  \text{AND}\qquad
F_{2n+1}=\sum_{i=0}^{n}{\binom{2n-i}{i}}
\]
\subparagraph{Base Case:}For $n=0$, $\sum_{i=0}^{-1}{\binom{2n-i-1}{i}}=0$ since the summation basically has no terms. Indeed $F_{0}=0$ so the first half of what we need to show holds. $\sum_{i=0}^{0}{\binom{2n-i}{i}}=1$ and $F_{1}=1$ so the second half also holds.
\subparagraph{Induction Step:} Assume $P(n)$. We want to prove $P(n+1)$. We need to show 2 things:
\[
F_{2n+2} = \sum_{i=0}^{n}{\binom{2n-i+1}{i}}\qquad  \text{and}\qquad
F_{2n+3}=\sum_{i=0}^{n+1}{\binom{2n-i+2}{i}}
\]
First, let's see what $\sum_{i=0}^{n}{\binom{2n-i+1}{i}}$ is equal to. The first term of the summation, i.e, when $i=0$ is $1$, therefore, we can write this as \[
1+ \sum_{i=1}^{n}{\binom{2n-i+1}{i}}\]Now, using the identity from part (b), we can write this as
\[
1+ \sum_{i=1}^{n}{\left[ \binom{2n-i}{i}+ \binom{2n-i}{i-1}\right] } 
\] 
which is, of course, equal to 
\[
1+\sum_{i=1}^{n}{\binom{2n-i}{i}}+\sum_{i=1}^{n}{\binom{2n-i}{i-1}}\]
We notice that if we let $i=0$, $\binom{2n-i}{i}=1$, so we can ``absorb'' that 1 into the first summation and write
 \[
\sum_{i=0}^{n}{\binom{2n-i}{i}}+\sum_{i=1}^{n}{\binom{2n-i}{i-1}}\]
 Things are starting to look good since we recognize that first sum to be $F_{2n+1}$. In order to attack the second sum, we make a substitution: let $k=i-1$ (which means, wherever we see $i$, we put $k+1$. So the above becomes \[
\sum_{i=0}^{n}{\binom{2n-i}{i}}+\sum_{k=0}^{n-1}{\binom{2n-k-1}{k}}\]
From our induction hypothesis, this equals $F_{2n+1}+F_{2n}$ so this does indeed equal $F_{2n+2}$. (For those who are confused about what I proved: if you want to prove that $a=b$, you can just prove that $b=a$).
\medskip

Now, let's see what $\sum_{i=0}^{n+1}{\binom{2n-i+2}{i}}$ is equal to. 
For $i=n+1$, $\binom{2n-i+2}{i}=\binom{n+1}{n+1}=1$. For  $i=0$, $\binom{2n-i+2}{i}=1$. Therefore, we can write this thing as
\[
1+1 +\sum_{i=1}^{n}{\binom{2n+-i+2}{i}}
\] 
which, using the same identity again, can be written as
\[
1+1+\sum_{i=1}^{n}{\left[ \binom{2n-i+1}{i}+\binom{2n-i+1}{i-1}\right]}
\]which is equal to
\[
1+1+\sum_{i=1}^{n}{\binom{2n-i+1}{i}}+\sum_{i=1}^{n}{\binom{2n-i+1}{i-1}}
\]Since for $i=0$, $\binom{2n-i+1}{i}=1$ and for $i=n+1$, $\binom{2n-i+1}{i-1}=\binom{n}{n}=1$, we can ``absorb'' one of the $1$'s into the first sum and the other into the second sum and write
\[
\sum_{i=0}^{n}{\binom{2n-i+1}{i}}+\sum_{i=1}^{n+1}{\binom{2n-i+1}{i-1}}
\]and making the substitution $i-1=k$ into the second sum, we get
\[
\sum_{i=0}^{n}{\binom{2n-i+1}{i}}+\sum_{k=0}^{n}{\binom{2n-k}{k}}
\] By what we proved before, the first sum equals $F_{2n+2}$ and by our induction hypothesis, the second sum equals $F_{2n+1}$. Therefore, $\sum_{i=0}^{n+1}{\binom{2n-i+2}{i}}=F_{2n+2}+F_{2n+1}=F_{2n+3}$ as desired.
 


}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset7 problem4 spring98, from M&R, # 4.7.5
\problem

How many ways can 4 balls be placed in 4 urns if 
\begin{problemparts}
\problempart both the balls and the urns are distinguishable;

\solution{
\medskip
\textbf{Solution:}
\medskip
       
$4\cdot 4\cdot 4\cdot 4 =256$.
}

\problempart the balls are distinguishable but the urns are not;

\solution{
\medskip
\textbf{Solution:}
\medskip
       
15.  We can put either all 4 balls in one urn; or 3 in one, 1 in
another; or 2 in one, 2 in another; or 2 in one, 1 in one and 1 in
another; or 1 ball in each urn.  The balls are distinguishable, so
there are $4\choose 3$ ways of putting 3 in one urn.  There are
$4\choose 2$ ways of putting 2 in one and 1 in each of the other two.
There are ${4\choose 2}/2$ ways of putting 2 in one and 2 in another.
Since the urns are indistinguishable, there is only one way to put all
the balls in the same urn and one way to put each ball in a different
urn. So the total number of ways is
\[
1 + {4\choose 3} + \frac{1}{2}{4\choose 2} + {4\choose 2} + 1 = 15.
\]
}

\problempart the urns are distinguishable but the balls are not;

\solution{
\medskip
\textbf{Solution:}
\medskip
       
35.
This is a stars and bars problem with the balls being stars and the 
urns bars.  The answer is
${4+4-1 \choose 4} = {7 \choose 4} = 35$.
}

\problempart neither the balls nor the urns are distinguishable.

\solution{
\medskip
\textbf{Solution:}
\medskip
       
5.
This is the number of ways to partition a multiset $\{1,1,1,1\}$
of 4 indistinguishable objects into 4 (possibly empty) subsets.
We can either put
$\{1,1,1,1\}, \emptyset, \emptyset, \emptyset$ or
$\{1,1,1\}, \{1\}, \emptyset,\emptyset$, or
$\{1,1\}, \{1,1\},\emptyset,\emptyset$, or
$\{1,1\}, \{1\}, \{1\}, \emptyset$, or
$\{1\},\{1\},\{1\},\{1\}$.
The ordering in which we list the subsets doesn't matter because
the urns are indistinguishable.
}

\end{problemparts}

                
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem In this problem, we use generating functions
to compute the number of $m$ bit strings with a multiple of three 1's.
For example, if $m = 4$, then there are five such strings:

\[
\begin{array}{ccccc}
0000 &\quad&    1110    &\quad& 1101 \\
1011 &\quad&    0111        \\
\end{array}
\]

\begin{problemparts}
\problempart Use summation notation and binomial coefficients to
describe the number of $m$-bit strings with a multiple of three 1's.

\solution{
\medskip
\textbf{Solution:}
\medskip
       
\[
\sum_{i=0}^{\left\lfloor\frac{m}{3}\right\rfloor} \binom{m}{3i}
\]
}
\end{problemparts}

The following fact will be useful in evaluating this sum.  Let $z_1 =
1$, $z_2 = -\frac{1}{2} + \frac{\sqrt{3}}{2} i$, and $z_3 =
-\frac{1}{2} - \frac{\sqrt{3}}{2} i$.  The expression
$\frac{1}{3}(z_1^k + z_2^k + z_3^k)$ is then equal to 1 if $k$ is a
multiple of 3 and is equal to 0 otherwise.

\begin{problemparts}
\problempart Left $f(x)$ be a generating function for the series $<
a_0, a_1, a_2, \ldots >$.  Give a closed-form expression for the
sum $\sum_{i=0}^{\infty} a_{3i}$.

\solution{
\medskip
\textbf{Solution:}
\medskip
       
\begin{eqnarray*}
\sum_{i=0}^{\infty} a_{3i}
    & = &   \sum_{k=0}^{\infty} a_k \cdot \frac{z_1^k+z_2^k+z_3^k}{3}\\
    & = &   \frac{1}{3} \cdot \left(
        \sum_{k=0}^{\infty} a_k z_1^k +
        \sum_{k=0}^{\infty} a_k z_2^k +
        \sum_{k=0}^{\infty} a_k z_3^k
        \right) \\
    & = &   \frac{f(z_1) + f(z_2) + f(z_3)}{3}
\end{eqnarray*}
}

\problempart Recall that $f(x) = (1 + x)^m$ is the generating function
for binomial coefficients; that is, for $0 \leq k \leq m$, the
coefficient of $x^k$ is $\binom{m}{k}$, and for $k > m$, the
coefficient of $x^k$ is zero.  Combine this fact and the two preceding
problem parts to obtain a closed-form expression for the number of
$m$-bit strings with a multiple of three 1's.

\solution{
\medskip
\textbf{Solution:}
\medskip
       
\begin{eqnarray*}
\sum_{i=0}^{\left\lfloor\frac{m}{3}\right\rfloor} \binom{m}{3i}
    & = &   \frac{1}{3}((1 + z_1)^m + (1 + z_2)^m + (1 + z_3)^m) \\
    & = &   \frac{1}{3}\left(
        2^m +
        \left( \frac{1}{2} + \frac{\sqrt{3}}{2} i \right)^m +
        \left( \frac{1}{2} - \frac{\sqrt{3}}{2} i \right)^m
        \right)
\end{eqnarray*}
}

\problempart Use DeMoivre's formula, restated below, to eliminate
complex numbers from your solution.

\begin{eqnarray*}
(\cos \theta + i \sin \theta)^n & = & \cos(n \theta) + i \sin(n \theta)
\end{eqnarray*}

\solution{
\medskip
\textbf{Solution:}
\medskip
       
\begin{eqnarray*}
\lefteqn{\frac{1}{3}\left(2^m +
        \left( \frac{1}{2} + \frac{\sqrt{3}}{2} i \right)^m +
        \left( \frac{1}{2} - \frac{\sqrt{3}}{2} i \right)^m
        \right)}
\hspace{1in} \\
    & = &   \frac{1}{3}\left(2^m +
        \left( \cos \frac{\pi}{3} + i \sin \frac{\pi}{3} \right)^m +
        \left( \cos \frac{\pi}{3} - i \sin \frac{\pi}{3} \right)^m
        \right) \\
    & = &   \frac{1}{3}\left(2^m +
        \cos \frac{m \pi}{3} + i \sin \frac{m \pi}{3} +
        \cos \frac{m \pi}{3} - i \sin \frac{m \pi}{3} \right) \\
    & = &   \frac{1}{3}\left(2^m + 2 \cos \frac{m \pi}{3} \right)
\end{eqnarray*}

For example, the number of 4-bit strings with a multiple of three ones
is equal to

\begin{eqnarray*}
\frac{1}{3}\left(2^4 + 2 \cos \frac{4 \pi}{3} \right)
    & = &   \frac{1}{3}\left(16 + 2 \cdot \left(-\frac{1}{2}\right)
        \right) \\
    & = &   5
\end{eqnarray*}
 }

\end{problemparts}
                                     
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem  Prove or disprove the following statements
about sets.  (We use ``collection'' as a synonym for ``set'' to make
some of the statements easier to read.)

\begin{problemparts}

\problempart The product of a finite collection of countable sets is
countable.

\solution{
\medskip
\textbf{Solution:}
\medskip
       
The statement is true.  

\begin{proof}
The proof is by induction.  Let $P(n)$ be the proposition that the
product of $n$ countable sets is countable.  In the base case, $P(1)$
is true because the product of a single countable set is itself.  In
the inductive step, for $n \geq 1$ assume $P(n)$ to prove $P(n+1)$.
The product of $n+1$ countable sets $S_1, S_2, \ldots, S_{n+1}$ can be
written as shown below.

\[
(S_1 \times S_2 \times \ldots \times S_{n}) \quad \times \quad S_{n+1}
\]

The first term is a countable set by induction, and the second term is
a countable set by definition.  The product of two countable sets is
countable, as shown in lecture.  Therefore, the product of $n+1$
countable sets is countable.  This shows that $P(n)$ implies $P(n+1)$,
and the claim is proved by induction.
\end{proof}
}

\problempart The product of a countable collection of finite sets is
countable.

\solution{
\medskip
\textbf{Solution:}
\medskip

The statement is false.

We will construct a bijection between the product of a
countable number of finite sets and the power set of the natural
numbers.  Since the latter is uncountable, the former must be
uncountable as well.

Consider the countable collection of finite sets $S_1 = S_2 = \ldots =
\{ 0, 1 \}$.  The product $S_1 \times S_2 \times \ldots$ consists of
all infinite binary sequences, e.g. $( 0, 1, 1, 0, 1, \ldots)$.  There
is a natural bijection between such infinite binary sequences and the
power set of the natural numbers.  In particular, let the sequence
$(b_0, b_1, \ldots)$ correspond to the set of all natural numbers $i$
such that $b_i = 1$.  This bijection implies that the set of infinite
binary sequences is uncountable.}

\problempart The set of all finite subsets of a countable set is
countable.

\solution{
\medskip
\textbf{Solution:}
\medskip
       
The statement is true.

\begin{proof}
Let $S$ be a countable set.  For $k \geq 0$, let $S_k$ be the set of
$k$-element subsets of $S$.  The set of all finite subsets of $S$ is
then the union of the sets $S_k$ for $k \geq 0$.  We will prove below
that every set $S_k$ is countable.  This will imply that the set of
all finite subsets of $S$ is a union of a countable collection of
countable sets and is therefore countable.

All that remains is to show that $S_k$, the set of $k$-element subsets
of $S$, is countable for all $k \geq 0$.  We prove this by
establishing an injection from $S_k$ to $S^k$, the product of the set
$S$ with itself taken $k$ times.  In particular, the injection maps
the set $\{ s_1, s_2, \ldots s_k \} \in S_k$ to the tuple $(s_1, s_2,
\ldots, s_k) \in S^k$, where the elements in the tuple are ordered in
an arbitrary way.  Since $S^k$ is countable, the injection implies
that $S_k$ is also countable.
\end{proof}
}

\ignore{
\problempart Suppose that the intersection of a countable collection
of sets is finite.  Then there exists a finite subcollection of the
sets with finite intersection.

\solution{
\medskip
\textbf{Solution:}
\medskip
       
The statement is false.

Let $S_k$ be the set of integers divisible by $k$, for $k \geq 1$.
The intersection of this countable family of sets is finite; in fact,
the intersection is $\{ 0 \}$, since zero is the only integer
divisible by every positive integer.  However, there is no finite
subfamily of sets $S_k$ with finite instersection.  In particular, the
intersection of the finite subfamily

\[
S_{a_1} \cap S_{a_2} \cap \ldots \cap S_{a_n}
\]

contains all integers of the form $m \cdot a_1 \cdot a_2 \cdots a_n$
where $m \in \mathbb{Z}$.  }
}

\end{problemparts}
                        
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
% fall97 ps7, Rosen 1.8 / 30
% infinity

Use a diagonalization argument to show that the set of functions from
the positive integers to the set $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ is
uncountable.

\solution{
\medskip
\textbf{Solution:}
\medskip
       
Assume, for the purposes of contradiction, that this set is countable.
Then there is a listing of the function in the set,
 $f_1, f_2,\ldots$.  Now define $f$ such that $f(i) = (f_i(i)+5) \mod 10$.
Then $f$ is not in the list, because $f$ differs from each $f_i$
in the $i$th value.  We have established a contradiction.  We conclude that
the set is uncountable.
}                

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset6 problem6 spring98 countable, uncountable set via diagonalization

\ignore{%
\problem 
Consider the set of binary strings of infinite length (strings of zeroes and
ones).  Prove that the set of such strings with at most $501$ ones in them
is countable. 
(Hint: how might you list these numbers?) 

\solution{
\medskip
\textbf{Solution:}
\medskip
       
Let $A$ be the set of infinite binary strings with at most $501$ ones 
in them.
For any arbitrary $x>0$, only a finite number of elements of $A$
have all of their ones occur before the $x$th digit.
(i.e., only 2 have all ones before the $2$nd digit, specifically
$1000000$\dots and $000000$\dots)  Let $A_x$ be the set of those elements in $A$
such that all of their ones occur before the $x$th digit.
Each $A_x$ is a finite set, and a subset of $A$.
For any element $a \in A$, look at the position of the last one in $a$.
If that one is in position $i$ then $a \in A_{i+1}$.  Therefore, every 
element of $A$ appears in at least one $A_x$.  
To list all of the elements in $A$, first list all of the elements
in $A_1$, then all of the elements in $A_2$, then all of the
elements in $A_3$ etc, removing duplicates.
Since each $A_x$ is finite, the list is a valid list.
Thus a list has been generated for all elements in
$A$ and therefore $A$ is countable.
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset6 problem7 spring98 countable, uncountable set via diagonalization

\problem
Consider the set of binary strings of infinite length (strings of zeroes
and ones).  Define $A_n$ to be the set of binary strings such that, at any
point in the string, at most $1/n$ of the preceding numbers can be $1$.
So $A_1$ is the set of all binary strings of infinite length, since at any
point, at most all of the preceding numbers can be $1$.  $A_2$ is the set
of strings such that at any point, at most half of the preceding terms
can be $1$.  For instance, the first element of every string in $A_2$ must
be 0, and of the first three elements, at most $1$ can be $1$.  In general,
the first $n-1$ elements of $A_n$ must be $0$.  
As a further example, the string $010101000$... $ \in A_2$, but the string
$0101011000$... $\not\in A_2$. 

Prove that $A_{501}$ is uncountable.

\solution{
\medskip
\textbf{Solution:}
\medskip
       
The proof is by diagonalization.  Assume for the purposes of
contradiction that the set is countable.  Then there must be
a way to list the elements in order.  Construct such a list, using
a mapping function such that $f(i)$ represents the $i$th element in
the list.  Now construct a number $a$ as follows.  For each $f(i)$, set
the $501(i)$th element of $a$ to be the opposite of the $501(i)$th element
of $f(i)$.  For all elements of $a$ not set in this manner, set them to $0$. 
Since at any point, there are at least $500$ zeroes for every one, $a$ is 
in $A_{501}$.  Therefore it must appear in this list at $a = f(j)$.  However,
$f(j)$ and $a$ differ on the $501(j)$th element of the string, so
$a \neq f(j)$, and a contradiction is reached.  Therefore $a$ cannot be in
the list and the elements of $A_{501}$ cannot be listed, therefore $A_{501}$ is
uncountable.
}  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
}



\end{problems}

\end{document}                            

