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

Name and Student Number

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

Repeated substrings in bitstrings

Arbitrary bitstrings

Let $B=b_1,\ldots,b_{1200}$ be a bitstring of length $1200$. Prove that $B$ contains at least two identical $10$-bit substrings. More precisely, prove that there are distinct indices $i,j\in\{1,\ldots,1191\}$ such that $b_{i},b_{i+1},\ldots,b_{i+9}=b_j,b_{j+1},\ldots,b_{j+9}$.

$00$-free bitstrings

Recall that a bitstring is $00$-free if it does not contain two consecutive zeros. Let $B=b_1,\ldots,b_{1200}$ be a $00$-free bitstring of length $1200$. Prove that $B$ contains at least two identical $14$-bit substrings. More precisely, prove that there are distinct indices $i,j\in\{1,\ldots,1187\}$ such that $b_{i},b_{i+1},\ldots,b_{i+13}=b_j,b_{j+1},\ldots,b_{j+13}$.

Recurrences

An easy recurrence

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

Prove that $f(n)=\tfrac{1}{2}(7\cdot 3^n-5)$ for all $n\ge 0$.

A wild recurrence

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

Prove that $f(n)=2^{n-2}\left((-1)^{n+1}+1\right)$ for all $n\ge 0$.

Breaking bad

Consider the following recursive function: \[ f(n) = \begin{cases} 1 & \text{if $n=1$} \\ \max\{f(\ell)+f(n-\ell): \ell\in\{1,\ldots,n-1\}\} & \text{if $n\ge 2$} \end{cases} \]

Give a closed form solution for $f(n)$ and then prove that your closed form solution is correct.

Laying out chopsticks

You have $n$ chopsticks that you want to place on a long table. Starting at the left end of the table and working right, you can either place a single chopstick vertically or you can place two chopsticks horizontally, one above the other, or you can place two chopsticks so that they form an X. Here are examples of two different placements when $n=8$.

alt text

alt text

Note that we can express a chopstick placement as a string over the alphabet $\{{\times},{=},{|}\}$, where the number of ${|}$ symbols plus twice the number of ${\times}$ and ${=}$ symbols is $n$. Two placements above would be represented by "${|}{=}{\times}{|}{\times}$" and "${\times}{|}{|}{=}{=}$".

Let $F(n)$ be the number of ways of placing $n$ chopsticks.

Find the recurrence

Write a recursive formula for the number of ways, $F(n)$, to place $n\ge 0$ chopsticks. Explain how you get this formula using our usual rules for counting (Product Rule, Sum Rule, Complement Rule, etc). Check that your formula gives the correct value of $F(n)$ for at least two consecutive values of $n$ that are not explicitly defined in your formula.

Solve the recurrence

Once you're sure that your recursive formula is correct, find a closed form solution and prove (by induction) that this closed form matches your recursive formula. It's ok to use something like Wolfram Alpha to find the closed form, but you will still have to prove by induction that the formula it gives you is correct. Note: It's also ok to give a formula with two separate cases (maybe one for even values of $n$ and one for odd values of $n$) as long as its not recursive.

Simon is at it again

Simon goes to the pub with $n=4^k$ dollars in his pocket for some non-negative integer $k$. This is Peel Pub circa 1980, so one beer costs one dollar and and a plate of nachos also costs one dollar. Simon repeatedly does the following, until he is left with only one dollar:

Let $B(k)$ be the number of beers Simon drinks. Let $N(k)$ be the number of plates of nachos Simon eats.

Hint: In solving the questions below, it's helpful to remember that $4^k=2^{2k}$.

How much beer?

Give a recurrence (with an explanation) for $B(k)$. Find a closed form for your recurrence and prove it is correct.

How many nachos?

Give a recurrence (with an explanation) for $N(k)$. Find a closed form for your recurrence and prove it is correct.

A weird recurrence

Consider the following function

P(n):
  print("hello")
  if n = -3
    return
  else if n is divisible by 4:
    P(n-7)
  else
    P(n+1)

Why does it terminate?

Explain why, for any integer $n\ge 1$, $P(n)$ eventually terminates.

How much does it print?

Write and solve a recurrence that describes exactly how many times $P(n)$ prints "hello" for any positive integer $n$.

Hint: Counting from $n$ up to the next integer that is a multiple of $4$ takes $4\lceil n/4\rceil -n$ steps.

image/svg+xml