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.
-
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.
Sketch of answer: In the proof of Ramsey's Theorem given in class, the first step is to argue that some vertex $v$ has three incident edges $vx$, $vy$, and $vz$ of the same colour. That's easy to do for $K_{6}$ because there are only two colours and $5$ edges incident on each vertex. In the current question we only have a $K_{5}$ so that argument doesn't work. Instead, we can use the fact that the number of blue and red edges are not the same. All we need to do is prove the following:
Claim: Some vertex $v$ of $K_5$ is incident to three edges $vx$, $vy$, and $vz$ that all have the same colour.
Proof by contradiction: Suppose the claim is not true, for the sake of contradiction. By definition, each vertex of $K_5$ is incident to $4$ edges. Since no vertex is incident to three edges of the same colour, each vertex must be incident to two red edges and two blue edges. Then, if we count the number of red edges, we get $2\cdot 5 /2 = 5$ since if we count each of the two red edges (the first two in our formula) around each of the five vertices (the five in our formula) then we count each edge exactly twice (the division by two). Counting the blue edges gives the same result, $5$. But this contradicts the statement in the question that the number of red edges and the number of blue edges are not the same. ↯
After this claim, the proof is exactly the same as the proof given in class: the triangle $xyz$ is monochromatic or one of the triangles $vxy$, $vyz$, or $vzx$ is monochromatic. -
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.
Sketch of answer: First we do what the hint suggests:
Claim: Some vertex of $K_{16}$ incident to $6$ edges of the same colour.
Proof by contradiction: We can follow the same strategy as the previous question. Each vertex of $K_{16}$ is incident to $15$ edges. If each vertex $v$ is not incident to $6$ edges of the same colour then $v$ is incident to exactly $5$ red edges, $5$ blue edges, and $5$ green edges. Counting the number of red edges in the entire $K_{16}$, we get $16\cdot 5/2=40$. We get the same answer for the number of blue edges and the number of green edges, contradicting the statement in the question that these numbers are not all equal. ↯
Let $v$ be a vertex of $K_{16}$ that is incident to $6$ edges $vx_1$, $vx_2$, $vx_3$, $vx_4$, $vx_5$ and $vx_6$ of the same colour. Without loss of generality, assume these edges are all green. If any edge $x_ix_j$ with $1\le i < j\le 6$ is green then $vx_ix_j$ is a monochromatic (green) triangle and we are done. The only other possibility is that each such edge $x_ix_j$ is coloured red or is coloured blue. But then the subgraph that contains only the vertices $x_1,\ldots,x_6$ and all the edges $x_ix_j$ for $1\le i<j\le 6$ is a $K_6$ whose edges are coloured red and blue, so the version of Ramsey's Theorem discussed in class implies that this graph contains a monochromatic (red or blue) triangle.
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
- five kinds of bourbon;
- ten kinds of scotch; and
- four kinds of beer.
-
If Pat wants to drink one bourbon, one scotch, and one beer—in that order—how many options does Pat have?
Sketch of answer: Product Rule: Pick one of each, in order. There are $5\cdot 10\cdot 4$ ways to do this. -
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.)
Sketch of answer: Product Rule: Pick the three drinks, as above, and then choose the order to drink them in. There are $5\cdot 10\cdot 4\cdot 3!$ ways to do this. -
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)
Sketch of answer: There are $5+10+4=19$ different kinds of drinks. Then there are $19$ options for Pat's first drink, $18$ for his second, and $17$ for his third, so the answer is $19\cdot 18\cdot 17$.
Note: It wasn't entirely clear from the question that order matters here. If you assume that order doesn't matter then the answer is simpler. There are only $5+10+4=19$ kinds of drinks and pat choose three different ones, so the answer is $\binom{19}{3}$. I will accept this answer if the assumptions are made clear. -
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?
Sketch of answer: Pat has $19$ options for each of his three drinks, so the answer is $19^3$.
Note: It wasn't entirely clear from the question that order matters here. If you assume that order doesn't matter then the answer is more complicated. Either- Pat drinks the same drink three times. There are $19$ ways to do this. Or
- Pat drinks two kinds of one drink and a second drink. There are $19\cdot18$ ways to do this. Or
- Pat drinks three difference kinds of drinks. There are $\binom{19}{3}$ ways to do this.
Therefore, by the Sum Rule, the answer is in this case is $19+19\cdot 18 + \binom{19}{3}$. I will accept this answer if the assumptions are made clear.
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.
-
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?
Sketch of answer: As each traveller arrives, choose which of the $3$ queues they go into. By the Product Rule, there are $3^n$ ways to do this. -
What if, when each passenger arrives at the arrival hall, they always choose a queue with the fewest number of people already in it?
Sketch of answer: When $p_1$ arrives, all queues are empty so $p_1$ has $3$ options. When $p_2$ arrives $2$ queues are empty (and the other contains $p_1$) so $p_2$ has only two options. Then $p_3$ has no choice but to go into the empty queue. We conclude that $p_1,\ldots,p_3$ have a total of $3\cdot2\cdot 1=3!$ options. After that, each of $p_4,\ldots,p_{6}$ arrives at a situation where some queues have size one and some have size $2$ and they have to choose a queue of size $1$. They have a total of $3!$ ways to do this. If $n$ is a multiple of three, then the answer is easy: $(3!)^{n/3}$. Otherwise, it's $(3!)^{\lfloor n/3\rfloor}\cdot 3!/(3-(n\bmod 3))!$. That's an ugly formula, and it only has two cases, which we could also do by hand. If $n\bmod 3=1$, then the answer is $(3!)^{(n-1)/3}\cdot 3$. If $n\bmod 3=2$ then the answer is $(3!)^{(n-2)/3}\cdot 3\cdot 2$. -
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.
Sketch of answer: The end result of this process is three ordered subsets of the $n$ passengers (the ordered list of the passengers in each of the queues, $Q_1$, $Q_2$, adn $Q_3$) that form a partition of the $n$ passengers. To generate such a thing we can first choose a permutation of the passengers in one of $n!$ ways. In this permutation, we take the first $x_1$ passengers and put them into $Q_1$, the next $x_2$ passengers and put them into $Q_2$ and the next $x_3$ passengers and put them into $Q_3$. The total number of ways choose $x_1,x_2,x_3$ is the number of solutions to $x_1+x_2+x_3=n$, which is $\binom{n+2}{2}$. So the answer is $n!\cdot\binom{n+2}{2}$. -
What if we're dealing with the English passengers again, like in question 1, but this time we require that no queue is empty?
Sketch of answer: We'll use the principle of inclusion-exclusion. The answer $3^n$, from question $1$ counts the set $S_2$ of assignments where two queues are empty and counts the set of assignments $S_1$ where exactly one queue is empty. So the answer will be $3^n-|S_1\cup S_2|$. Since $S_1$ and $S_2$ are disjoint, $|S_1\cup S_2|=|S_1|+|S_2|$, by the Sum Rule. The set $S_2$ is easy to describe: all the passengers line up in one of the three queues, in the same order they got off the plane. The only thing to decide is which queue they will line up, so $|S_2|=3$. To get an element from the set $S_1$, choose which of the three queues are empty ($3$ choices) then assign the passengers to the other two queues making sure that each gets at least one passenger. The number of ways to do this is $2^n-2$, where the ${}-2$ is needed because we need to exclude the two assignments in which all the passengers are assigned to one of the queues. So the answer is $3^n-|S_1|-|S_2|=3^n-3\cdot (2^n-2)-3=3^n-3\cdot 2^n+3$.
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$.
-
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?
Sketch of answer: This is the number of injective functions from a set of size $n$ (the dogs) onto a set of size $m$ (the cages). We've seen in class that this is $m!/(m-n)!$. -
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?
Sketch of answer: Use the product rule. First, match each white dog with a distinct black dog. There are $(n/2)!$ ways to do this. Then assign each of the resulting pairs of dogs to a distinct cage. There are $(n/2)!$ ways to do this, so the final answer is $(n/2)!\cdot (n/2)!$. -
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!)
Sketch of answer: This is like the previous question, but now it's harder to analyze the number of matchings because there aren't two different kinds of dogs. Let's try something else. First choose $n/2$ dogs and paint them white. There are $\binom{n}{n/2}$ ways to do this. Now match white dogs with black dogs and place them into cages as before. There are $(n/2)!\cdot(n/2)!$ ways to this, as before. This makes a total of $\binom{n}{n/2}\cdot(n/2)!\cdot(n/2)!$ ways to paint $n/2$ dogs white, then match each white dog with a distinct black dog, and then assign each pair to a distinct cage. To answer the original question, we notice that we could wait until the dogs are in their cages before we pick one from each cage and paint it white, and we would get the same result—an arbitrary set of $n/2$ dogs are painted white and white/black pairs are assigned to cages. Therefore, the number of ways to pair the black dogs off, put them into cages, and then paint one of each pair white is also $\binom{n}{n/2}\cdot(n/2)!\cdot(n/2)!$.
Once the dogs are in their cages, the number of ways to choose one from each pair to paint white is $2^{n/2}$, so if we skip this step, then the number of ways to assign two dogs to each cage is $\binom{n}{n/2}\cdot(n/2)!\cdot(n/2)!/2^{n/2}$.
Sketch of Second Answer: If we don't try to copy the previous approach, we can just do it directly. Choose two dogs to put into cage $c_1$ in one of $\binom{n}{2}=n(n-1)/2$ ways. Then choose two remaining dogs to put into cage $c_2$ in one of $\binom{n-2}{2}=(n-2)(n-3)$ ways. Continue like this to get the answer \[ \prod_{i=0}^{n/2-1}\binom{n-2i}{2}= \frac{n!}{2^{n/2}} \enspace . \] Is this the same answer? Yes, because \[ \binom{n}{n/2}\cdot(n/2)!\cdot(n/2)! = \frac{n!}{(n/2)!(n-n/2)!}\cdot(n/2)!\cdot(n/2)! = n! \enspace . \] -
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?
Sketch of answer: Use the Principle of Inclusion-Exclusion. The number of ways to assign dogs to cages without worrying about whether any are empty is $4^n$. Some of these assignments result in three empty cages, that we don't want to count. But three empty cages means all the dogs are assigned to one cage. Therefore are only $4$ ways to do this: Pick one of the four cages and put all the dogs in. So the answer is $4^n-4$.
Note: While you guys were doing this assignment on Sunday afternoon, I was adopting a dog from the OHS. Here's Romeo:
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.
-
Use the Product Rule to show that the number of ways we can do this is $\binom{n}{m}\binom{m}{k}$.
Sketch of answer: Choose a set $A\subseteq S$ of size $m$ in one of $\binom{n}{m}$ ways. From $A$ choose a set $R$ of $k$ elements in one of $\binom{m}{k}$ ways. Let $B:=A\setminus R$. Colour the elements in $R$ red and colour the elements in $B$ blue. The number of ways to do this is $\binom{n}{m}\cdot\binom{m}{k}$. -
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}$. Sketch of answer: Choose a set $R\subseteq S$ of size $k$ in one of $\binom{n}{k}$ ways. From $S\setminus R$ choose a set $B$ of $m-k$ element in one of $\binom{n-k}{m-k}$ ways. Colour the elements in $R$ red and colour the elements in $B$ blue. The number of ways to do this is $\binom{n}{k}\cdot\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$.
- 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}$
Sketch of answer: Count the number of rearrangements of the string $A^iB^jC^kD^\ell$ using the trick learned in class:- Approach 1: Choose $i$ locations for the letter $A$ in $\binom{n}{i}$ ways, then choose $j$ locations for $B$ in $\binom{n-i}{j}$ ways, then choose $k$ locations for $C$ in $\binom{n-i-j}{k}$ ways. The remaining $\ell$ locations are filled with $D$. There are a total of $\binom{n}{i}\binom{n-i}{j}\binom{n-i-j}{k}$ ways to do this.
- Approach 2: Choose $\ell$ locations for $D$ in $\binom{n}{\ell}$ ways, then choose $k$ locations for $C$ in $\binom{n-\ell}{k}$ ways, then choose $j$ locations for $B$ in $\binom{n-\ell-k}{j}$ ways. The remaining $i$ locations get filled with $A$. There are a total of $\binom{n}{\ell}\binom{n-\ell}{k}\binom{n-\ell-k}{j}$ ways to do this.
Both these approaches count the number of rearrangents of the string $A^iB^jC^kD^\ell$, so both these quantities are equal to each other.
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?
Sketch of answer: Since the average is $75$ and there are $100$ students, the sum of all student grades must be $7500$. Let $g_i$ be the grade assigned to student $s_i$, for each $i\in\{1,\ldots,100\}$. Therefore $\sum_{i=1}^{100} g_i = 7500$. Let $g_i'=g_i-50$, for each $i\in\{1,\ldots,100\}$. Then \[ \sum_{i=1}^{100} g_i' = \sum_{i=1}^{100} (g_i-50) = \sum_{i=1}^{100} g_i- \sum_{i=1}^{100} 50=7500-5000=2500 \enspace .
\]
So the number of ways to do this is the number of ways to choose non-negative integers $g_1',\ldots,g_{100}'$ so that $\sum_{i=1}^{100}g_i'=2500$. We've seen in class that this is exactly $\binom{2500+99}{99}=\binom{2599}{99}$.