Assignment 2

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

# Administrivia

- 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.
- When writing your solutions:
- You must justify your answers.
- The answers should be concise, clear and neat.
- When presenting proofs, every step should be justified.

# Meat

## 1. ID

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

## 2. Arrangements of PUNKEYDOODLES

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

## 3. Modern Coupling

- 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?
- 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:

- 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?
- 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. - 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. - 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. - 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$.
- 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$.)
- 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.

- 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.
- 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.
- 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.
- 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$.
- 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?