COMP2804: Discrete Structures II
$\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

Administrivia

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?