COMP2804: Discrete Structures II
$\newcommand{\R}{\mathbb{R}}\DeclareMathOperator{\E}{\mathbf{E}}\DeclareMathOperator{\deg}{deg}\newcommand{\N}{\mathbb{N}}$

Assignment 1

Question 1

Make sure that the PDF file you submit begins with your name and student number on the first page.

Question 2

We have seen in Lecture 1 that if we colour the edges of the complete graph $K_6$ on six vertices using two colours, then there will always be a monochromatic triangle; a cycle of length $3$ whose edges are all red or all blue.

  1. Show that this result is tight by drawing an edge colouring of the graph $K_5$ using two colours that has no monochromatic $K_3$. Just to be clear, you should make a drawing that looks something like this, but that has no monochromatic triangles:

    An edge 2-colouring of K_5

Now let's try to generalize the problem. Let $R(s,t)$ be the minimum integer $n$ such that every $2$-colouring of the edges of $K_n$ contains:

The theorem mentioned above says that $R(3,3)\le 6$ and your solution to the previous question shows that $R(3,3)> 5$, so $R(3,3)=6$.

  1. Explain, in a few words, why $R(s,2)=s$ for any $s\ge 2$. (This is also the same as saying that $R(2,t)=t$ for any $t\ge 2$.)
  2. Now argue that that, for any integers $s,t\ge 3$, $R(s,t)\le R(s-1,t) + R(s, t-1)$. (Hint: Start by slowly and carefully repeating the argument used in class and modifying it as necessary.)

Note that these two questions give a proof, by induction, that $R(s,t)$ is finite; for any $s,t\ge 2$, any sufficiently large group of people will contain $s$ mutual friends or $t$ mutual strangers.

Question 3

Before attempting this question, make sure that you've watched Lecture 2 on the Product Rule.

Canada's Wonderland has the following attractions, all rated as "Agressive thrill rides":

Pat always rides roller coasters first (which are fun), then carnival rides (which make Pat sick), then water slides (which Pat finds refreshing). Order matters to Pat so, for example, if he rides The Behemoth and then the Dragon Fyre, that's different than riding the Dragon Fyre and then the Behemoth.

  1. If Pat wants to ride one attaction of each type (roller coaster, water slide, carnival ride), then how many options does he have?
  2. If Pat wants to ride two attractions of each type and doesn't mind riding the same attraction twice, then how many options does he have?
  3. If Pat wants to ride two attractions of each type and doesn't want to ride the same attraction twice, then how many options does he have?
  4. If Pat wants to ride rollercoasters 20 times and doesn't want to ride the same rollercoaster twice in a row, then how many options does he have?

Question 4

Let $n\ge 1$ be an integer and let $S=\{1,\ldots,n\}$. Use the Product Rule (Lecture 2) to answer these questions.

  1. How many ways are there to partition $S$ into four sets $X$, $Y$, $Z$, and $W$? [Partition means that each element of $S$ is contained in exactly one of $X$, $Y$, $Z$, or $W$ (and we allow any of these four sets to be empty)]
  2. How many ways are there to pick three pairwise-disjoint sets $X,Y,Z\subseteq S$? [Pairwise disjoint means that each element of $S$ appears in at most one of $X$, $Y$, or $Z$.]
  3. How many ways are there to make three subsets $X, Y, Z\subseteq S$ so that any element of $S$ appears in at most $2$ of the three sets?

Question 5

Each of the following questions, which are motivated by the movie Four Rooms can be answered using the rules (Bijection, Complement, Sum, or Inclusion-Exclusion) introduced in Lecture 3.

Note: Parts 3 and 4 need binomial coefficients, from Lecture 4

Note: In each part of this question, each person must go into one of the rooms.

  1. How many ways are there to place $n$ distinct people into four different rooms? (Hint: Question 4 contains a similar question.)
  2. How many ways are there to place $n$ distinct people into four different rooms so that there are at least two non-empty rooms?
  3. How many ways are there to place $n\ge 7$ people into two different rooms so that one of the rooms contains exactly $3$ people?
  4. How many ways are there to place $n\ge 10$ people into three different rooms so that at least one of the rooms contains exactly $3$ people?

Question 6

In this question we're going to prove a binomial identity using a combinatorial proof (also known as counting two different ways) discussed in Lecture 4. Let $A$ be the set of all ways to colour the elements of an $n$ element set using $c$ colours. (Formally, $A$ is the set of functions $f:\lbrace 1,\ldots,n\rbrace\to\lbrace 1,\ldots,c\rbrace$.)

  1. Give a simple expression for $|A|$ and justify it using something covered in class/in the textbook.
  2. Prove that $|A|=\sum_{k=0}^n (c-1)^{k}\binom{n}{k}$.

Question 7

Before attempting this question, you should be familiar with the content of Lecture 5.

Dappledown Farm is a farm in Tennessee run by a farmer who likes to make all kinds of extraordinary claims. Give combinatorial proofs that each of the following claims made by the farmer is true:

  1. $9\cdot\binom{8}{4}\cdot\binom{4}{2} = \binom{9}{2}\cdot\binom{7}{2}\cdot 5$
  2. $\binom{10}{2}\cdot\binom{8}{2} = \binom{10}{6}\cdot \binom{4}{2}$

Question 8

Last Halloween 20 different kids came trick-or-treating to my house and I gave out 100 identical pieces of candy in such a way that each kid got at least three pieces of candy. How many different ways could I have done this?