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

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.

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.

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?

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.)

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)

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?

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?

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?

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.2 in the textbook, which is not covered until Lecture 5.

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?

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?

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.

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?

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).

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.)

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 are put into the bags?

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.