COMP2804: Discrete Structures II
$\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.

  1. 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 $a$ and $b$ such that $a/b$ is a power of $3$; i.e., $a/b=3^k$ for some positive integer $k$.

Answer 1

Let $x_1,\ldots,x_{2n+1}$ be a $(2n+1)$-element subset of $\{1,\ldots,3n\}$. For each $i\in\{1,\ldots,2n+1\}$, repeatedly remove factors of $3$ from $x_i$ to express it as $x_i = y_i3^{t_i}$ where $t_i\ge 0$ is an integer and $y_1\bmod 3\in\{1,2\}$.

Now, the number of integers $y\in\{1,\ldots,3n\}$ such that $y\bmod 3\{1,2\}$ is $2n$. Therefore, by the Pigeonhole Principle, there must exist disting $i,j\in\{1,\ldots,2n+1\}$ such that $y_i=y_j$. Since $x_i\neq x_j$, it must be that $t_i\neq t_j$. Without loss of generality we may assume that $t_i>t_j$. Then \[ \frac{x_i}{x_j} = \frac{y_i\cdot 3^{t_i}}{y_j\cdot 3^{t_j}} = \frac{3^{t_i}}{3^{t_j}} = 3^{t_i-t_j} = 3^k \enspace , \] where $k=t_i-t_j$ is a positive integer, as required.

Question 3

Packing unit disks into a disk of radius $r$

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

Answer the following questions

  1. (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$.)
  2. Explain, in words, why it is impossible to place more than $(r+1)^2-1$ disks this way.

Answer 3.1

Packing unit disks into a disk of radius $r$

Let $D$ be a set of $k$ disks that satisfy the conditions of the question. We need to show that $k\le (r+1)^2$. The area of each disk in $D$ is $\pi$ and, since they are disjoint, the area $A$ of their union is $k\pi$. On the other hand, since all these disks have centers inside a disk of radius $r$, they are all contained in a disk $B$ of radius $r+1$. The disk of radius $r+1$ has area $\pi(r+1)^2$. Therefore, $k\pi \le \pi(r+1)^2$, so $k\le (r+1)^2$.

Answer 3.2

In the previous question we already established that $k\le (r+1)^2$. Since $k$ is an integer, we therefore only need to show that $k < (r+1)^2$. In other words we need only show that $k\neq (r+1)^2$. Suppose for the sake of contradiction that $k=(r+1)^2$. Then $\mathop{area}(\cup D)=\pi(r+1)^2=\mathop{area}(B)$. This means that if we take away all the disks in $D$ from $B$, then there is no area left, i.e., $\mathop{area}(B\setminus (\cup D))=0$. But this certainly can't be the case since, for example, there are small areas near the boundary of $B$ that are not covered by any disk.

Question 4

Placing beer bottles on shelves

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:

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

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

Answer 4.1

$F_0$ ask how many ways we can place $0$ bottles in addition to the two bottles that are already placed. There is only one way to do this (by doing nothing), so $F_0=1$.

Answer 4.2

To place $2n$ bottles, we must first place the first two bottles on each shelf and then place the remaining $n-1$ bottles on each shelf. There are already two bottles placed immediately to the left of the first two bottles we want to place, and these already-placed bottles have different colours. Suppose without loss of generality that they are red (top shelf) and green (bottom shelf). Then the first two bottles we place can have colors (green,red), (green,blue), or (blue, red). Therefore, there are $3$ ways to place the first two bottles.

After we do this, we are left with the problem of placing $n-1$ bottles on each of the two shelves and the two leftmost bottles are preceded by already-placed bottles having two different colours. By definition, there are $F_{n-1}$ ways to do this. This gives us the recurrence equation \[ F_n = \begin{cases} 1 & \text{if $n=0$} \\ 3\cdot F_{n-1} & \text{if $n\ge 1$} \end{cases} \]

Answer 4.3

This is an easy inductive prove. The base case $n=0$ asserts that $F_0=3^0=1$, which is true by definition. For the inductive step, we assume that $F_{n-1}=3^{n-1}$ and now \[ F_n = 3\cdot F_{n-1}=3\cdot 3^{n-1} = 3^n \enspace . \]

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,

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

  1. What are the values of $G_0$ and $G_1$?
  2. Give a recurrence equation for $G_n$, when $n\ge 2$.
  3. 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.

Answer 5.1

As before $G_0$ leaves us with only one option (do nothing), so $G_0=1$. But $G_1$ leaves us with several options; we just have to make sure we include at least one blue bottle. This gives us five options (blue, red), (red,blue), (blue, green), (green,blue) or (blue,blue), so $G_0=5$.

Answer 5.2

Again, we start by placing the leftmost bottles that are not already placed, assuming that immediately to the left of these there are two already-placed bottles of different colours. Without loss of generality, these two already-placed bottles have colours (red,green).

There are two mutually exclusive possibilities:

  1. The first two bottles we place have different colours. These could be (blue, red), (red,blue), (blue, green), or (green,blue). After this we are now left with the problem of placing $n-1$ bottles on each shelf assuming that there are already two different coloured bottles placed immediately to the left of these. By the Product Rule, the number of options in this case is $4G_{n-1}$.
  2. The first two bottles we place have the same colour, (blue,blue). Then we're not quite done, since these two bottles have the same colour. In this case we place two more bottles, which must be (red,green) or (green,red) and then we're left with the problem of placing $n-2$ bottles on each shelf assuming that there are already two different coloured bottles placed immediately to the left of these. By the Product Rule, the number of options in this case is $2G_{n-2}$.

Therefore, by the Sum Rule, we have \[ F_n = \begin{cases} 1 & \text{if $n=0$} \\ 5 & \text{if $n=1$} \\ 4F_{n-1} + 2F_{n-2} & \text{if $n\ge 2$} \end{cases} \]

Answer 5.3

The proof is by induction on $n$. For the two base cases $n=0$ and $n=1$, just evaluate the given expression when $n=0$ and $n=1$ and verify that this gives values $1$ and $5$, respectively.

Now for the inductive step we will assume that $F_x = \tfrac{1}{4}\left((2-\sqrt{6})^{x+1} + (2+\sqrt{6})^{x+1} \right)$ for all $x\in\{0,\ldots,n-1\}$.

First observe that $2\pm\sqrt{6}$ are the two solutions the quadratic equation $x^2=4x+2$. (1)

Then we get \begin{align*} F_n & = 4F_{n-1} + 2F_{n-2} & \text{(from the previous part)} \\ & = \color{red}{(2-\sqrt{6})^n} + \color{blue}{(2+\sqrt{6})^n} + \color{red}{\tfrac{1}{2}(2-\sqrt{6})^{n-1}} + \color{blue}{\tfrac{1}{2}(2+\sqrt{6})^{n-1}} & \text{(from the inductive hypothesis)} \\ & = \color{red}{(2-\sqrt{6})^{n-1}((2-\sqrt{6})+\tfrac{1}{2})} + \color{blue}{(2+\sqrt{6})^n} + \color{blue}{\tfrac{1}{2}(2+\sqrt{6})^{n-1}} & \text{(algebra)} \\ & = \color{red}{\tfrac{1}{4}(2-\sqrt{6})^{n-1}(4(2-\sqrt{6})+2)} + \color{blue}{(2+\sqrt{6})^n} + \color{blue}{\tfrac{1}{2}(2+\sqrt{6})^{n-1}} & \text{(multiply and divide by $4$)} \\ & = \color{red}{\tfrac{1}{4}(2-\sqrt{6})^{n-1}(2-\sqrt{6})^{2}} + \color{blue}{(2+\sqrt{6})^n} + \color{blue}{\tfrac{1}{2}(2+\sqrt{6})^{n-1}} & \text{(by (1))} \\ & = \color{red}{\tfrac{1}{4}(2-\sqrt{6})^{n+1}} + \color{blue}{(2+\sqrt{6})^n} + \color{blue}{\tfrac{1}{2}(2+\sqrt{6})^{n-1}} & \text{(algebra)} \\ & = \color{red}{\tfrac{1}{4}(2-\sqrt{6})^{n+1}} + \color{blue}{\tfrac{1}{4}(2+\sqrt{6})^{n+1}} & \text{(the same way)} \\ & = \tfrac{1}{4}\left(\color{red}{(2-\sqrt{6})^{n+1}} + + \color{blue}{(2+\sqrt{6})^{n+1}}\right) & \text{(algebra).} \\ \end{align*}

Question 6

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

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$.

  1. Determine $L_0$, $L_1$, $O_0$, and $O_1$.
  2. Prove that, for $n\ge 2$, $O_n = L_{n-1}$.
  3. Prove that, for $n\ge 2$, $L_n = L_{n-1} + 2O_{n-1}$
  4. 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)
  5. Find a closed-form expression for $O_n$.

Answer 6.1

By inspection, $L_0=1$, $L_1=3$, $O_0=1$ and $O_1=1$.

Answer 6.2

For each $n$, let $Z_n$ be the number of zeros in $s_n$, which means that $L_n=O_n+Z_n$.

To make $s_n$ we start with $s_{n-1}$ and replace each zero with a one (this makes $Z_{n-1}$ ones in $s_n$) and replace each one with a $100$ (this makes $O_{n-1}$ ones in $s_n$). Therefore, $O_n=Z_{n-1}+O_{n-1}=L_{n-1}$.

Answer 6.3

To make $s_n$ we start with $s_{n-1}$ and replace each zero with a one (this contributes $Z_{n-1}$ to the length of $s_n$) and replace each one with $100$ (this contributes $3O_{n-1}$ to the length of $s_n$). Therefore $L_n=Z_{n-1}+3O_{n-1} = L_{n-1}+2O_{n-1}$.

Answer 6.4

Using the answers to the last two questions we have $L_n=L_{n-1}+2O_{n-1}=L_{n-1}+2L_{n-2}$. Wolfram Alpha says this solves to $L_n=\tfrac{1}{3}((-1)^{n+1}+2^{n+2})$.

Answer 6.5

From Parts 2 and 4, we know that $O_n=L_{n-1}=\tfrac{1}{3}((-1)^{n}+2^{n+1})$.

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
  1. Determine the output of Foo as a function of $n$
  2. Determine the output of Bar as a function of $n$

Answer 7.1

By trying a few values, we guess that $\mathop{Foo}(n)=1+\log_2 n$. Now we verify this by induction. For the base case $n=1=2^0$ and $1+\log_2(1)=1+0=\mathop{Foo}(1)$. For $n\ge 2$, we have \[ \mathop{Foo}(n) = 1+ \color{red}{\mathop{Foo}(n/2)} = 1 + \color{red}{(1+\log_2(n/2))} = 1+ \color{red}{(1+\log_2(n) - 1)} = 1+\color{red}{\log_2(n)} \]

Answer 7.2

By trying a few values we guess that $\mathop{Bar}(n)=2n-1$. For the base case $n=1$ we have $2\times 1 -1 = 2-1=1=\mathop{Bar}(1)$. For $n\ge 2$ we have \[ \mathop{Bar}(n) = n + \color{red}{\mathop{Bar}(n/2)} = n + \color{red}{2(n/2) - 1} = 2n-1 \enspace . \]

image/svg+xml