COMP2804: Discrete Structures II
$\newcommand{\R}{\mathbb{R}}\DeclareMathOperator{\E}{\mathbf{E}}\DeclareMathOperator{\deg}{deg}\newcommand{\N}{\mathbb{N}}$

Assignment 2

$\newcommand{\IN}{\mathbb{N}}$

Question 1

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

Question 2

A degree in computer science has $8$ elective topics, and students must complete $2$ or $3$ of them in order to graduate. If 1000 students graduate, show that there is a group of at least $12$ students that all completed the same electives.

Question 3

Consider the following recursive function: \[ f(n) = \begin{cases} 8 & \text{if $n=0$} \\ 2\cdot f(n-1)-5n+3 & \text{if $n\ge 1$} \end{cases} \]

Prove that the closed form is $f(n) = 2^n +5n + 7$.

Question 4

The functions $f:\IN \rightarrow \IN$ and $g:\IN^2 \rightarrow \IN$ are recursively defined as follows, where $n$ and $m$ are each non-negative integers. \[ f(n) = \begin{cases} 1 & \text{if $n=0$} \\ g(n, f(n-1)) & \text{if $n\ge 1$} \end{cases} \]

\[ g(m, n) = \begin{cases} 0 & \text{if $m=0$ and $n\ge 1$} \\ g(m-1,n) + 2n & \text{if $m\ge 1$ and $n\ge 1$} \end{cases} \]

  1. Express $g(m,n)$ as a function of $m$ and $n$.
  2. Prove by induction that your closed form expression for $g(m,n)$ is correct.
  3. Express the recurrence for $f(n)$ in terms of $f(n-1)$ and without any $g(...)$ terms.
  4. Express $f(n)$ in terms of $n$.
  5. Prove by induction that your closed form expression for $f(n)$ is correct.

Question 5

$\DeclareMathOperator{\Algo}{AssignmentAlgo}$

Your assignment is due tomorrow so you decide to stream some shows on your laptop. To make sure you finish finish your assignment, you run the following algorithm.

AssignmentAlgo(n):
  if n=1:
    Complete one question
    return
  else:
    Watch n episodes of a show
    AssignmentAlgo(n/4)
    AssignmentAlgo(n/4)

You should assume that $n$ is a power of $4$.

  1. Determine the number of questions that you complete as a function of $n$.
    Hint: You can change the base of a logarithm with the following formula (here we change base $a$ to base $c$ ): \[ \log_ab =\frac{\log_cb}{\log_ca} \]
  2. Determine the number of episodes that you watch as a function of $n$. You may wish to use $$\sum_{j=0}^{k-1} ar^j = a\left(\frac{1-r^{k}}{1-r}\right),$$ where $0<r<1$ and $a$ is a real number (this formula gives the closed form of a geometric series; we'll cover it later in the course, but you can use it now).

Question 6

Let $n\geq 1$ be an integer and consider a $1\times n$ board $B_n$ consisting of $n$ cells, each one having side length one. The top part of the figure below shows $B_9$.

Tilings

We have an unlimited supply of bricks which are of the following types (see the bottom part of the figure above):

  1. There are red ($R$) and green ($G$) bricks which are $1\times 1$ cells.
  2. There are white ($W$), yellow ($Y$), and blue ($B$) bricks which are $1\times 2$ cells.

A tiling of a board $B_n$ is a placement of bricks on the board such that:

  1. the bricks exactly cover $B_n$ and
  2. no two bricks overlap.

In a tiling any colour can be used more than once and some colours might not be used at all. The figure below shows one possible tiling of $B_9$.

Tilings

Let $T_n$ be the number of different tilings of the board $B_n$.

  1. Determine $T_1$ and $T_2$.
  2. Express $T_n$ recursively for $n\geq 3$.
  3. Prove that for any integer $n\geq 1$, \[ T_n = \frac{1}{4}\left( 3^{n+1} + (-1)^n\right). \]
  4. Show that $T_{2n+2} = T_{n+1}^2 + 3\cdot T_n^2$.
    Hint: you can use the closed form from above and prove this, or prove this by induction, but those are both long and painful. It would be easier to prove it combinatorially by describing corresponding tilings.
  5. Show that $T_{2n+1} = 2\cdot T_{n}^2 + 6\cdot T_{n}T_{n-1}$.

Question 7

Note: Updated October 5, parts (a) and (b).

Consider the following recursive algorithm:

Algorithm Eu-seful(time,x,y)
  if x < time:
    study math
    Eu-seful(time,2x+3y,x)
  else:
    print("My brain is fried.")

Let $n$ be the number of times you $study$ $math$ on a call to Eu-seful($time,2,1$). We will prove that $n \leq 2+\log_3(time)$, $\forall n\geq 2$. For the inequalities below assume that $n \geq 2$. Use the definition of $T_n$ from the previous question.

  1. Prove that $T_{n}\leq time \leq T_{n+1}$.
  2. Prove that $3^{n-2}\leq T_{n}$.
  3. Using the inequalities from above, prove that $n \leq 2+\log_3time$.
image/svg+xml