As­sign­ment 1

In this as­sign­ment you may use any of the the­o­rems or lem­mas that we have proved in class (these are all also in the text­book).

Name and Stu­dent Num­ber

Make sure that the PDF file you sub­mit be­gins with your name and stu­dent num­ber on the first page.

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

We have seen in Lec­ture 1 (The­o­rem 1.1.1 in the text­book) that if we colour the edges of the com­plete graph $K_6$ on six ver­tices using two colours, then there will al­ways be a mono­chro­matic tri­an­gle; a cycle of length $3$ whose edges all have the same colour. For this ques­tion you will prove some­thing stronger.

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

A lol­lipop is a graph with $4$ ver­tices, $4$ edges, and ex­actly one $3$-cycle. A $K_{3,3}$ is a graph with $6$ ver­tices $a_1,a_2,a_3,b_1,b_2,b_3$ that con­tains the edge $a_ib_j$ for each $i,j\in\{1,2,3\}$. Prove that if we colour the edges of the com­plete graph $K_6$ using two colours, then there will al­ways be a mono­chro­matic lol­lipop or a mono­chro­matic $K_{3,3}$.

Hint: Since we al­ready proved this in class (The­o­rem 1.1.1 in the text­book), you can start by as­sum­ing that the graph con­tains a mono­chro­matic tri­an­gle $a_1a_2a_3$ and work from there.

Lol­lipops and dou­ble $3$-cy­cles

A dou­ble $3$-cycle is a graph with $6$ ver­tices and $6$ edges that form two ver­tex-dis­joint $3$-cy­cles. Prove that if we colour the edges of the com­plete graph $K_6$ using two colours, then there will al­ways be a mono­chro­matic lol­lipop or a mono­chro­matic dou­ble $3$-cycle.

Hint: This builds on the proof you have found when an­swer­ing the pre­vi­ous ques­tion.

What, no Sticky Fin­gers?

Be­fore at­tempt­ing this ques­tion, make sure that you've watched Lec­ture 2 on the Prod­uct Rule.

Pat is going to the Rolling Stones con­cert. To get him in the mood, he wants to lis­ten to three tracks from the 'Stones three best al­bums:

• 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: Af­ter­math (1966) has 11 songs on it.

One song from each, in order

If Pat wants to lis­ten to one song from Album 1, one song from Album 2, and one song from Album 3—in that order—how many op­tions does Pat have?

One song from each, in any order

If Pat wants to lis­ten to one song from Album 1, one song from Album 2, and one song from Album 3—not nec­es­sar­ily in that order—how many op­tions does Pat have? (Lis­ten­ing to the same three songs in dif­fer­ent or­ders counts as two dif­fer­ent op­tions.)

Three dif­fer­ent songs

If Pat just wants to lis­ten to three dif­fer­ent songs then how many op­tions does he have? (For ex­am­ple, he might lis­ten to three songs from Album 2)

Three songs

If Pat just wants to lis­ten to three songs and doesn't mind hear­ing the same song twice, or even three times, then how many op­tions does he have?

Kids buy­ing food

Use the Prod­uct Rule (Lec­ture 2) to an­swer the first three of these ques­tions (the last one may need some­thing extra).

A group of $n$ dis­tinct kids $k_1,\ldots,k_n$ ar­rive at the amuse­ment park and head straight for the food court. There are four op­tions for food: one pizza stand, one taco stand, one ham­burger stand, and one cot­ton-candy stand. Since it's only 9am no one is work­ing at these stands, but each kid chooses their favourite food and joins the queue at their cho­sen stand.

For each of the fol­low­ing ques­tions we care about which kids are in which queues and what the order of the kids within each queue is.

Well-be­haved kids

Sup­pose there was only one gate at the amuse­ment 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 ar­rive 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 as­sign the kids to queues?

Well-be­haved im­pa­tient kids

What if, when each kids ar­rives at the food court, they al­ways choose a queue with the fewest num­ber of kids al­ready in it?

Lit­tle sav­ages

What if the kids are re­ally hun­gry, all break through the gate to­gether, and race each down to the food court, so they don't nec­es­sar­ily join the queues in the order they ar­rived at the park gates? Since they're rac­ing, they don't have time to choose the short­est queue, so they pick one ar­bi­trar­ily.

Hint: The eas­i­est so­lu­tion to this ques­tion uses The­o­rem 3.9.2 in the text­book, which is not cov­ered until Lec­ture 5.

Stu­dents writ­ing exams

Each of the fol­low­ing ques­tions can be an­swered using the rules (Bi­jec­tion, Com­ple­ment, Sum, or In­clu­sion-Ex­clu­sion) in­tro­duced in Lec­ture 3.

$100$ COM­P2804 stu­dents $c_1,\ldots,c_{100}$ and $100$ dif­fer­ent PSY­C1000 stu­dents $p_1,\ldots,p_{100}$ are writ­ing an exam. (All stu­dents are dis­tinct, even if they are writ­ing the same exam.)

Plenty of desks

Sup­pose the stu­dent are writ­ing their exam in a room with $m\ge 200$ dis­tinct desks $d_1,\ldots,d_m$. How many ways are there to as­sign the stu­dents to desks so that each stu­dent gets their own desk?

A short­age of desks, avoid­ing cheat­ing

Sup­pose the exam room has ex­actly $100$ dis­tinct stand­ing desks $d_1,\ldots,d_{100}$ and no chairs. How many ways are there to as­sign stu­dents to desks so that each desk has ex­actly one COM­P2804 stu­dent and ex­actly one PSY­C1000 stu­dent?

A short­age of desks, avoid­ing dis­trac­tions

Like the pre­vi­ous ques­tion, sup­pose the exam room has ex­actly $100$ dis­tinct stand­ing desks $d_1,\ldots,d_{100}$ and no chairs. How many ways are there to as­sign the COM­P2804 stu­dents to desks $d_1,\ldots,d_{50}$ and the PSY­CH1000 stu­dents to desks $d_{51},\ldots,d_{100}$ so that each desk has ex­actly two stu­dents at it.

Only three desks

Sup­pose the exam room has three re­ally large ta­bles, $t_1,t_2,t_3$, each of which can eas­ily ac­com­mo­date $200$ stu­dents. How many ways are there to as­sign stu­dents to these ta­bles so that each table is as­signed at least one stu­dent?

Prov­ing a bi­no­mial iden­tity

In this ques­tion we're going to prove a bi­no­mial iden­tity using a com­bi­na­to­r­ial proof (also known as count­ing two dif­fer­ent ways) dis­cussed in Lec­ture 4.

Let $S$ be a set of $n$ el­e­ments. Let $S_0$ be the set of all sub­sets of $S$ that have even size. Let $S_1$ be the set of all sub­sets of $S$ that have odd size.

Find­ing a bi­jec­tion

De­fine a bi­jec­tion $f:S_0\to S_1$ be­tween $S_0$ and $S_1$. You must prove that what­ever func­tion you de­fine is a one-to-one (in­jec­tive) and onto (sur­jec­tive).

A bi­no­mial iden­tity

Prove that $\sum_{k=0}^n (-1)^k\binom{n}{k} = 0$. (You may use the re­sult from the pre­vi­ous ques­tion even if you weren't able to find the bi­jec­tion.)

Mak­ing loot bags

Pro­fes­sor M needs to make $10$ loot bags $b_1,\ldots,b_{10}$ for his son's birth­day party. Each loot bag has the name of one of his son's friends on it and Pro­fes­sor M has $80$ iden­ti­cal pieces of candy. The candy is not very good so he doesn't want any left­over for him­self. He cares a bit about being fair, but not enough to bother count­ing 8 pieces of can for each bag. It's good enough if each bag con­tains at least $3$ pieces of candy. How many ways are there for Pro­fes­sor~M to dis­trib­ute 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 mys­te­ri­ous func­tion

Con­sider the fol­low­ing Python func­tion:

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-neg­a­tive in­te­gers with $x\ge y$, what does $f(x,y)$ re­turn? Ex­plain your an­swer using one of the the­o­rems dis­cussed in class.