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 MOOSONEE
- How may distinct ways are there to rearrange the letters in MOOSONEE (the name of a town in northern Ontario)?
3. Self-Inverting Functions
A function $f:S\to S$ is called self-inverting if $f(f(x)) = x$ for every $x\in S$. A point $x\in S$ is called a fixed point of $f$ if $f(x)=x$.
-
Prove that, if $f:S\to S$ is a self-inverting function that has $k$ fixed points, then $|S|-k$ is even.
-
Prove that, for even $n$, the number of self-inverting functions on an $n$-element set is \begin{align*} & \quad \sum_{k=0}^{n/2} \binom{n}{2k}\left(\frac{1}{2^{n/2-k}}\right)\binom{n-2k}{n/2-k}(n/2-k)! \\ & = \sum_{k=0}^{n/2}\binom{n}{2k}\left(\frac{1}{2^k}\right)\binom{2k}{k}k! \\ & = \sum_{k=0}^{n/2} \binom{n}{2k}\left(\frac{(n-2k)!}{2^{n/2-k}(n/2-k)!}\right) \end{align*} (there are three formulas here because different ones are more natural depending on how you approach the problem.)
4. Pigeonholing
Use the pigeonhole principle to prove each of the following statements:
-
Pied Piper™ is a data-compression company that claims to have an algorithm to losslessly compress any 1024-bit binary string so that it's size is not more than 1023 bits. Prove that their claim is false.
-
Let $k$ and $n$ be positive integers such that $4n-2\le k(k-1) \le n(n-1)$. Prove that every $k$-element subset of $\{1,\ldots,n\}$ contains a 4-element subset $\{a,b,x,y\}$ such that $a+b = x+y$.
-
The $(n\times n)$-grid is \[ G = \{ (i,j) : x,y\in\{1,\ldots,n\} \} \enspace . \] In other words, $G$ is the set of points whose coordinates are integers coordinates between 1 and $n$. The mid-point of a pair $a=(i_a,j_a)$ and $b=(i_b,j_b)$ is defined as \[ m(a,b) = (a+b)/2 = ((i_a+i_b)/2, (j_a+j_b)/2) \enspace . \] Prove that, if $k(k-1)> 2(2n-1)^2$, then any $k$-element subset of $G$ contains a $4$-element subset $\{a,b,x,y\}$ such that $m(a,b)=m(x,y)$. In words: The line-segment $ab$ and the line-segment $xy$ cross exactly at their common midpoints.
-
Consider the $n\times n$ square $Q=[0,n]\times [0,n]$. Prove that, if $S$ is a set of $n^2+1$ points contained in $Q$ then there are two distinct points $p,q\in S$ such that the distance between $p$ and $q$ is at most $\sqrt{2}$.
-
Two strings $s$ and $t$ are anagrams if $s$ is a permutation of $t$. For example, dilly and idyll are anagrams. Prove that any set of $n+2$ $n$-bit binary strings contains a pair of anagrams.
-
Prove that any set of 456 12-character strings over the alphabet $\{a,b,c,d\}$ contains a pair of anagrams.
5. Recurrences
-
The function $f:\N\to\N$ is defined by \[ f(n) = \begin{cases} 1 & \text{if $n=0$} \\ \frac{1}{2}\times 4^n\times f(n-1) & \text{if $n\ge 1$.} \end{cases} \] Prove that $f(n)=2^{n^2}$ for every integer $n\ge 0$.
-
Solve the following recurrence: \[ f(n) = \begin{cases} 1 & \text{if $n=0$ or $n=1$} \\ 3f(n-2) & \text{if $n> 1$.} \end{cases} \]
-
Consider the set $A_n$ of strings over the 3-character alphabet $\{a,b,c\}$ whose length is $n$ and for which $aa$ does not appear as a consecutive substring. For example: \[ A_0 = \{\varepsilon\} \] \[ A_1 = \{a,b,c\} \] \[ A_2 = \{ab, ac, ba, bb, bc, ca, cb,cc\} \] Write a recurrence for $|A_n|$. Then, using induction, show that this recurrence solves to \[ |A_n| = (\sqrt{3}/3+1/2)(1+\sqrt{3})^n - (\sqrt{3}/3-1/2)(1-\sqrt{3})^n \]
-
Consider the set $S_n$ of strings over the 3-character alphabet $\{a,b,c\}$ whose length is $n$ and for which $ab$ does not appear as a consecutive substring. For example, \[ S_0=\{\varepsilon\} , \] \[ S_1=\{a,b,c\} , \] \[ S_2=\{aa, ac, ba, bb, bc, ca, cb, cc\} , \] \[ S_3=\{a,b,c\}^3 \setminus \{aba, abb, abc, aab, bab, cab\} \] a. Argue that \[ |S_n| = 2|S_{n-1}| + \sum_{k=2}^n |S_{n-k}| + 1\enspace . \] 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?
-
Solve the following recurrence equation \[ f(n, k) = \begin{cases} 0 & \text{if $k>n$} \\ 1 & \text{if $k=0$} \\ f(n-1,k) + f(n-1, k-1) & \text{if $n\ge k > 0$} \end{cases} \]
