$\newcommand{\R}{\mathbb{R}}\DeclareMathOperator{\E}{\mathbf{E}}\DeclareMathOperator{\deg}{deg}\newcommand{\N}{\mathbb{N}}$

Assignment 2

Question 1

Write your name and student number on the top of the assignment

Question 2

In Lecture 6 we proved that any subset of $\{1,\ldots,2n\}$ of size at least $n+1$ contains a divisible pair; a pair distinct values $x$ and $y$ such that $x/y$ is an integer.

Using the same approach, prove that any subset of $S\subseteq \{1,\ldots,3n\}$ of size at least $2n+1$ contains a pair of distinct values $x$ and $y$ such that $x/y$ is a power of $3$; i.e., $x/y=3^k$ for some positive integer $k$.

Question 3

Suppose that we want to place disks of radius $1$ so that

their centers are all contained in a single disk of radius $r$; and
no pair of disks overlap.

Answer the following questions

(Use something similar to the Pigeonhole Principle to) prove that it is impossible to place more than $(r+1)^2$ disks in this way. (Hint: a disk of radius $x$ has area $\pi x^2$.)
Explain, in words, why it is impossible to place more than $(r+1)^2-1$ disks this way.

Question 4

This question involves a (fairly simple) recurrence equation. You probably want to watch the beginning of Lecture 7 before attempting it.

We have two parallel shelves that can each hold $n+1$ beer bottles. Each beer bottle is red, green, or blue and we have infinitely many bottles of each colour. Someone has already glued a red bottle to the leftmost location on the top shelf and a green bottle to the leftmost location on the bottom shelf, so we still have to place $n$ bottles on each shelf. We want to do this so that:

If two bottles are adjacent on one of the shelves then they should have different colours. (For example, we should never have a red bottle immediately to the right of another red bottle).
If one bottle is placed directly above another bottle then these two bottles should have different colours.

Let $F_n$ denote the number of ways there are to place $2n$ additional bottles so that they satisfy our requirements.

What is the value of $F_0$?
Give a recurrence equation for $F_n$, when $n\ge 1$.
Prove, by induction on $n$, that $F_n=3^n$.

Question 5

This is the same setup as in Question 4, but now the requirements are different. Let $t_0,\ldots,t_n$ be the bottles placed on the top shelf and let $b_0,\ldots,b_n$ be the bottles placed on the bottom shelf. In both cases, these are listed in left-to-right order and the bottles $t_0$ and $b_0$ are already glued to the shelf ($t_0$ is red and $b_0$ is green). Now we only require that,

for each $i\in\{0,\ldots,n-1\}$, the bottles in $\{t_i,t_{i+1},b_i,b_{i+1}\}$ should include at least one red, at least one green, and at least one blue bottle.

Let $G_n$ be the number of ways there are to place $2n$ bottles so that they satisfy our requirements.

What are the values of $G_0$ and $G_1$?
Give a recurrence equation for $G_n$, when $n\ge 2$.
Prove, by induction on $n$, that $G_n=\tfrac{1}{4}\left((2-\sqrt{6})^{n+1} + (2+\sqrt{6})^{n+1} \right)$.

Hint: Once you think you've figured out the recurrence for Part 1, you can use Wolfram Alpha to solve it and see if it gives the solution you're expecting.

Hint: For Part 2, you must still prove by induction that the solution to your recurrence is indeed $\tfrac{1}{4}\left((2-\sqrt{6})^{n+1} + (2+\sqrt{6})^{n+1} \right)$. Don't just say Wolfram Alpha told you so. Try to follow the steps in the proof that the $n$th Fibonnaci number is $(\varphi^n - \psi^n)/\sqrt{5}$. Notice that $\varphi$ and $\psi$ are special because they're the solutions to a certain quadratic equation.

Question 6

The sequence $s_0,s_1,s_2,\ldots$ of bitstrings is defined recursively as follows:

$s_0=1$, i.e., the bitstring of length $1$ consisting of one $1$.
For $n\ge 1$, $s_n$ is obtained from $s_{n-1}$ by replacing each $1$ by $100$ and by replacing each $0$ by $1$.

For example, $s_0=1$, $s_1=100$, $s_2=10011$, $s_3=10011100100$, and so on.

For each $n\ge 0$, let $L_n$ denote be the length of $s_n$ and let $O_n$ be the number of $1$'s in $s_n$.

Determine $L_0$, $L_1$, $O_0$, and $O_1$.
Prove that, for $n\ge 2$, $O_n = L_{n-1}$.
Prove that, for $n\ge 2$, $L_n = L_{n-1} + 2O_{n-1}$
Write a recurrence for $L_n$ that does not involve $O_n$ and use Wolfram Alpha to solve it. (You don't need to prove that Wolfram Alpha solved it correctly, just write the recurrence and the solution Wolfram Alpha gave you for it)
Find a closed-form expression for $O_n$.

Question 7

Consider the following two recursive algorithms, each of which takes as input an integer $n\ge 1$ that is a power of two:

    Foo(n):
        if n = 1 then return 1
        x = Foo(n/2)
        return 1+x

    Bar(n):
        if n = 1 then return 1
        x = Bar(n/2)
        return n+x

Determine the output of Foo as a function of $n$
Determine the output of Bar as a function of $n$