Exercises

Exercises 3.4 Exercises

Additional Exercises for Chapter 3

1.

Prove that any $(n+1)$-subset of $\{1,2,\ldots,2n\}$ has a pair of consecutive numbers.

Why does this imply that any $(n+1)$-subset must have a pair of relatively prime numbers?

Define pigeonholes to be $\{1,2\}, \{3,4\}, \ldots, \{2n-1,2n\}\text{.}$ Note that there are $n$ of them, and each set has two consecutive integers.

The pigeons are the $n+1$ elements we pick from $\{1,2,\ldots,2n\}\text{.}$ Since there are more pigeons than pigeonholes, by Corollary 3.1.5 we conclude that one pigeonhole (set) has at least two pigeons.

This means there must be two consecutive integers among the $n+1$ we picked.

Finally, any two consecutive integers are relatively prime. We can see this by applying Checkpoint 1.3.6 with $a = b+1$ and $k = 1\text{.}$

2.

Prove that any $(2n+1)$-subset of $\{1,2,\ldots,3n\}$ has three consecutive numbers.

Hint

Construct pigeonholes so that each pigeonhole has three consecutive numbers, then apply Theorem 3.1.3.

3.

The numbers 1 to 10 are placed in some order around a circle. Prove that some set of three consecutive numbers sums to at least 17.

Hint

What should the average of all the three-sums be?

4. Fall 2019 Term Test.

Prove that if seven integers are selected from

\begin{equation*} \{1,2,3,\ldots,12\}\text{,} \end{equation*}

then some two integers $m$ and $n$ must have been chosen so that $m + 3 = n\text{.}$

Solution

Define pigeonholes to be the sets

\begin{equation*} \{1,4\}, \{ 2,5\}, \{3,6\}, \{7, 10\}, \{8, 11\}, \{9, 12\} \end{equation*}

and pigeons to be the integers selected from $\{1,2,\ldots,12\}\text{;}$ assign each integer selected to the bin that contains that number.

Since seven integers are selected, one of the bins must have two numbers $m$ and $n$ selected from it—these two numbers satisfy the given condition (larger number is three more than the smaller number).

5.

Jungkook has 6 friends; over several days he invites some of them over to his home to eat lamb skewers for dinner, so that the company never repeats (i.e. a different set of friends comes every night). If he has at least one friend over every day, how many days can he follow this rule?

6.

Place 5 points inside (or on the boundary) of a square with side length 2 cm. Show that there is a pair of points no more than $\sqrt{2}$ cm apart.

7.

Recall that the midpoint of the segment joining points $(a,b)$ and $(c,d)$ on the plane has coordinates

\begin{equation*} \left(\frac{a+c}{2},\frac{b+d}{2}\right)\text{.} \end{equation*}

Show that given five integer points (i.e. points with integer coordinates) on the plane, the midpoint of the segment joining some pair of them is also an integer point.

Hint

Consider parity.

8.

If we select 38 subsets of size at most three from the set $S = \{1,2,\ldots,13\}\text{,}$ show that two of these subsets must have the same sum.

9. Fall 2021 Final.

If we select 20 subsets of size at least five from the set $U = \{2,5,8,11,14,17,20\}\text{,}$ show that two of these subsets will have the same sum.

10. Winter 2022 Term Test.

Let $S = \{6,8,10,12,\ldots,30,32\}\text{.}$

Show that if seven distinct integers are picked from $S\text{,}$ that two of these integers will have a sum that is divisible by three.
How many distinct integers do you need to pick from $S$ to guarantee that three of them sum of a multiple of three?

Hint

Note that part b is implicitly asking for the best possible answer; that is, what is the smallest number of integers for which the guarantee still holds?

Consider the remainders of the elements of $S$ when divided by 3.

11.

The Greater Toronto Area has a population of about 6 million. Suppose that each resident has a jar with 100 coins, consisting of nickels, dimes, quarters, loonies ($1), and toonies ($2). Prove that two residents must have identical jars.

12.

The UTM e-sports team Eagle Geniuses is training for an Ontario e-sports tournament called The Provincial, which is 30 days away. They are scheduled to play at least one scrim (practice game) with another university team every day for the next 30 days; their coach tells them they will be playing a total of 42 games.

Prove that there was a period of consecutive days during which the team scrimmed exactly 17 times.

Hint

Similar to Checkpoint 3.1.15.

13.

Fall 2020 course data about 1000 first-year students at a college reveal that:

800 are taking calculus
750 are taking linear algebra
550 are taking an intro to proofs course
650 are taking calculus and linear algebra
500 are taking linear algebra and proofs
500 are taking calculus and proofs
450 are taking all three

How many students are taking none of these courses?
How many students are taking only linear algebra?
Draw a venn diagram and indicate the number of students for each part of the diagram.

14.

How many ways are there to place 11 distinct people into 3 distinct rooms?

How many ways are there to place 11 distinct people into 3 distinct rooms such that each room has at least one person?

15.

Twenty students in a class exchange quiz papers for peer evaluation. How many ways can this be done so that no student gets their own paper?

16.

Count the number of 5-letter arrangements that can be formed from the letters of the word

EUPHORIA

such that the string EAR does not appear, and there is at least one vowel.

17.

Count the number of integer solutions to the system

\begin{equation*} \begin{cases} x_1 + x_2 + x_3 + x_4 = 25 \amp \\ 2 \leq x_1 \leq 9 \amp \\ 3 \leq x_2 \leq 9 \amp \\ -1 \leq x_3 \leq 11 \amp \\ 5 \leq x_4 \ \ \amp \end{cases} \end{equation*}

Hint

Deal with the lower bounds first using the same technique as in Checkpoint 2.4.10, then use inclusion-exclusion (Theorem 3.2.6).

18.

Count the number of lattice paths from $(0,0)$ to $(6,4)$ that pass through at least one of the points $(2,3)\text{,}$ $(3,1)\text{,}$ and $(5,4)\text{.}$

19. Winter 2022 Final.

Count the number of five-card hands from a standard deck of cards that satisfy at least one of the following conditions:

The hand has only hearts or spades.
The hand has exactly one three-of-a-kind.
The hand has exactly two kings.

20.

Consider a set of $n$ cats and $n$ dogs; suppose we want to pair them up for an afternoon playdate. Derive formulas for the number of ways this can be done, such that:

For each $i\text{,}$ the $i$th heaviest cat is not paired up with the $i$th heaviest dog (but pairs can have two dogs or two cats).
Same condition as (a), but also each pair has exactly one cat and one dog.

Solution

Let $U$ be the set of all pairings of the $2n$ pets, and define the forbidden set $A_i$ as the set of all pairings where the $i$th heaviest cat is paired with the $i$th heaviest dog.

Then the desired quantity is

\begin{equation*} N = |A_1^c \cap A_2^c \cap \cdots \cap A_n^c|\text{,} \end{equation*}

which is the number of pairings satisfying the given condition. By Theorem 3.2.6, this is equal to the sum

\begin{align*} N \amp = \sum_{S \subseteq \{1,2,\ldots,n\}} (-1)^{|S|} \left| \bigcap_{i \in S} A_i\right| \\ \amp = |U| - \sum_{1 \leq i \leq n} |A_i| + \sum_{1 \leq i \lt j \leq n} |A_i \cap A_j| - \cdots + (-1)^n|A_1 \cap A_2 \cap \cdots \cap A_n|. \end{align*}

First, we compute $|A_i|$ by observing that once the $i$th heaviest dog and $i$th heaviest cat are paired up, then we can pair up the other $2n-2$ pets with no restrictions.

The number of ways to do this can be determined as follows:

Create a pair out of the $2n-2$ remaining animals: $\binom{2n-2}{2}$ ways.
Create a pair out of the $2n-4$ remaining animals: $\binom{2n-4}{2}$ ways.
$\displaystyle \vdots$
Create a pair out of the 4 remaining animals: $\binom{4}{2}$ ways.
Create a pair out of the 2 remaining animals: $\binom{2}{2} = 1$ way.
Divide by $(n-1)!$ since the order in which pairs are formed doesn't matter.

Hence for any $i = 1,2,\ldots,n$ we have

\begin{align*} |A_i| \amp = \binom{2n-2}{2}\binom{2n-4}{2}\cdots\binom{4}{2}\binom{2}{2}\dfrac{1}{(n-1)!}\\ \amp = \dfrac{(2n-2)!}{2!\ (2n-4)!}\cdot\dfrac{(2n-4)!}{2!\ (2n-6)!}\cdots\dfrac{4!}{2!\ 2!}\cdot \dfrac{2!}{2! \ 0!} \cdot \dfrac{1}{(n-1)!}\\ \amp = \dfrac{(2n-2)!}{(2!)^{n-1}\ (n-1)!} \end{align*}

For the pairwise intersections $|A_i \cap A_j|$ the only difference is that we are fixing two pairs to begin, and then grouping the remaining $2n-4$ animals into pairs. This means that for any $i \ne j$ we have

\begin{align*} |A_i \cap A_j| \amp = \binom{2n-4}{2}\binom{2n-6}{2}\cdots\binom{4}{2}\binom{2}{2}\dfrac{1}{(n-1)!}\\ \amp = \dfrac{(2n-4)!}{2!\ (2n-6)!}\cdot\dfrac{(2n-6)!}{2!\ (2n-8)!}\cdots\dfrac{4!}{2!\ 2!}\cdot \dfrac{2!}{2! \ 0!} \cdot \dfrac{1}{(n-1)!}\\ \amp = \dfrac{(2n-4)!}{(2!)^{n-2}\ (n-2)!} \end{align*}

And in general, the cardinality of the intersection of $k$ of the $A_i$'s is:

\begin{equation*} |A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k}| = \dfrac{(2n-2k)!}{(2!)^{n-k}\ (n-k)!}\text{.} \end{equation*}

Note this is also true when we pick $k = 0\text{:}$ we just get the number of ways we can group $2n$ animals into pairs unrestricted.

Since this quantity is only dependent on how many $A_i$'s we are taking, we can write the inclusion-exclusion as:

\begin{align*} N \amp = |U| - \binom{n}{1}|A_1| + \binom{n}{2}|A_1 \cap A_2| - \cdots + (-1)^n\binom{n}{n}|A_1 \cap A_2 \cap \cdots \cap A_n|\\ \amp = \sum_{k=0}^n (-1)^k\binom{n}{k}\dfrac{(2n-2k)!}{(2!)^{n-k}\ (n-k)!}. \end{align*}

21.

Suppose that four friends have two pets each—a cat and a dog—and they all meet up at the park. They decide to form four groups of one human, one cat, and one dog each. Count the number of ways they can do this, such that:

No human is with their dog.
No human is with either of their pets.
Each human is grouped with at most one of their pets.