<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt]{article}

\usepackage{fullpage}
\usepackage{amssymb}
\usepackage{fancybox}

\newcommand{\IR}{\mathbb{R}}

\newcommand{\Mystery}{\textsf{\sc Mystery}}

%%%%%%%%%%%%%% Capsule %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\capsule}[2]{\vspace{0.5em}
  \shadowbox{%
    \begin{minipage}{.90\linewidth}%
      \textbf{#1:}~#2%
    \end{minipage}}
  \vspace{0.5em} }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcounter{ques}
\newenvironment{question}{\stepcounter{ques}{\noindent\bf Question \arabic{ques}:}}{\vspace{5mm}}

\begin{document} 

\begin{center} \Large\bf
COMP 2804 --- Assignment 2
\end{center}

\noindent {\bf Due:} Sunday October 11, 11:55 pm.

\vspace{0.5em}

\noindent {\bf Assignment Policy:}
\begin{itemize}
\item Your assignment must be submitted as one single PDF file through
      cuLearn.
\item {\bf Late assignments will not be accepted. I will not reply to
      emails of the type ``my internet connection broke down at
      11:53pm'' or ``my scanner stopped working at 11:54pm'', or
      ``my dog ate my laptop charger''.}
\item You are encouraged to collaborate on assignments, but at the level
      of discussion only. When writing your solutions, you must do so
      in your own words.
\item Past experience has shown conclusively that those who do not put
      adequate effort into the assignments do not learn the material and
      have a probability near 1 of doing poorly on the exams.
\item When writing your solutions, you must follow the guidelines below.
      \begin{itemize}
      \item You must justify your answers.
      \item The answers should be concise, clear and neat.
      \item When presenting proofs, every step should be justified.
      \end{itemize}
\end{itemize}

\vspace{1em} 

\begin{question}
\begin{itemize}
\item Write your name and student number.
\end{itemize}
\end{question}

\begin{question}
Consider a finite set $S$ of points in the two-dimensional plane. 
A point $p$ of $S$ is called a \emph{covidiot}, if $p$ is within two 
meters of some other point of $S$. 

Let $R$ be a rectangle whose horizontal sides have a length of $20$ 
meters and whose vertical sides have a length of $30$ meters. 
Assume that all points of $S$ are contained in $R$ and that $S$ contains 
at least $601$ points. 
\begin{itemize}
\item Use the Pigeonhole Principle to prove that $S$ contains at least 
two covidiots. 
\end{itemize}
\end{question}

\begin{question}
\begin{itemize}
\item Let $\alpha_1,\alpha_2,\ldots,\alpha_7$ be real numbers 
that are all contained in the interval $[-\pi/2,\pi/2]$. 

Use the Pigeonhole Principle to prove that there are two distinct 
indices $i$ and $j$ such that $0 \leq \alpha_i - \alpha_j \leq \pi/6$. 
\item Let $a_1,a_2,\ldots,a_7$ be real numbers such that 
$a_i a_j \neq -1$ for all $i \neq j$. 

Prove that there are two distinct indices $i$ and $j$ such that 
\[ 0 \leq \frac{a_i - a_j}{1 + a_i a_j} \leq \frac{1}{\sqrt{3}} . 
\]

\noindent 
\emph{Hint:} For each $i$, let $p_i$ be the point with coordinates 
$(1,a_i)$, and consider the angle between the $x$-axis and the vector 
from the origin to $p_i$. You learned in high school that 
\[ \tan(\alpha-\beta) = 
   \frac{\tan\alpha - \tan\beta}{1 + \tan\alpha \tan\beta} . 
\] 
\end{itemize}
\end{question}

\begin{question} 
The function $f : \{0,1,2,\ldots\} \rightarrow \IR$ is defined by 
\[ \begin{array}{lcll} 
      f(0) &amp; = &amp; 7 , &amp; \\ 
      f(n) &amp; = &amp; 5 \cdot f(n-1) + 12 n^2 - 30 n + 15 
                      &amp; \mbox{if $n \geq 1$.}  
   \end{array} 
\]
\begin{itemize} 
\item Prove that for every integer $n \geq 0$, 
\[ f(n) = 7 \cdot 5^n - 3 n^2 . 
\] 
\end{itemize} 
\end{question} 

\begin{question}  
Consider the following recursive algorithm, which takes as input an 
integer $n \geq 1$ that is a power of two: 

\capsule{Algorithm $\Mystery(n)$}{
\begin{quote}
\begin{tabbing}
{\bf if} $n=1$ \\
{\bf then} return $1$ \\
{\bf else} \= $x = \Mystery(n/2)$; \\ 
           \&gt; return $n+x$ \\ 
{\bf endif}
\end{tabbing}
\end{quote}
}

\begin{itemize} 
\item Determine the output of algorithm $\Mystery(n)$ as a function 
      of $n$. As always, justify your answer. 
\end{itemize} 
\end{question} 

\begin{question} 
In class, we have seen that for any integer $m \geq 1$, the number of 
$00$-free bitstrings of length $m$ is equal to $f_{m+2}$, which is the 
$(m+2)$-th Fibonacci number.

Let $n \geq 4$ be an integer and consider the set 
\[ B = \{ (x,y) : \mbox{both $x$ and $y$ are $00$-free bitstrings of 
                        length $n-1$} \} . 
\] 

\begin{itemize} 
\item Explain, in a few sentences, why $|B| = f_{n+1}^2$. 

Note that $f_{n+1}^2$ is the square of $f_{n+1}$, i.e., it is to be read 
as $\left( f_{n+1} \right)^2$.
\item Determine the number of elements $(x,y)$ in $B$ for which the 
concatenation $xy$ is $00$-free. 
\item Determine the number of elements $(x,y)$ in $B$ for which the 
concatenation $xy$ is not $00$-free. 
\item Use the previous results to prove that 
      \[ f_{2n} = f_{n+1}^2 - f_{n-1}^2 .
\] 
\end{itemize} 
\end{question} 

\begin{question}  
The sequence $s_0, s_1, s_2, \ldots$ of bitstrings is recursively 
defined as follows: 
\begin{enumerate}
\item $s_0 = 1$, i.e., the bitstring of length one consisting of 
one $1$. 
\item For $n \geq 1$, the bitstring $s_n$ is obtained as follows: 
In the bitstring $s_{n-1}$, replace each $1$ by $10$ and replace each 
$0$ by $1$. 
\end{enumerate} 
The first few strings in this sequence are 
\[ s_0 = 1 ; s_1 = 10 ; s_2 = 101 ; s_3 = 10110 ; 
   s_4 = 10110101 . 
\] 

\begin{itemize} 
\item Prove that for each $n \geq 0$, the bitstring $s_n$ is $00$-free.
\end{itemize} 
For each $n \geq 0$, let $L_n$ be the length of $s_n$ and let $O_n$ 
be the number of $1$'s in $s_n$. 
\begin{itemize} 
\item Determine $L_0$, $L_1$, $O_0$, and $O_1$. 
\item Let $n \geq 2$. Prove that $O_n = L_{n-1}$. 
\item Let $n \geq 2$. Prove that $L_n = L_{n-1} + O_{n-1}$. 
\item Express $O_n$ in terms of numbers that we have seen in class. 
\end{itemize} 
For each $n \geq 0$, let $Z_n$ be the number of $0$'s in $s_n$. 
\begin{itemize} 
\item Express $Z_n$ in terms of numbers that we have seen in class. 
\end{itemize} 
\end{question} 

\begin{question}
Consider a bitstring $b_1 b_2 \ldots b_n$ of length $n$, where $n \geq 2$ 
is an integer. For any integer $i$, the bit $b_i$ is called \emph{lonely},
if $b_i = 1$ and its neighboring bits are $0$. More formally, the bit 
$b_i$ is lonely if 
\begin{enumerate}
\item $i = 1$, $b_1 = 1$, and $b_2 = 0$, or 
\item $i=n$, $b_n = 1$, and $b_{n-1} = 0$, or 
\item $2 \leq i \leq n-1$, $b_i = 1$, and $b_{i-1} = b_{i+1} = 0$. 
\end{enumerate}
For example, in the following bitstring, the three bits in boldface 
are lonely: 
\[ {\bf 1} 0 0 0 1 1 1 0 0 {\bf 1} 0 {\bf 1} 0 0 0 
\] 
A bitstring of length at least two is called \emph{happy} if none of its 
bits is lonely. 

For any integer $n \geq 2$, let $A_n$ denote the number of happy 
bitstrings of length $n$, and let $B_n$ denote the number of happy 
bitstrings of length $n$ that start with $11$. 

\begin{itemize} 
\item Determine $A_2$, $A_3$, $A_4$, and $A_5$. 
\item Let $n \geq 3$ be an integer. Express $A_n$ in terms of $A_{n-1}$ 
      and $B_n$. 
\item Let $n \geq 4$ be an integer. Express $A_{n-1}$ in terms of 
      $A_{n-2}$ and $B_{n-1}$. 
\item Let $n \geq 5$ be an integer. Express $B_n$ in terms of $A_{n-3}$ 
      and $B_{n-1}$. 
\item Let $n \geq 5$ be an integer. Prove that 
      \[ A_n = 2 \cdot A_{n-1} - A_{n-2} + A_{n-3} . 
      \] 
\end{itemize}  
\end{question} 

\end{document} 
</pre></body></html>