\documentclass{article}
\usepackage{amsmath}
\usepackage{xcolor}
\usepackage{paralist}
\usepackage{graphicx}
\plparsep 2ex
\usepackage{amsfonts}
\usepackage{url}
\usepackage{listings}
\usepackage{minted}
\usepackage[utf8]{inputenc}
\usepackage[margin=1in]{geometry}
\setlength{\parskip}{1em}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\DeclareMathOperator{\E}{\mathbf{E}}
\newcommand{\N}{\mathbb{N}}
\title{Assignment 1 Solutions}
\author{COMP2804 Winter 2020}
\begin{document}
\maketitle
\newcommand{\Z}{\mathbb{Z}}
\section{ID}
Name: Lenny Learning Combinatorics \\
Student ID: 100000000
\section{Decimal Strings}
A \emph{dec-string} is a sequence of characters from the 10-character alphabet $\lbrace 0,1,2,3,4,5,6,7,8,9\rbrace$. For example, these are dec-strings:
\begin{verbatim}
0
36562342320
49548362729
\end{verbatim}
\begin{compactenum}[Q\thesection.1:]
\item What is the number of dec-strings of length $n$?
Let $U_n$ be the set of dec-strings $d_1,\ldots,d_n$ of length $n$. We can determine $|U_n|$ by the most straightforward application of the Product Rule: For each $i\in\{1,\ldots,n\}$ there are 10 choices for $d_i$, so there are $10^n$ dec-strings of length $n$.
\item What is the number of dec-strings $d_1,\ldots,d_n$ of length $n$ such that $d_1d_2\neq 00$. In other words, what is the number of dec-strings of length $n$ that don't begin with $00$?
Let $S_n$ be the set of dec-strings $d_1,\ldots,d_n$ that don't begin with $d_1d_2=00$.
Any dec-string of length $n<2$ does not begin with $00$, so $|S_0|=1$ and $|S_1|=10$.
For $n=2$, each of the $10^2=100$ dec-strings of length 2 is valid except for $00$, so $|S_2|=99$. (This is an application of the Complement Rule.)
For $n\ge 3$ we can use the Product Rule with a 2-step procedure to generate an element of $S_n$:
\begin{compactenum}[Step 1.]
\item Choose the values of $d_1d_2$. There are 99 ways to do this.
\item Choose $d_3,\ldots,d_n$, a dec-string of length $n-2$. There are $10^{n-2}$ ways to do this.
\end{compactenum}
Therefore $|S_n|=99\cdot 10^{n-2}$.
\item What is the number of dec-strings $d_1,\ldots,d_n$ of length $n$ such that $d_1d_2\neq 00$ \emph{and} $d_2d_3\neq 11$?
Let $T_n$ be the set of dec-strings $d_1,\ldots,d_n$ of length $n$ that don't have $b_1b_2=00$ and don't have $b_2b_3=11$. For $n\in\{0,1,2\}$, this problem is easy, $|T_n|=10^n$ for $n\in\{0,1,2\}$.
For $n\ge 3$ we will use the Complement Rule. We will start with the set $U_n$ of all dec-string of length $n$ and remove those that start with $b_1b_2=00$ and remove those that have $b_2b_3=11$.
First, consider the case $n=3$. Let $A$ be the set of dec-strings $b_1b_2b_3$ of length 3 that begin with $b_1b_2=00$ and let $B$ be the set of length-3 dec-strings that have $d_2d_3=11$. Notice that $A$ and $B$ are disjoint (all elements in $A$ have $b_2=0$ and all elements in $B$ have $b_2=1$), so by the Sum Rule:
\[ |A\cup B| = |A|+|B| \enspace . \]
It's easy to see that $|A|=10$ and $|B|=10$ since each element in $A$ has 10 options for $b_3$ (and $b_1b_2=00$) while each element in $B$ has 10 options for $b_1$ (and $b_2b_3=11$). So
\[ |A\cup B| = |A|+|B| = 10+10 = 20 \enspace . \]
Finally, let $U_3$ be the set of \emph{all} dec-strings of length 3. Then
\[ |T_3| = |U_3\setminus (A\cup B)| = |U|-|A\cup B| = 10^3-20 \enspace = 980 . \]
As in the previous question, for $n>3$ we can generate any element of $T_n$ by a two step procedure by first choosing $b_1b_2b_3$ from $T_3$ and then choosing $d_4,\ldots,d_n$ from $U_{n-3}$. Therefore, for $n\ge 3$,
\[ |T_n| = |T_3|\cdot |U_{n-3}| = 980\cdot 10^{n-3} \enspace . \]
\item What is the number of dec-strings $d_1,\ldots,d_n$ of length $n$ such that $d_1d_2\neq 00$ \emph{and} $d_2d_3\neq 01$?
Let $S_n$ be the set of dec-strings $d_1,\ldots,d_n$ of length $n$ such that $d_1d_2\neq 00$ \emph{and} $d_2d_3\neq 01$? This looks a lot like the previous question, and we will tackle it the same way. The cases $n=\{0,1,2\}$ are boring.
For $n=3$, define $A$ as before, so $|A|=10$. Define $C$ as the set of length-3 dec-strings $b_1b_2b_3$ with $b_2b_3=01$. Again $|C|=10$. The difference now is that $A$ and $C$ are not disjoint: $A\cap C=\{001\}$, so $|A\cap C|=1$. Therefore, by the Principle of Inclusion-Exclusion
\[ |A\cup C|=|A|+|B|-|A\cap C| = 10+10-1= 19 \enspace . \]
Therefore
\[ |S_3|=|U_3\setminus(A\cup C)| = |U_3|-|A\cup C| = 10^3-19=981 \enspace .\]
For $n>3$ we apply the Product Rule with the same 2 step procedure, except now there are $981$ ways to execute Step~1, so $|S_n|=981\cdot10^{n-3}$.
\item What is the number of dec-strings $d_1,\ldots,d_n$ of length $n$ such that $d_1d_2=00$ \emph{or} $d_1d_2d_3=111$?
Let $X_n$ be the set of dec-strings of length $n$ that begin with $00$. For $n\ge 2$, each such string consists of $00$ followed by an element of $U_{n-2}$, so $|X_n|=|U_{n-2}|=10^{n-2}$.
Let $Y_n$ be the set of dec-strings of length $n$ that begin with $111$. For $n\ge 3$, each such string consists of $111$ followed by an element of $U_{n-3}$, so $|Y_n|=|U_{n-3}|=10^{n-3}$.
Now, the question asks about the size of $X_n\cup Y_n$ and $X_n$ and $Y_n$ are disjoint so, by the Sum Rule,
\[ |X_n\cup Y_n| = |X_n|+|Y_n| = 10^{n-2}+10^{n-3} \enspace , \]
for any $n\ge 3$. (For values of $n<3$, the question is vague, so I'm willing to accept any answer.)
\item What is the number of dec-strings $d_1,\ldots,d_n$ of length $n\ge 4$ such that $d_1d_2\neq 00$ \emph{or} $d_3d_4\neq 11$?
Let $P_n$ be the set of dec-strings $d_1,\ldots,d_n$ of length $n$ such that $d_1d_2\neq 00$. We've already studied these in Part~2, and we know that $|P_n|=|S_n|=99\cdot 10^{n-2}$.
Let $Q_n$ be the set of dec-strings $d_1,\ldots,d_n$ of length $n\ge 4$ such that $d_3d_4\neq 11$. Again, we can determine $|Q_n|$ easily using the Product Rule: There are 99 choices for $d_3d_4$ and $10^{n-2}$ choices for $d_1,d_2,d_5,d_6,\ldots,d_n$, so $|Q_n|=99\cdot10^{n-2}$.
The question asks about $|P_n\cup Q_n|$. We can't use the Sum Rule because $P_n$ and $Q_n$ are \emph{not} disjoint: $P_n\cap Q_n$ contains any string that has $d_1d_2\neq 00$ and has $d_3d_4\neq 11$. But it's easy to compute $|P_n\cap Q_n|$ using the Product Rule with the following procedure:
\begin{compactenum}[Step 1.]
\item Choose $b_1b_2$. There are $99$ ways to do this (only $00$ is not allowed).
\item Choose $b_3b_4$. There are $99$ ways to do this (only $11$ is not allowed).
\item Choose $b_5,\ldots,b_n$. There are $10^{n-4}$ ways to do this.
\end{compactenum}
Thererefore $|P_n\cap Q_n|=99^2\cdot 10^{n-4}$
Therefore, by the Principle of Inclusion-Exclusion
\begin{align*}
|P_n\cup Q_n|\ & = |P_n|+|Q_n|+|P_n\cap Q_n| \\
& = 99\cdot 10^{n-2} + 99\cdot 10^{n-2} - 99^{2}\cdot 10^{n-4} \\
& = 198\cdot 10^{n-2} - 9801\cdot 10^{n-4} \\
& = 19800\cdot 10^{n-4} - 9801\cdot 10^{n-4} \\
& = 9999\cdot 10^{n-4} \enspace .
\end{align*}
\item A dec-string $d_1,\ldots,d_n$ is \emph{bad} if $d_i=d_{i+1}$ or $d_{i}+d_{i+1}=9$ for at least one $i\in\lbrace 1,\ldots,n-1\rbrace$ and it is \emph{good} otherwise. What is the number of good dec-strings of length $n$?
Let $G_n$ be the set of good dec-strings of length $n$. We use the Product Rule with an $n$-step procedure.
\begin{compactenum}
\item In Step 1, we choose $d_1$ and there are 10 ways to do this.
\item In Step~$i+1$, for $i\in\{1,\ldots,n-1\}$, we choose $d_{i+1}$ such that $d_{i+1}\neq d_i$ and $d_{i+1}\neq 9-d_i$. Notice that $9-d_i\neq d_i$ since 9 is an odd number.\footnote{If $9-d_i=d_i$ then $9=2d_i$, which is impossible since $9$ is odd and $2d_i$ is even.} Therefore, there are $10-2=8$ ways to perform Step~$i+1$ for each $i\in\{1,\ldots,n-1\}$.
\end{compactenum}
Therefore, by the Product Rule,
\[ |G_n| = 10\cdot 8^{n-1} \enspace , \]
for $n\ge 1$.
\item A dec-string $d_1,\ldots,d_n$ is \emph{2-bad} if, $d_i=d_j$ or $d_i+d_j=9$ for some $i< j \le i+2$ and it is \emph{2-good} otherwise. What is the number of 2-good dec-strings?
Let $H_n$ be the set of 2-good dec-strings of length $n$. We use the Product Rule with an $n$-step procedure:
\begin{compactenum}
\item In Step~1 we choose $d_1$. There are 10 ways to do this.
\item In Step~2 we choose $d_2$ so that $d_2\neq d_1$ and $d_2\neq 9-d_1$. As discussed above, there are 8 ways to do this.
\item In Step~$j$, for $j\ge 3$, we choose $d_j$ so that $d_j\not\in X_2$, where $X_2=\{d_{j-1},9-d_{j-1},d_{j-2},9-d_{j-2}\}$. Notice that $|X_2|=4$. (Do you see why?) Therefore, there are $10-4=6$ ways to perform Step~$j$ for each $j\in\{3,\ldots,n\}$.
\end{compactenum}
Therefore, by the Product Rule,
\[ |H_n|=10\cdot8\cdot 6^{n-2} \enspace , \]
for $n\ge 2$.
For small values of $n$ we have $|H_0|=1$ and $|H_1|=10$.
\item A dec-string $d_1,\ldots,d_n$ is \emph{$k$-bad} if $d_i=d_j$ or $d_i+d_j=9$ for some $i