As­sign­ment 2

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

Name and Stu­dent Num­ber

Write your name and stu­dent num­ber on the top of the as­sign­ment

Re­peated sub­strings in bit­strings

Ar­bi­trary bit­strings

Let $B=b_1,\ldots,b_{1200}$ be a bit­string of length $1200$. Prove that $B$ con­tains at least two iden­ti­cal $10$-bit sub­strings. More pre­cisely, prove that there are dis­tinct in­dices $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 bit­strings

Re­call that a bit­string is $00$-free if it does not con­tain two con­sec­u­tive zeros. Let $B=b_1,\ldots,b_{1200}$ be a $00$-free bit­string of length $1200$. Prove that $B$ con­tains at least two iden­ti­cal $14$-bit sub­strings. More pre­cisely, prove that there are dis­tinct in­dices $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}$.

Re­cur­rences

An easy re­cur­rence

Con­sider the fol­low­ing re­cur­sive func­tion: $$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 re­cur­rence

Con­sider the fol­low­ing re­cur­sive func­tion: $$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$.

Break­ing bad

Con­sider the fol­low­ing re­cur­sive func­tion: $$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 so­lu­tion for $f(n)$ and then prove that your closed form so­lu­tion is cor­rect.

Lay­ing out chop­sticks

You have $n$ chop­sticks that you want to place on a long table. Start­ing at the left end of the table and work­ing right, you can ei­ther place a sin­gle chop­stick ver­ti­cally or you can place two chop­sticks hor­i­zon­tally, one above the other, or you can place two chop­sticks so that they form an X. Here are ex­am­ples of two dif­fer­ent place­ments when $n=8$.

Note that we can ex­press a chop­stick place­ment as a string over the al­pha­bet $\{{\times},{=},{|}\}$, where the num­ber of ${|}$ sym­bols plus twice the num­ber of ${\times}$ and ${=}$ sym­bols is $n$. Two place­ments above would be rep­re­sented by "${|}{=}{\times}{|}{\times}$" and "${\times}{|}{|}{=}{=}$".

Let $F(n)$ be the num­ber of ways of plac­ing $n$ chop­sticks.

• We'll use the con­ven­tion that $F(0)=1$.

• $F(1)=1$ be­cause the only valid place­ment is "${|}$".

• $F(2)=3$ be­cause we have the place­ments "${|}{|}$", "${\times}$", and "${=}$".

• $F(3)=5$ be­cause we have the place­ments "${|}{|}{|}$", "${{|}{\times}}$", "${{\times}{|}}$", "${{|}{=}}$", and "${=}{|}$".

Find the re­cur­rence

Write a re­cur­sive for­mula for the num­ber of ways, $F(n)$, to place $n\ge 0$ chop­sticks. Ex­plain how you get this for­mula using our usual rules for count­ing (Prod­uct Rule, Sum Rule, Com­ple­ment Rule, etc). Check that your for­mula gives the cor­rect value of $F(n)$ for at least two con­sec­u­tive val­ues of $n$ that are not ex­plic­itly de­fined in your for­mula.

Solve the re­cur­rence

Once you're sure that your re­cur­sive for­mula is cor­rect, find a closed form so­lu­tion and prove (by in­duc­tion) that this closed form matches your re­cur­sive for­mula. It's ok to use some­thing like Wol­fram Alpha to find the closed form, but you will still have to prove by in­duc­tion that the for­mula it gives you is cor­rect. Note: It's also ok to give a for­mula with two sep­a­rate cases (maybe one for even val­ues of $n$ and one for odd val­ues of $n$) as long as its not re­cur­sive.

Simon is at it again

Simon goes to the pub with $n=4^k$ dol­lars in his pocket for some non-neg­a­tive in­te­ger $k$. This is Peel Pub circa 1980, so one beer costs one dol­lar and and a plate of na­chos also costs one dol­lar. Simon re­peat­edly does the fol­low­ing, until he is left with only one dol­lar:

• Simon spends half his re­main­ing money on beer
• Simon spends half his re­main­ing money on na­chos

Let $B(k)$ be the num­ber of beers Simon drinks. Let $N(k)$ be the num­ber of plates of na­chos Simon eats.

Hint: In solv­ing the ques­tions below, it's help­ful to re­mem­ber that $4^k=2^{2k}$.

How much beer?

Give a re­cur­rence (with an ex­pla­na­tion) for $B(k)$. Find a closed form for your re­cur­rence and prove it is cor­rect.

How many na­chos?

Give a re­cur­rence (with an ex­pla­na­tion) for $N(k)$. Find a closed form for your re­cur­rence and prove it is cor­rect.

A weird re­cur­rence

Con­sider the fol­low­ing func­tion

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 ter­mi­nate?

Ex­plain why, for any in­te­ger $n\ge 1$, $P(n)$ even­tu­ally ter­mi­nates.

How much does it print?

Write and solve a re­cur­rence that de­scribes ex­actly how many times $P(n)$ prints "hello" for any pos­i­tive in­te­ger $n$.

Hint: Count­ing from $n$ up to the next in­te­ger that is a mul­ti­ple of $4$ takes $4\lceil n/4\rceil -n$ steps.