This is a Pigeonhole Principle question, where pigeons are the dolls that Derek made last week and the holes are all the different kinds of dolls that can be made. We have to do a bit of work to count the number of holes.

By the Product Rule, the number of possible dolls is $3\times 3\times 2\times 20=360$. Derek made $365$ dolls last week, so by the Pigeonhole Principle, Derek made at least one type of doll at least $\lceil 365/360\rceil = 2$ times. So, yes, we can be sure that Derek made two identical dolls last week.

This is a Pigeonhole Principle question where the pigeons are the $2$-element subsets of $\{1,\ldots,21\}$ and the holes are the possible values of $x_a+x_b$ when $x_a$ and $x_b$ are distinct integers in $\{1,\ldots,100\}$.

The number of $2$-element subsets of $\{1,\ldots,21\}$ is $\binom{21}{2}=\frac{21\cdot 20}{2}=210$. For any such subset $\{a,b\}$, the sum $x_a+x_b$ is at least $1+2=3$ and is at most $100+99=199$, so $x_a+x_b\in\{3,\ldots,199\}$, which is a set of size $199-2=197$. Since $210>197$, the Pigeonhole Principle implies that there are distinct subsets $\{a,b\}$ and $\{c,d\}$ such that $x_a+x_b=x_c+x_d$. The question asks us to prove that these sets are not only distinct, but disjoint. Luckily, this is easy. Suppose, for the sake of contradiction, that $\{a,b\}$ and $\{c,d\}$ are not disjoint. Then, without loss of generality, we can assume $a=c$. Then the condition $x_a+x_b=x_c+x_d$ implies that $x_b=x_d$, which implies that $b=d$, so $\{a,b\}=\{c,d\}$. But this is a contradiction since $\{a,b\}$ and $\{c,d\}$ are distinct (meaning that $\{a,b\}\neq\{c,d\}$).

This is a Pigeonhole Principle question where the pigeons are the $101$ people in the room. To answer this question, we need to partition the room into $100$ regions (the holes) in such a way that, if two people are the same region then they are at most $1.45$m apart from each other.

The easiest shape we can think of is a $1\mathrm{m}\times 1\mathrm{m}$ square. If two people are in the same $1\mathrm{m}\times 1\mathrm{m}$ square, then their distance (in meters) is at most $\sqrt{1^2+1^2}=\sqrt{2}\lt 1.45$. (This happens when the two people are at opposite corners of the square.)

So, partition the room into $100$ $1\mathrm{m}\times 1\mathrm{m}$ meter squares in the obvious way. Since there are $101>100$ people, there is some square with at least two people standing in it. Therefore, there is a pair of people (in that square) whose distance from each other is at most $1.45\mathrm{m}$. (If you want to be really fussy with this question, you discuss how you treat people that are standing on the boundary of two, three, or four different squares, but this is a boring detail.)

$2001$, since $\lceil 2001/1000\rceil = 3$.

This is similar to the example about Simon's Drinking Problem. Consider the length-$60$ sequence $x_1,x_2,\ldots,x_{30},x_1+9,x_2+9,\ldots,x_{30}+9$. The smallest number in this sequence is at least $1$ and the largest number in this sequence is at most $59$, so there are at most $59$ different numbers in this sequence. Since the sequence has length $60>59$, some number must appear twice in this sequence. Since $x_1,\ldots,x_{30}$ are distinct, this means that there exists $i$ and $j$ such that $x_i=x_j+9$, which means that $x_i-x_j=9$.

Let $I=\{(x_1,x_2,x_3): x_1,x_2,x_3\in S\}$ be the set of all possible inputs to $f$. By the Product Rule, $|I|=|S|^3$. Since $|S|>k^{1/3}$, $|I|=|S|^3 > k$. By the Pigeonhole Principle, there must be two distinct triples $(x_1,x_2,x_3)\in I$ and $(y_1,y_2,y_3)\in I$ such that $f(x_1,x_2,x_3)=f(y_1,y_2,y_3)$.

In class (and in Section 4.1.2 of the textbook) we saw that the number of $00$-free bitstrings of length $n$ is $f_{n+2}$. Since every substring of $B$ is $00$-free, there are at most $f_{16}=987$ distinct $14$-bit substrings in $B$. Since there are $1187>987$ indices that each define a $14$-bit substring of $B$, there must be two distinct indices $i$ and $j$ that define the same $14$-bit substring.

The first few values of $q$ are $q(0)=3$, $q(1)=5$, $q(2)=7$, $q(3)=9$. From this pattern we can guess that $q(n)=3+2n$. Now we prove, using induction on $n$, that our guess is correct.

Base case: If $n=0$, then $3+2\cdot0 = 3=q(0)$ by the definition of $q$.

Inductive step: Assume that $q(k)=3+2k$ for all $k\in\{0,\ldots,n-1\}$. Then, for $n\ge 1$, \begin{align*} q(n) & = 2 + q(n-1) & \text{(by definition)} \\ & = 2 + 3+2(n-1) & \text{(by the inductive hypothesis)} \\ & = 3+2n & \text{(by algebra).} \end{align*} Therefore, $q(n) = 3+2n$ for all integers $n\ge 0$.

The first few values of $q$ are $q(0)=3$, $q(1)=3$, $q(2)=5+q(0)=8$, $q(3)=5+q(1)=8$, $q(4)=5+q(2)=13$, $q(5)=5+q(3)=13$. From this pattern we can guess that $q(n)=3+5\lfloor n/2\rfloor$. Now we prove, using induction on $n$, that our guess is correct.

Base cases: If $n=0$, then $3+5\lfloor 0/2\rfloor = 3=q(0)$ by the definition of $q$. If $n=1$, then $3+5\lfloor 1/2\rfloor = 3=q(1)$ by the definition of $q$.

Inductive step: Assume that $q(k)=3+5\lfloor k/2\rfloor$ for all $k\in\{0,\ldots,n-1\}$. Then, for $n\ge 2$, \begin{align*} q(n) & = 5 + q(n-2) & \text{(by definition)} \\ & = 5 + 3+5\lfloor(n-2)/2\rfloor & \text{(by the inductive hypothesis)} \\ & = 3 + 5\lfloor n/2\rfloor & \text{(since $\lfloor n/2\rfloor = 1+\lfloor (n-2)/2\rfloor$ for $n\ge 2$).} \end{align*} Therefore, $q(n) = 3+5\lfloor n/2\rfloor$ for all integers $n\ge 0$.

For a large value of $n$, we can play around with the recurrence a bit to see that \begin{align*} q(n) &= 10 q(n-1) \\ &= 10 (10 q(n-2)) \\ &= 10 (10 (10 q(n-3))) \\ &= 10^{n} q(0) &= 3\cdot 10^{n} \end{align*} This seems like a good guess, though there is some danger that the exponent is off by one if we miscounted. Now we prove, using induction on $n$, that our guess is correct.

Base cases: If $n=0$, then $3\cdot 10^0 = 3\cdot 1 = 3=q(0)$ by the definition of $q$.

Inductive step: Assume that $q(k)=3\cdot 10^k$ for all $k\in\{0,\ldots,n-1\}$. Then, for $n\ge 1$, \begin{align*} q(n) & = 10\cdot q(n-1) & \text{(by definition)} \\ & = 10\cdot (3\cdot 10^{n-1}) & \text{(by the inductive hypothesis)} \\ & = 3\cdot 10^n \end{align*} Therefore, $q(n) = 3\cdot 10^n$ for all integers $n\ge 0$.

We prove this by induction on $n$. The base case $n=0$ is satisfied since $\tfrac{1}{2}(7\cdot 3^0-5)=\tfrac{1}{2}(7-5)=1=f(0)$. Now assume that $f(k)=\tfrac{1}{2}(7\cdot 3^k-5)$ for all $k\in\{0,\ldots,n-1\}$ and prove the statement for an arbitrary integer $n\ge 1$.
\begin{align*} f(n) & = 3f(n-1)+5 & \text{(by the definition of $f(n)$)} \\ & = 3\cdot\tfrac{1}{2}(7\cdot 3^{n-1}-5) + 5 & \text{(by the inductive hypothesis with $k=n-1$)} \\ & = \tfrac{1}{2}(7\cdot 3^{n}-15) + 5 & \text{(by algebra)} \\ & = \tfrac{1}{2}(7\cdot 3^{n}-5) & \text{(by algebra).} \end{align*}

For a large value of $n$, we can play around with the recurrence a bit to see that \begin{align*} q(n) &= 8 + q(\lfloor n/3\rfloor) \\ &= 8 + 8 + q(\lfloor\lfloor n/3\rfloor/3\rfloor) \\ &= 8 + 8 + 8 + q(\lfloor\lfloor\lfloor n/3\rfloor/3\rfloor/3\rfloor) \\ &= 8 + 8 + 8 + \cdots + 8 + q(0) \\ &= 8 + 8 + 8 + \cdots + 8 + 3 \end{align*} The number of times $8$ appears in the last line is equal to the number of times we can divide $n$ by $3$ and take the floor before we get to $0$. The floor is a bit annoying, but we can guess that the answer is something like $\log_3 n$. Since we want an integer, we could try $\lfloor\log_3 n\rfloor$, but that's not right, since $\lfloor\log_3(1)\rfloor=\lfloor 0\rfloor$ and $\lfloor\log_3(2)\rfloor=0$. To fix this, let's guess that the number of times $8$ appears in the last line is $1+\lfloor\log_3 n\rfloor$.

So we are guessing that $q(n) = 3 + 8(1+\lfloor\log_3 n\rfloor) = 11+8\lfloor\log_3 n\rfloor$ when $n\ge 1$ and $q(n)=3$ when $n=0$. (We need the special case $n=0$ because $\log_3(0)=-\infty$). Now we prove, using induction on $n$, that our guess is correct.

Base cases: If $n=0$, then $3=q(0)$ by the definition of $q$. If $n=1$, then $11+8\lfloor\log_3 1\rfloor=11 +8\lfloor 0\rfloor = 11= 8 + 3 = 8+q(0)=8+q(\lfloor 1/3\rfloor)=q(1)$, also by the definition of $q$. If $n=2$, then $11+8\lfloor\log_3 2\rfloor=11 +8\cdot 0 = 11= 8 + 3 = 8+q(0)=8+q(\lfloor 2/3\rfloor)=q(2)$, also by the definition of $q$.

Inductive step: Assume that $q(k)=11+8\lfloor \log_3 k\rfloor$ for all $k\in\{1,\ldots,n-1\}$. Then, for $n\ge 3$, \begin{align*} q(n) & = 8 + q(\lfloor n/3\rfloor) & \text{(by definition)} \\ & = 8 + 11 + 8\lfloor\log_3 \lfloor n/3\rfloor\rfloor & \text{(by the inductive hypothesis)} \\ & = 8 + 11 + 8\lfloor(\log_3 n)-1\rfloor & \text{} \\ & = 8 + 11 + 8(\lfloor\log_3 n\rfloor-1) & \text{} \\ & = 11 + 8\lfloor\log_3 n\rfloor & \text{} \end{align*} Therefore, $q(n) = 11 + 8\lfloor\log_3 n\rfloor$ for all integers $n\ge 0$. (The annoying bit of this proof is convincing yourself that $\lfloor\log_3 \lfloor n/3\rfloor\rfloor=\lfloor(\log_3 n)-1\rfloor$ for $n\ge 3$. This really does require $n\ge 3$, since otherwise we have a $\log_3(0)$.)

Calculating the first few values of $f(n)$ is enough to convince you that $f(n)=n$. This is obviously true for $n=1$. Now assume $f(k)=k$ for all $k\in\{1,\ldots,n-1\}$ and prove the statement for $n\ge 2$. For $n\ge 2$ we have

\begin{align*} f(n) & = \max\{f(k)+f(n-k): k\in\{1,\ldots,n-1\}\} & \text{(by the definition of $f(n)$)} \\ & = \max\{\ell+f(n-\ell): \ell\in\{1,\ldots,n-1\}\} & \text{(by the inductive hypothesis, since $\ell\in\{1,\ldots,n-1\}$)} \\ & = \max\{\ell+ (n-\ell): \ell\in\{1,\ldots,n-1\}\} & \text{(by the inductive hypothesis, since $n-\ell\in\{1,\ldots,n-1\}$)} \\ & = \max\{n: \ell\in\{1,\ldots,n-1\}\} & \text{(by algebra)} \\ & = n \end{align*}

For $n\ge 2$, a placement of chopsticks can either begin with a ${|}$, a ${\times}$, or a ${=}$. In the first case, what follows is any placement of $n-1$ chopsticks. In the second case, what follows is any placement of $n-2$ chopsticks. In the third case, what follows is any placement of $n-2$ chopsticks. Using the Sum Rule, this gives the recurrence \[ F(n) = F(n-1) + 2F(n-2) \] with the base cases $F(0)=1$ and $F(1)=1$ given in the question. With this recurrence, we get $F(2)=F(1)+2F(0)=1+2=3$ and $F(3)=F(2)+2F(1)= 3+2=5$, both of which are correct.

If Simon has only $1=4^0$ dollars then Simon gets no beer, so $B(0)=0$. Otherwise, Simon starts with $n=4^{k}=2^{2k}$ dollars for some $k\ge 2$. He then spends half his money on beer, drinking $2^{2k-1}$ beers and leaving him with $2^{2k-1}$ dollars. He then spends half his money on nachos, leaving him with $2^{2k-2}=2^{2(k-1)}=4^{k-1}$ dollars. He then repeats this process with his remaining $4^{k-1}$ dollars. This gives the recurrence \[ B(k) = \begin{cases} 0 & \text{if $k=0$} \\ 2^{2k-1} + B(k-1) & \text{if $k\ge 1$} \end{cases} \] The easiest way to guess the solution here is just to repeatedly expand the recurrence: \begin{align*} B(k) & = 2^{2k-1} + B(k-1) \\ & = 2^{2k-1} + 2^{2(k-1)-1} + B(k-2) \\ & = 2^{2k-1} + 2^{2k-3} + B(k-2) \\ & = 2^{2k-1} + 2^{2k-3} + 2^{2k-5} + B(k-3) \\ & = 2^{2k-1} + 2^{2k-3} + 2^{2k-5} + 2^{2k-7} + \cdots + 32 + 8 + 2 \\ & = \tfrac{1}{2}(2^{2k} + 2^{2k-2} + 2^{2k-4} + \cdots + 2^6 + 2^4 + 2^2) \\ & = \tfrac{1}{2}\sum_{j=1}^k 4^j \\ & = \tfrac{2}{3}(4^k - 1) \end{align*} Later in the course, we'll learn how to evaluate the sum $\sum_{j=1}^{k} 4^j$ directly. For now, we can just check that our guess was correct using induction.

When $k=0$, we have $\tfrac{2}{3}(4^0-1)=\tfrac{2}{3}(1-1)=0=B(0)$, which handles the base case. Now we can assume $B(\ell)=\tfrac{2}{3}(4^{\ell}-1)$ for all $\ell\in\{0,\ldots,k-1\}$ and use this to prove that $B(k)=\tfrac{2}{3}(4^k-1)$, for $k\ge 1$. For $k\ge 1$, \begin{align*} B(k) & = 2^{2k-1} + B(k-1) & \text{(by the definition of $B(k)$)} \\ & = 2^{2k-1} + \tfrac{2}{3}(4^{k-2}-1) & \text{(by the inductive hypothesis with $\ell=k-1$)} \\ & = 2^{2k-1} + \tfrac{2}{3}(2^{2k-2}-1) & \text{(by algebra)} \\ & = 2^{2k-1} + \tfrac{1}{3}(2^{2k-1}-2) & \text{(by algebra)} \\ & = \tfrac{4}{3}\cdot 2^{2k-1} -\tfrac{2}{3} \\ & = \tfrac{2}{3}\cdot 2^{2k} -\tfrac{2}{3} \\ & = \tfrac{2}{3}(4^{k} -1) \\ \end{align*}

If Simon has only $1=4^0$ dollars then Simon gets no nachos, so $N(0)=0$. Otherwise, Simon starts with $n=4^{k}=2^{2k}$ dollars for some $k\ge 1$. He then spends half his money on beer, leaving him with $2^{2k-1}$ dollars. He then spends half his money on nachos, eating $2^{2k-2}$ plates of nachos, and leaving him with $2^{2k-2}=2^{2(k-1)}=4^{k-1}$ dollars. He then repeats this process with his remaining $4^{k-1}$ dollars. This gives the recurrence \[ N(k) = \begin{cases} 0 & \text{if $k=0$} \\ 2^{2k-2} + N(k-1) & \text{if $k\ge 1$} \end{cases} \] At this point you can either repeat all the steps used to solve $B(k)$ or you can notice that $N(k)=\tfrac{1}{2}B(k)$. In either case, you get the answer $N(k)=\tfrac{1}{3}(4^k-1)$.

Start by drawing the recursion tree, labelled with input value. (This is the tree whose root is $57$, whose two children are $56$ and $55$. The children of $56$ are labelled $55$ and $54$, and so on.)

Drawing the whole tree would take a really long time, but you don't need to draw anything below the nodes labelled $50$. Even drawing this tree would take a long time (it has $21$ leaves). Avoid drawing the whole thing by noticing that, if you know how many leaves the subtree rooted at a node labelled $x$ has, then you can just reuse that information each time you encounter a node labelled $x$.