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 all have the same colour.

  1. Prove that if we colour the edges of $K_5$ with $2$ colours, red and green, so that the number of red edges is not equal to the number of green edges, then $K_5$ will always have a monochromatic triangle.

  2. We colour the edges of the graph $K_{16}$ using $3$ colours, red, green, and blue. Prove that if the number of red, green, and blue edges are not all equal, then we will always have a monochromatic triangle.
    Hint: First show that if $r$, $g$, and $b$ are not all equal, then there must be a vertex of $K_{16}$ with at least $6$ edges of the same colour.

Question 3

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

Pat is going to the George Thorogood concert, but first he makes a stop at the bar, where they have

  1. If Pat wants to drink one bourbon, one scotch, and one beer—in that order—how many options does Pat have?

  2. If Pat wants to drink one bourbon, one scotch, and one beer—not necessarily in that order—how many options does Pat have? (Drinking the same three drinks in different orders counts as two different options.)

  3. If Pat just wants to have three different drinks then how many options does he have? (For example, he might drink three different kinds of scotch)

  4. If Pat just wants to have three drinks and doesn't mind drinking the same drink twice, or even three times, then how many options does he have?

Question 4

Use the Product Rule (Lecture 2) to answer the first three of these questions (the last one may need something extra).

Suppose we have a set of $n$ air travellers called $p_1,\ldots,p_n$. They've just landed at Pearson International Airport and they get off the plane one at a time with $p_1$ getting off first, followed by $p_2$, and so on, up to $p_n$. The arrival hall at the airport has three queues, $Q_1,\ldots,Q_3$ and they're all empty when the air travellers arrive. The customs agents are on their break, so all passengers have time to choose a queue before any passenger gets to leave.

  1. The travellers come from England and walk calmly through the corridor from the plane to the arrival hall and arrive in the same order they got off the plane. In this way, their order within each queue matches the order they got off the plane. How many ways are there to assign the travellers to queues?

  2. What if, when each passenger arrives at the arrival hall, they always choose a queue with the fewest number of people already in it?

  3. What if the travellers came from Amsterdam and raced each down the corridor before the arrival hall so they don't necessarily join the queues in the order they got off the plane? Since they're racing, they don't have time to choose the shortest queue, so they pick one arbitrarily.

  4. What if we're dealing with the English passengers again, like in question 1, but this time we require that no queue is empty?

Question 5

Each of the following questions 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

The Ottawa Humane Society has $n$ dogs $d_1,\ldots,d_n$ and $m$ cages $c_1,\ldots,c_m$.

  1. If they have $m\ge n$ cages, how many ways are there to put the dogs into cages so that each do gets their own cage?

  2. Suppose $n$ is even and they have exactly $m=n/2$ cages. Half the dogs are white and half the dogs are black. How many ways are there to place the dogs into cages so that each cage contains one white dog and one black dog?

  3. Suppose $n$ is even and they have $m=n/2$ cages. All the dogs are black. How many ways are there to place the dogs into cages so that there are exactly two dogs in each cage? (Careful, this is much trickier than the previous question!)

  4. Suppose that $n\ge 7$ and they only have $m=4$ (really large) cages. How many ways are there to place the dogs into cages so that at least two cages are non-empty?

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 $n\ge m\ge k$ be integers. We have an $n$-element set $S$. We want to colour $k$ elements of $S$ red and $m-k$ elements of $S$ blue.

  1. Use the Product Rule to show that the number of ways we can do this is $\binom{n}{m}\binom{m}{k}$.

  2. Use the Product Rule to show that the number of ways we can do this is also $\binom{n}{k}\binom{n-k}{m-k}$.

Question 7

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

Let $i,j,k,\ell$ be positive integers, and let $n=i+j+k+\ell$.

  1. Give a combinatorial proof that $\binom{n}{i}\binom{n-i}{j}\binom{n-i-j}{k} = \binom{n}{\ell}\binom{n-\ell}{k}\binom{n-\ell-k}{j}$

Question 8

Professor M is teaching a class with 100 distinct students $s_1,\ldots,s_{100}$. He wants to assign each student $s_i$ a set of $g_i$ homework exercises so that each student gets at least $50$ exercises and that the students get an average of $75$ exercises each. (Some may get more than 75 and some may get less, but never less than $50$). How many ways are there to do this?

image/svg+xml