$\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:

   

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:

• a clique of size $s$ whose edges are all red; or
• a clique of size $t$ whose edges are all blue.

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.

Answer 1

1. The statement $R(s,2)=s$, in English, is just the following statement: If we colour the edges of $K_s$ red and blue, then there is a blue edge (a blue $K_2$) or all the edges of $K_s$ are red (a red $K_s$). Obviously if we don't have any blue edges, then all the edges are red.

2. Let $n= R(s-1,t) + R(s, t-1)$ and consider some red/blue colouring of $K_n$. Pick your favourite vertex $v$ of $K_n$. The vertex $v$ is the endpoint of $n-1$ edges of $K_n$. Define $r$ as the number of these edges that are coloured red and $b$ as the number of these edges that are coloured blue, so $r+b=n-1$. It cannot be the case $r<R(s-1,t)$ and $b<R(s,t-1)$ since this would imply that $r\le R(s-1,t)-1$ and $b\le R(s,t-1)-1$, so $r+b \le n-2 < n-1=r+b$. Therefore $r\ge R(s-1,t)$ or $b\ge R(s,t-1)$, which gives us two cases to consider:

   1. If $r\ge R(s-1,t)$ then consider the subgraph $K_r$ of $K_n$ that contains all the $r$ neighbours of $v$ that share a red edge with $v$. Since $r\ge R(s-1,t)$, at least one of the following cases occurs:
      • $K_r$ contains a clique $K_{s-1}$ whose edges are all red. In this case, the clique formed by $v$ and the vertices of $K_{s-1}$ is a clique of size $s$ whose edges are all red.
      • $K_r$ contains a clique $K_t$ whose edges are all blue. In this case there is nothing to do.
   2. If $b\ge R(s,t-1)$ then we proceed exactly the same way, but reversing the roles of red and blue and reversing the roles of $s$ and $t$.

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":

• Nine roller coasters
• Seven carnival rides
• Five water slides

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?

Answer 3

1. The procedure Pat can use is the following
   • Pick one of the $9$ roller coasters
   • Pick one of the $5$ water slides
   • Pick one of the $7$ carnival rides By the Product Rule, there are $9\times 5\times 7=315$ ways to execute this procedure, each one gives a different result and, for any triple $(a,b,c)$ of roller coaster/water slide/carnival ride there is an execution of the procedure that produces the result $(a,b,c)$. Therefore Pat has $315$ options.
2. This is similar to the previous question, and order matters, so now Pat has $9^2$ options for the two roller coasters, $5^2$ options for the two water slides and $7^2$ options for the two carnival rides. By the Product Rule, this gives $9^2\times 5^2\times 7^2=99225$ options for Pat.
3. This is similar to the previous question except that Pat doesn't want to ride the same ride twice, so he only has $8$ options for this second roller coaster ride, $4$ options for his second water slide, and $6$ options for his second carnival ride. The number of options Pat has is therefore $9\times 8\times 5\times 4\times 7\times 6=60480$.
4. Pat can do this using a $20$ step procedure. In the first step, Pat can ride any roller coaster so he has $9$ options. In each of the $19$ subsequent steps, Pat can ride any roller coaster except for the one he chose in the previous step, so Pat has $8$ options. Therefore, by the Product Rule, there are $9\times 8^{19}=1297036692682702848$ options for Pat to take $20$ roller coaster rides without riding the same roller coaster twice in a row.

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?

Answer 4

1. This is an application of the Product Rule. For each element in $x\in S$ we pick one of the four sets $X$, $Y$, $Z$, or $W$ and place $x$ in that set. This an $n$ step procedure with four options at each step, so there $4^n$ ways to execute this procedure. Each execution gives a different result and each result can be obtained from some execution. (Alternatively you could observe that what we are counting here is the number of functions $f:S\to\{X,Y,Z,W\}$ from a set of size $n$ onto a set of size $4$. We counted these in class.)
2. This is another application of the Product Rule. For each $x\in S$ we still have four options: We can put $x$ in $X$, $Y$, or $Z$; or we can put $x$ in none of the sets. So the answer again is $4^n$.
3. This time, we have $7$ options for each $x\in S$: Each of the $7$ proper subsets of $\{X,Y,Z\}$. Each $x\in S$ could be placed in any of these $\{\},\{X\},\{Y\},\{Z\}, \{X,Y\}, \{X,Z\}, \{Y,Z\}\}$. So the answer here is $7^n$.

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?

Answer 5

1. This is just like placing $n$ numbers into four different sets; just calls the people $\{1,\ldots,n\}$ and call the rooms $X$, $Y$, $Z$, and $W$. So by the Bijection Rule and Question 4.1, the answer is $4^n$.
2. Here we can use the Complement Rule. The only way to avoid having at least two non-empty rooms is to put all the people into one room. There are only $4$ ways to do this (pick one of the four rooms and put everyone in it). So, by the Complement Rule, the answer is $4^n-4$.
3. We can solve this one with the Product Rule. Pick one of the two rooms (2 options) and then pick three of the people ($\binom{n}{3}$ options). Now place the three chosen people into the chosen room and place the $n-3$ other people into the other room. This gives the answer $2\times\binom{n}{3}$.
4. Here we can use principle of inclusion-exclusion. Call the rooms $A$, $B$, and $C$. We're in computing the size of the union of three sets:
5. $S_A$ is the set of assignments where $A$ has exactly three people in it;
6. $S_B$ is the set of assignments where $B$ has exactly three people in it; and
7. $S_C$ is the set of assignments where $C$ has exactly three people in it. We want to compute $|S_A\cup S_B\cup S_C|$. The inclusion-exclusion formula for this is \[ |S_A| + |S_B| + |S_C| - |S_A\cap S_B| - |S_B\cap S_C| - |S_A\cap S_C| + |S_A\cap S_C\cap S_C| \] The last term in this sum is $|S_A\cap S_C\cap S_C|=0$ because we have $n\ge 10$ people, so (by the pigeonhole principle) at least one of the rooms has at least $\lceil 10/3\rceil=4$ people in it. Furthermore, the situation is symmetric for $A$, $B$, and $C$, so we can simplify this to: \[ 3\cdot |S_A| - 3\cdot |S_A\cap S_B| \] We can compute $|S_A|$ using the Product Rule: Pick $3$ people to put in room $A$ and then place the remaining $n-3$ people in rooms $B$ and $C$. There are $\binom{n}{3}$ ways to do the first step and $2^{n-3}$ ways to do the second step, so $|S_A|=\binom{n}{3}\cdot 2^{n-3}$.

We can also compute $|S_A\cap S_B|$ using the Product Rule: Pick $3$ of the $n$ people to put in room $A$, pick $3$ of the remaining $n-3$ people to put in room $B$, and put everyone else in Room $C$. By the Product Rule, there are $\binom{n}{3}\cdot\binom{n-3}{3}$ ways to do this, so $|S_A\cap S_B|=\binom{n}{3}\cdot\binom{n-3}{3}$.

Plugging that back into the formula above, we get \[ |S_A\cup S_B\cup S_C| = 3\binom{n}{3}\cdot 2^{n-3} - 3\binom{n}{3}\cdot\binom{n-3}{3} \]

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}$.

Answer 6

1. $|A|=c^n$. In Lecture 2 we counted the number of functions from a set of size $n$ to a set of $m$ and saw that it was $m^n$. (In this case $m=c$.)
2. Here's another way to count $|A|$. For each $k\in\{0,\ldots,n\}$, let $A_k$ be the set of all ways to colour an $n$-element set so that there are exactly $k$ elements with colour $c$. We can use the Product Rule to compute $|A_k|$ using the following procedure: Pick $k$ elements of the set and colour them $c$. Colour the remaining $n-k$ elements using colours $\{1,\ldots,c-1\}$. There are $\binom{n}{k}$ ways to execute the first step and there are $(c-1)^{n-k}$ ways to execute the second step, so $|A_k|=\binom{n}{k}\cdot(c-1)^{n-k}$.
   Now, by the Sum Rule \[ |A|= \sum_{k'=0}^n |A_{k'}| = \sum_{k'=0}^n (c-1)^{n-k'}\binom{n}{k'} \enspace . \] Now, the right hand side is not exactly what we want, but we can use the fact that $\binom{n}{k'}=\binom{n}{n-k'}$ to get \[ |A|= \sum_{k'=0}^n (c-1)^{n-k'}\binom{n}{n-k'} \enspace . \] Still not exactly what we want but that's just because we're counting backward. Define $k=n-k'$ and the sum becomes: \[ |A|= \sum_{k=0}^n (c-1)^{k}\binom{n}{k} \enspace . \]

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 \binom{5}{2}$
2. $\binom{10}{2}\cdot\binom{8}{2} = \binom{10}{6}\cdot \binom{4}{2}$

Answer 7

In Lecture 5 we counted the number of ways to rearrange the string "SUCCESS" using the Product Rule and saw that we could get different looking answers if we used procedures that were slightly different. That's what's happening with these two questions and the strings we need to look at are "TENNESSEE" and "DAPPLEDOWN"

1. The number of rearrangements of "TENNESSEE" is $9\cdot\binom{8}{4}\cdot\binom{4}{2}$ if we start by placing the T ($\binom{9}{1}=9$ options), then placing the four E's ($\binom{8}{4}$ options) then placing the two $N$'s ($\binom{4}{2}$ options) and then we can only place the two S's in the two remaining positions ($1$ option).
   On the other hand, the number of rearrangments of "TENNESEE" is also $\binom{9}{2}\cdot\binom{7}{2}\cdot 5$ if we start by placing the two S's ($\binom{9}{2}$ options) then the two N's ($\binom{7}{2}$ options), then the four E's ($\binom{5}{4}=\binom{5}{1}=5$ options) and then we can only put T in the remaining position ($1$ option).
   Since these two formulas each count the same thing, they must be equal.
2. The number of rearrangements of the string "DAPPLEDOWN" is $\binom{10}{2}\cdot\binom{8}{2}\cdot 6!$ if we start by placing the two D's ($\binom{10}{2}$ options), then the two P's ($\binom{8}{2}$ options), and then the remaining $6$ letters A, L, E, O, W, and N ($6!$ options).
   The number of rearrangements of the string "DAPPLEDOWN" is also $\binom{10}{6}\cdot 6!\cdot \binom{4}{2}$ if we start by choosing the six locations for A, L, E, O, W, and N ($\binom{10}{6}$ options), then placing A, L, E, O, W, and N in those $6$ locations ($6!$ options), then placing the two P's ($\binom{4}{2}$ options), and then we can only put the remaining two D's in the remaining two locations ($1$ option). Therefore, \[ \binom{10}{2}\cdot\binom{8}{2}\cdot 6! = \binom{10}{6}\cdot 6!\cdot \binom{4}{2} \] and removing the common factor $6!$ from both sides gives us what we want.

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?

Answer 8

For each $i\in\{1,\ldots,20\}$, let $y_i$ be the number of pieces of candy I gave to child $i$ and let $x_i=y_i-3$. Since I gave out $100$ pieces of candy, $\sum_{i=1}^{20} y_i = 100$, so $\sum_{i=1}^{20} x_i = \sum_{i=1}^{20} (y_i-3) = 100 - 60 = 40$. Since each kid got at least $3$ pieces of candy, $x_i\ge 0$ for each $i\in\{1,\ldots,20\}$. Therefore, the number of ways I could have given out candy to these kids is the number of solutions to \[ x_1 + x_2 + \cdots + x_{20} = 40 \] where each $x_i$ is a non-negative integer. We saw in Lecture 5, that this is \[ \binom{40+19}{19} = \binom{59}{19} = 1397281501935165 \]