$\newcommand{\R}{\mathbb{R}}\DeclareMathOperator{\E}{\mathbf{E}}\DeclareMathOperator{\deg}{deg}\newcommand{\N}{\mathbb{N}}$

Assignment 1

In this assignment you may use any of the theorems or lemmas that we have proved in class (these are all also in the textbook).

Name and Student Number

Make sure that the PDF file you submit begins with your name and student number on the first page.
Grading (5 marks): An easy five marks just for including their name and student number at the start of the first page. Zero if they omit it. ▶

Extension of the Erdős–Rényi–Sós Friendship Theorem

We have seen in Lecture 1 (Theorem 1.1.1 in the textbook) 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. For this question you will prove something stronger.

$A lollipop, a $K_{3,3}$, and a double $3$-cycle$

Lollipops and complete bipartite graphs

A lollipop is a graph with $4$ vertices, $4$ edges, and exactly one $3$ -cycle. A $K_{3,3}$ is a graph with $6$ vertices $a_1,a_2,a_3,b_1,b_2,b_3$ that contains the edge $a_ib_j$ for each $i,j\in\{1,2,3\}$ . Prove that if we colour the edges of the complete graph $K_6$ using two colours, then there will always be a monochromatic lollipop or a monochromatic $K_{3,3}$ .

Examples for Question 2.1

Hint: Since we already proved this in class (Theorem 1.1.1 in the textbook), you can start by assuming that the graph contains a monochromatic triangle $a_1a_2a_3$ and work from there.

Solution: Using the hint we assume that our graph contains a monochromatic $3$ -cycle $a_1a_2a_3$ . Without loss of generality, we can assume that the edges $a_1a_2$ , $a_2a_3$ , and $a_3a_1$ are blue. Call the other vertices of the graph $b_1$ , $b_2$ , and $b_3$ . If some edge $a_ib_j$ is blue for some $i,j\in\{1,2,3\}$ , then the edges $a_1a_2$ , $a_2a_3$ , $a_3a_1$ , and $a_ib_j$ form a blue lollipop and we are done. The only other possibility is that $a_ib_j$ is red for each $i,j\in\{1,2,3\}$ . But in this case, these $9$ edges form a red $K_{3,3}$ . ∎

Grading (5 marks): This is an open-ended question and there are lots of possible proofs. They don't have to use the hint. $5$ marks for a complete and correct proof. $3$ – $4$ marks for a proof that is mostly correct but might have missed some details. $0$ – $2$ marks for a proof that is incorrect. ▶

Lollipops and double $3$ -cycles

A double $3$ -cycle is a graph with $6$ vertices and $6$ edges that form two vertex-disjoint $3$ -cycles. Prove that if we colour the edges of the complete graph $K_6$ using two colours, then there will always be a monochromatic lollipop or a monochromatic double $3$ -cycle.

Examples for Question 2.2

Hint: This builds on the proof you have found when answering the previous question.

Solution: In solving the the previous question we showed that we have a blue lollipop on the vertices $a_1,a_2,a_3,b_j$ or we have partition of the vertices into two sets $A:=\{a_1,a_2,a_3\}$ and $B:=\{b_1,b_2,b_3\}$ where $a_1a_2a_3$ is a blue $3$ -cycle and the edges between $A$ and $B$ form a red $K_{3,3}$ . In the former case, there is nothing more to prove since we have a blue lollipop. In the latter case, consider the edges of the $3$ -cycle $b_1b_2b_3$ . There are two cases to consider:

Each of the edges $b_1b_2$ , $b_2b_3$ , and $b_3b_1$ is blue. In this case we have a blue double $3$ -cycle since $a_1a_2a_3$ is a blue $3$ -cycle, $b_1b_2b_3$ is also a blue $3$ -cycle, and the sets $A$ and $B$ are disjoint.
At least one of the edges $b_1b_2$ , $b_2b_3$ , and $b_3b_1$ is red. Without loss of generality, suppose $b_1b_2$ is red. In this case, the edges $b_1a_1$ , $a_1b_2$ , $b_1b_2$ and $b_1a_2$ form a red lollipop. ∎

What, no Sticky Fingers?

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

Pat is going to the Rolling Stones concert. To get him in the mood, he wants to listen to three tracks from the 'Stones three best albums:

Album 1: Exile on Main St. (1972) has 18 songs on it;
Album 2: Some Girls (1978) has 10 songs on it; and
Album 3: Aftermath (1966) has 11 songs on it.

One song from each, in order

If Pat wants to listen to one song from Album 1, one song from Album 2, and one song from Album 3—in that order—how many options does Pat have?

Solution: This is an easy application of the Product Rule: Pat has $18$ choices for the first song, $10$ choices for the second song, and $11$ choices for the third song, so the answer is $18\times 10\times 11$ . ∎

Grading (5 marks): $5$ for a correct answer with a little explanation. $4$ for a correct answer with no explanation. $0$ for an incorrect answer. ▶

One song from each, in any order

If Pat wants to listen to one song from Album 1, one song from Album 2, and one song from Album 3—not necessarily in that order—how many options does Pat have? (Listening to the same three songs in different orders counts as two different options.)

Solution: Pat can first choose the three songs in one of $18\times 10\times 11$ ways and then choose which order to listen to these songs to in one of $3!$ ways, for a total of $18\times 10\times 11\times 3!$ possibilities. ∎

Grading (5 marks): $5$ for a correct answer with a little explanation. $4$ for a correct answer with no explanation. $0$ for an incorrect answer. There's more than one correct way to come up with or explain this answer, so use your judgement. ▶

Three different songs

If Pat just wants to listen to three different songs then how many options does he have? (For example, he might listen to three songs from Album 2)

Solution: There are a total of $18+10+11=39$ songs on these three albums. Pat has $39$ choices for his first song, $38$ for his second, and $37$ for his third, for a total of $39\times 38\times 37$ options. ∎

Three songs

If Pat just wants to listen to three songs and doesn't mind hearing the same song twice, or even three times, then how many options does he have?

Solution: Pat has 39 options for each of the three songs he listens to, so he has $39\times39\times39=39^3$ options in total. ∎

Grading (5 marks): $5$ for a correct answer with a little explanation. $4$ for a correct answer with no explanation. $0$ for an incorrect answer. There's more than one way correct way to come up with or explain this answer, so use your judgement. ▶

Kids buying food

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

A group of $n$ distinct kids $k_1,\ldots,k_n$ arrive at the amusement park and head straight for the food court. There are four options for food: one pizza stand, one taco stand, one hamburger stand, and one cotton-candy stand. Since it's only 9am no one is working at these stands, but each kid chooses their favourite food and joins the queue at their chosen stand.

For each of the following questions we care about which kids are in which queues and what the order of the kids within each queue is.

Well-behaved kids

Suppose there was only one gate at the amusement park and the kids came through the gate in the order $k_1,\ldots,k_n$ . The kids walk calmly through the park from the gate to the food court and arrive in the same order they came through the gate. In this way, their order within each of the four queues matches the order they got off the plane. How many ways are there to assign the kids to queues?

Solution: When each kid arrives, they choose one of the $4$ queues to choose from, so there are $4^n$ options for assigning the kids to queues. ∎

Grading (5 marks): $5$ for a correct answer with a clear explanation. $4$ for a correct answer with an unclear explanation. $3$ for a correct answer with no explanation. $0-2$ for an incorrect answer. There's more than one way correct way to come up with or explain this answer, so use your judgement. ▶

Well-behaved impatient kids

What if, when each kids arrives at the food court, they always choose a queue with the fewest number of kids already in it?

Solution: Here the kids arrive in rounds of four kids each. For each round $i\in\{0,\ldots,\lfloor n/4\rfloor-1\}$ , in round $i$ , $k_{4i+1}$ sees four queues each having $i$ kids in it, so has four choices. Then $k_{4i+2}$ sees three queues with $i$ kids and one queue with $i+1$ kids so only has three options. Similarly, $k_{4i+3}$ only has two options, and $k_{4i+4}$ is forced to join the only queue of length $i$ so only has one option. Thus, each group of four kids has $4\times 3\times 2\times 1=4!$ options. If $n$ is a multiple of $4$ , then the answer is $(4!)^{n/4}$ . Otherwise, the last group is a little bit different. There are $(4!)^{\lfloor n/4\rfloor}$ options for the first $\lfloor n/4\rfloor$ groups, and the final group has $4!/(4-n\bmod 4)!$ options. This gives a total of $(4!)^{\lfloor n/4\rfloor}\times 4!/(4-n\bmod 4)!$ ∎

Grading (5 marks): $5$ for a correct and complete answer with a clear explanation that deals with the case where $n$ is not a multiple of $4$ . $3$ – $4$ for any answer of the form $(4!)^{n/4}$ , even if it's not quite correct when $n$ is not divisible by $4$ . $0-2$ for an incorrect answer. There's more than one way correct way to come up with or explain this answer, so use your judgement. ▶

Little savages

What if the kids are really hungry, all break through the gate together, and race each down to the food court, so they don't necessarily join the queues in the order they arrived at the park gates? Since they're racing, they don't have time to choose the shortest queue, so they pick one arbitrarily.

Hint: The easiest solution to this question uses Theorem 3.9.1 in the textbook, which is not covered until Lecture 5.

Quick Solution: At least one student has noticed that this question is equivalent to the problem of placing $m$ books on a set of $n$ shelves (Theorem 3.1.4 in the textbook), which can be solved with a clever application of the Product Rule. In this case we are placing $n$ kids (books) onto $4$ queues (shelves). Students should be given full marks if they explain this clearly or if they adapt the proof technique used to prove Theorem 3.1.4.

Solution: This is a trickier question, and there are lots of ways to go wrong. The final outcome of this process is an assignment of kids to each of the four food stalls and four permutations, one for the kids assigned to each stall.

The easiest way to count this is to first decide how many kids go to each of the queues. The number of ways to do this is the number of non-negative integer solutions to $x_1+x_2+x_3+x_4=n$ . In one of our Lecture 5, we have seen Theorem 3.9.1, which shows that the number of solutions to this equation in $\binom{n+3}{3}$ . Next we choose one of the $n!$ permutations $\pi$ of the $n$ kids and send the first $x_1$ kids in $\pi$ to the first food stall in the same order they appear in $\pi$ . Then we send the next $x_2$ kids in $\pi$ to the second food stall in the same order they appear in $\pi$ , and so on. It's easy to check that if we change the permutation or the values of $x_1,x_2,x_3,x_4$ then we finish with a different outcome. It's also easy to check that for any outcome we can count the number of kids in each queue to get a solution to $x_1+\cdots+x_4=n$ and construct the permutation $\pi$ by concatenating the four queues. So there is a bijection between executions of this two step procedure and possible outcomes. So the total number of possible outcomes is $\binom{n+3}{3}n!$ . ∎

Grading (5 marks): $5$ for a correct and complete answer with a clear explanation. $3$ – $4$ for a correct answer with an unclear explanation. $0-2$ for an incorrect answer. There's more than one way correct way to come up with or explain this answer, so use your judgement. ▶

Students writing exams

Each of the following questions can be answered using the rules (Bijection, Complement, Sum, or Inclusion-Exclusion) introduced in Lecture 3.

$100$ COMP2804 students $c_1,\ldots,c_{100}$ and $100$ different PSYC1000 students $p_1,\ldots,p_{100}$ are writing an exam. (All students are distinct, even if they are writing the same exam.)

Plenty of desks

Suppose the student are writing their exam in a room with $m\ge 200$ distinct desks $d_1,\ldots,d_m$ . How many ways are there to assign the students to desks so that each student gets their own desk?

Solution: This the number of injective functions from a set of size $200$ onto a set of size $m\ge 200$ . We've seen in Lecture 2 (Theorem 3.1.3 in the textbook) that the number of such functions is $m!/(m-200)!$ . ∎

A shortage of desks, avoiding cheating

Suppose the exam room has exactly $100$ distinct standing desks $d_1,\ldots,d_{100}$ and no chairs. How many ways are there to assign students to desks so that each desk has exactly one COMP2804 student and exactly one PSYC1000 student?

Solution: This is an application of the Product Rule. First assign each COMP student a distinct desk. There are $100!$ ways to do this (This is the number of permutations of students and is also a special case of Theorem 3.1.3 in the textbook). Then do the same for each PSYC student. There are $100!$ ways to do this, so the answer is $(100!)^2$ . ∎

A shortage of desks, avoiding distractions

Like the previous question, suppose the exam room has exactly $100$ distinct standing desks $d_1,\ldots,d_{100}$ and no chairs. How many ways are there to assign the COMP2804 students to desks $d_1,\ldots,d_{50}$ and the PSYCH1000 students to desks $d_{51},\ldots,d_{100}$ so that each desk has exactly two students at it.

Solution: We can do the COMP students first and then the PSYC students. Start by choosing two COMP students and assign them to desk $d_1$ . There are $\binom{100}{2}$ ways to do this. From the remaining $98$ COMP students, choose $2$ and assign them to desk $d_2$ . There are $\binom{98}{2}$ ways to do this. Continue this way and finish by assigning the last two COMP students to desk $d_{50}$ . There are $\binom{2}{2}$ ways to do this. By the Product Rule, the number of ways to do these 50 steps is $\prod_{i=0}^{49}\binom{100-2i}{2} = \left(\frac{100\times 99}{2}\right)\left(\frac{98\times 97}{2}\right)\cdots\left(\frac{4\times 3}{2}\right)\left(\frac{2\times 1}{2}\right) = \frac{100!}{2^{50}}$ Exactly the same argument shows that the number of ways of assigning PSYC students to desks $d_{51},\ldots,d_{100}$ is $100!/2^{50}$ . Therefore, by the Product Rule, the number of ways of assigning all students to desks is $(100!/2^{50})^2=(100!)^2/2^{100}$ . ∎

Grading (5 marks): $5$ for a correct and complete answer with a clear explanation. $3$ – $4$ for a correct answer with an unclear explanation or an answer that correctly figured out how to assign COMP students to desks $d_1,\ldots,d_{50}$ but forgot to do the second step of squaring the answer. $0-2$ for an incorrect answer. There's more than one way correct way to come up with or explain this answer, so use your judgement. ▶

Only three desks

Suppose the exam room has three really large tables, $t_1,t_2,t_3$ , each of which can easily accommodate $200$ students. How many ways are there to assign students to these tables so that each table is assigned at least one student?

Solution: For this, we will use the Complement Rule to first count solutions in which at least one of the tables is empty. The number of ways of assigning students so that they all sit at one table (leaving two tables empty) is $3$ ; you just choose the table. The number of ways of assigning students so that exactly one table is empty can be computed using the Product Rule. First choose one of the $3$ tables that will be empty. There are $3$ ways to do this. Next, assign the students to the other two tables so that neither of those is empty. The number of ways to do this is $2^n-2$ since, of the $2^n$ possible assignments of students to tables, the two assignments that have all students sitting at a single table are not allowed. Therefore, the number of assignments in which at least one table is empty is $3 + 3\times (2^n-2) = 3\times 2^{n} - 3$ Now we use the Complement Rule. The number of ways to assign students to tables without any restrictions is $3^n$ . Therefore, the number of ways to assign students to tables in such a way that no table is empty is $3^n - (3\times 2^{n} - 3) = 3^n - 3\times 2^n + 3$ . ∎

Grading (5 marks): $5$ for a correct and complete answer with a clear explanation. $3$ – $4$ for a mostly correct answer that has a small calculation error. $0-2$ for an incorrect answer. There's more than one way correct way to come up with or explain this answer, so use your judgement. ▶

Proving a binomial identity

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 $S$ be a set of $n$ elements. Let $S_0$ be the set of all subsets of $S$ that have even size. Let $S_1$ be the set of all subsets of $S$ that have odd size.

Finding a bijection

Define a bijection $f:S_0\to S_1$ between $S_0$ and $S_1$ . You must prove that whatever function you define is a one-to-one (injective) and onto (surjective).

Solution: Let $x$ be any element of $S$ . Consider the function $f(X) = \begin{cases} X\setminus\{x\} & \text{if $x\in S$} \\ X\cup\{x\} & \text{if $x\not\in S$} \end{cases}$ Notice that for any $X\in S_0$ , $f(X)\in S_1$ since $|f(X)|=|X|+1$ or $|f(X)|=|X|-1$ . By the same reasoning, for any $Y\in S_1$ , $f(Y)\in S_0$ . Finally, notice that $f(f(X))=X$ for any $X\subseteq S$ . Therefore $f:S_0\to S_1$ is onto because for any $Y\in S_1$ , there is an element $X=f(Y)$ in $S_0$ such that $f(X)=Y$ . Furthermore $f:S_0\to S_1$ is injective because if, for some $X_1,X_2\in S_0$ , $f(X_1)=f(X_2)$ then $X_1=f(f(X_1))=f(f(X_2))=X_2$ . ∎

Grading (5 marks): There are many possible bijections. $5$ for a correct and complete answer with a clear explanation which shows that the function is one-to-one (injective) and onto (surjective). $3$ – $4$ for a mostly correct answer that misses one of those steps or is unclear. $0-2$ for an incorrect answer. ▶

A binomial identity

Prove that $\sum_{k=0}^n (-1)^k\binom{n}{k} = 0$ . (You may use the result from the previous question even if you weren't able to find the bijection.)

Quick Solution: At least one student has noticed that this identity is an easy consequence of Newton's Binomial Theorem with $x=1$ and $y=-1$ , since $0 = 0^n = (1+(-1))^n = \sum_{k=0}^{n}1^{n-k}(-1)^k\binom{n}{k} = \sum_{k=0}^{n}(-1)^k\binom{n}{k} \enspace .$ A student who gives this solution should receive full marks.

Solution: Since $-1^k=1$ when $k$ is even and $-1^k=-1$ when $k$ is odd, we can rewrite $\sum_{k=0}^n (-1)^k\binom{n}{k}$ as $\sum_{k=0}^n (-1)^k\binom{n}{k} = \sum_{k=0}^{\lfloor n/2\rfloor} \binom{n}{2k} - \sum_{k=0}^{\lfloor (n-1)/2\rfloor} \binom{n}{2k+1}$ By the Sum Rule, $\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n}{2k}$ is the number of ways of choosing a subset of $S$ that contains an even number of elements, so $\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n}{2k}=|S_0|$ . By the same reasoning, $\sum_{k=0}^{\lfloor (n-1)/2\rfloor} \binom{n}{2k+1}=|S_1|$ . By the previous question, $|S_0|=|S_1|$ by the Bijection Rule. Therefore, $\sum_{k=0}^n (-1)^k\binom{n}{k} = \sum_{k=0}^{\lfloor n/2\rfloor} \binom{n}{2k} - \sum_{k=0}^{\lfloor (n-1)/2\rfloor} \binom{n}{2k+1} = |S_0|-|S_1| = 0 \enspace .$ ∎

Grading (5 marks): They just need to realize that the sum has a negative part and a positive part, and that these count odd and even-sized subsets. Without realizing that, they're doomed. $5$ for a correct and complete answer with a clear explanation. $3$ – $4$ for a mostly correct answer that is unclear. $0-2$ for an incorrect answer. ▶

Making loot bags

Professor M needs to make $10$ loot bags $b_1,\ldots,b_{10}$ for his son's birthday party. Each loot bag has the name of one of his son's friends on it and Professor M has $80$ identical pieces of candy. The candy is not very good so he doesn't want any leftover for himself. He cares a bit about being fair, but not enough to bother counting 8 pieces of can for each bag. It's good enough if each bag contains at least $3$ pieces of candy. How many ways are there for Professor~M to distribute the candy among the loot bags so that each bag has at least three pieces of candy and all $80$ pieces of candy is put into the bags.

Solution: The professor wants to solve the equation $\sum_{i=1}^{10} x_i = 80$ with integer valued $x_i$ with each $x_i\ge 3$ . Define $y_i = x_i-3$ , so that the constraint $x_i\ge 3$ is equivalent to $y_i\ge 0$ . Then this equation becomes $\sum_{i=1}^{10} (y_i+3) = 80$ , which we can rewrite as $\sum_{i=1}^{10} y_i = 50$ . The number of ways to solve this equation with non-negative integers $y_1,\ldots,y_{10}$ is $\binom{50+9}{9}=\binom{59}{9}$ , by Theorem 3.9.1 in the textbook.

A mysterious function

Consider the following Python function:

def f(x,y):
    if y == 0: return 1
    s = 0
    while x > y:
        s = s + f(x-1, y-1)
        x = x - 1
    return s + 1

If $x$ and $y$ are two non-negative integers with $x\ge y$ , what does $f(x,y)$ return? Explain your answer using one of the theorems discussed in class.

Solution: This function returns $\binom{x}{y}$ . The base case $\binom{x}{0}=1$ is handled by the first line. If $x=y$ then the while loop doesn't execute and the function returns $1$ , correctly, since $\binom{x}{x}=1$ . Otherwise, the function computes $f(x-1,y-1)$ (recursively) and then reduces $x$ by $1$ and returns to the top of the loop so that the remainder of the code computes $f(x-1,y)$ . This implements Pascal's Identity $\binom{x}{y} = \binom{x-1}{y-1}+\binom{x-1}{y}$ (Theorem 3.7.2 in the textbook).

Grading (5 marks): There's no excuse for not figuring out that $f(x,y)=\binom{x}{y}$ for $x\ge y\ge 0$ . They can run the code. $5$ for a correct and complete answer with a clear explanation that references Pascal's Formula. $3$ – $4$ for a mostly correct answer that is unclear. $0-2$ for an incorrect answer. ▶

As­sign­ment 1

Name and Stu­dent Num­ber

Ex­ten­sion of the Erdős–Rényi–Sós Friend­ship The­o­rem

Lol­lipops and com­plete bi­par­tite graphs

Lol­lipops and dou­ble 33-cy­cles

What, no Sticky Fin­gers?

One song from each, in order

One song from each, in any order

Three dif­fer­ent songs

Three songs

Kids buy­ing food

Well-be­haved kids

Well-be­haved im­pa­tient kids

Lit­tle sav­ages

Stu­dents writ­ing exams