$\newcommand{\R}{\mathbb{R}}\DeclareMathOperator{\E}{\mathbf{E}}\DeclareMathOperator{\deg}{deg}\newcommand{\N}{\mathbb{N}}$
Assignment 2

If your browser has trouble rendering MathJaX, then use this PDF file

• Your assignment must be submitted as a single PDF file through cuLearn
• Late assignments will not be accepted under any circumstances. If you're unable to complete the assignment due to a valid and documented medical or personal situation then the weight of this assignment can be shifted to the weight of the remaining assignments.
• You are encouraged to collaborate on assignments, but at the level of discussion only. When writing your solutions, you must do so in your own words.
• Past experience has shown conclusively that those who do not put adequate effort into the assignments do not learn the material and have a probability near 1 of doing poorly on the exams.
• The answers should be concise, clear and neat.
• When presenting proofs, every step should be justified.

# Meat

## 1. ID

1. Make sure the first thing on page 1 of your assignment is your name and student number.

## 2. Arrangements of PUNKEYDOODLES

1. How may distinct ways are there to rearrange the letters in PUNKEYDOODLES (the name of a town in Ontario)?

## 3. Modern Coupling

1. Suppose we have a group of $n$ women and $n$ men, all heterosexual and all strictly monogamous. How many ways are there to make $n$ couples out of these $2n$ people?
2. Suppose we have $2n$ people, each of whom is bisexual but strictly monogamous. How many ways are there to make $n$ couples out of these $2n$ people?

## 4. Pigeonholing

Use the pigeonhole principle to solve each of the following problems:

1. In an anonymous survey of a group of 20 men and 20 women, the men reported a total of 81 sexual encounters with women in the group, and all women reported having at most 4 sexual encounters with men in the group. Is everyone telling the truth?
2. A group of $n$ agents all start at the same location and each one takes a $\le m$-walk on the line, where a $\le m$-walk is a sequence of at most $m$ steps and each step moves the agent one unit to the left or one unit to the right. (Different agents might take different walks.) Prove that, if $n> 2m+1$, then some pair of agents finishes their walk at the same location.
3. A group of $n$ agents all start at the same location and each one takes an $m$-walk on the line, where a $m$-walk is a sequence of exactly $m$ steps and each step moves the agent one unit to the left or one unit to the right. (Different agents might take different walks.) Prove that, if $n> m+1$, then some pair of agents finishes their walk at the same location.
4. Let $V=\{v_1,\ldots,v_k\}$ be any set of vectors in $\R^2$. Suppose $n$ agents each start at $(0,0)$ and each takes a $mV$-walk where a $mV$-walk consists of a sequence of exactly $m$ steps and each step moves the agent along a vector in $V$. Prove that, if $n>\binom{m+k-1}{k-1}$, then some pair of agents finishes their walk at the same location.
5. Let $S$ be a $k$-element subset of $\{1,\ldots,n\}$. Prove that, if $k> \lceil n/2\rceil$, then there exists $x,y\in S$ such that $x-y=1$.
6. Let $S$ be a $k$-element subset of $\{1,\ldots,n\}$. Prove that, if $\binom{k}{2}> n-1$, then there exists $a,b,x,y\in S$ such that $a\neq b$, $\{a,b\}\neq\{x,y\}$ and $b-a=y-x$. (Note that it may be the case that $b=x$ or $a=y$.)
7. Let $S$ be a $k$-element subset of $\{1,\ldots,n\}$. Prove that, if $\lfloor k/2\rfloor\cdot\lceil k/2\rceil> n-1$, then there exists a $4$-element subset $\{a,b,x,y\}\subset S$ such that $a-b=x-y$. (Unlike the previous question, $a,b,x,y$ must be 4 distinct elements.)

## 5. Recurrences

Some of the following questions ask for a closed-form formula. This is a formula that is non-recursive and doesn's use the summation ($\sum$) or product ($\prod$) notation. These formulas can use any of the special functions we've seen in class, including the factorial function and binomial coefficients.

1. Let $a,b\ge 0$ be two real numbers and consider the function $f:\N\to\R$ given by the recurrence $f(n) = \begin{cases} a & \text{if n=0} \\ f(n-1) + b & \text{if n\ge 1} \end{cases}$ Write a closed form formula for $f(n)$ and prove that your formula is correct.
2. Consider the function $f:\N\to\N$ defined by the recurrence $f(n) = \begin{cases} \frac{1}{2} & \text{if n=0} \\ \frac{1}{2}\cdot n\cdot f(n-1) & \text{if n\ge 1.} \end{cases}$ Write a closed form formula for $f(n)$ and prove that your formula is correct.
3. Consider the function $f:\N^+\to\N$ defined by: $f(n) = \begin{cases} 1 & \text{if n\in\{1,2,3\}} \\ 4f(n-3) & \text{if n> 3.} \end{cases}$ Write a closed form formula for $f(n)$ and prove that your formula is correct.
4. Consider the set $A_n$ of strings over the 4-character alphabet $\{a,b,c,d\}$ whose length is $n$ and for which $cc$ does not appear as a consecutive substring. For example: $A_0 = \{\varepsilon\}$ $A_1 = \{a,b,c,d\}$ $\require{cancel} A_2 = \{aa, ab, ac, ad, ba, bb, bc, bd, ca, cb, \xcancel{cc,} cd, da, db, dc, dd\}$ Write a recurrence for $|A_n|$. Then, using induction, show that this recurrence solves to $|A_n| = (1/2 + 5\cdot \sqrt{21}/42)\cdot\alpha^n + +(1/2-5\cdot\sqrt{21}/42)\cdot \beta^n \enspace ,$ where $\alpha=(3+ \sqrt{21})/2$ and $\beta=(3-\sqrt{21})/2$.
5. Consider the set $S_n$ of binary strings whose length is $n$ and for which $010$ does not appear as a consecutive substring. For example, $S_0=\{\varepsilon\} ,$ $S_1=\{0,1\} ,$ $S_2=\{00, 01, 10, 11\} ,$ $\require{cancel} S_3=\{000, 001, \xcancel{010,} 011, 100, 101, 110, 111\}$ $\require{cancel} S_4=\{0000, 0001, \xcancel{0010,} 0011, \xcancel{0100,} \xcancel{0101,} 0110, 0111, 1000, 1001, \xcancel{1010,} 1011, 1100, 1101, 1110, 1111 \}$ a. Argue that, for $n\ge 3$, \begin{equation} |S_n| = |S_{n-1}| + \sum_{k=3}^n |S_{n-k}| + 2\enspace . \end{equation} b. Write a program to compute $|S_n|$ for $n=0,\ldots,20$ and look up the resulting sequence in the Online Encyclopedia of Integer Sequences. What did you find?