CSE 312 – Section 2 Solutions

Spring 2026

Review of Main Concepts (Counting)

Section Plan

Administrivia

Questions about material covered so far?

Problems to be covered in section

Be sure to check out all the remaining problems before you do your homework.

1  Content Review

a)
True or False. For any sets \(A\) and \(B\), the following statement is always true: \(|A \cup B| = |A| + |B|\)

False. In general, if \(A\) and \(B\) are not disjoint, elements in \(A \cap B\) are counted twice in \(|A| + |B|\). By the Principle of Inclusion-Exclusion,

|A ∪ B | = |A |+ |B|− |A ∩ B |.

Therefore, the given equality holds only when \(A\) and \(B\) are disjoint.

b)
If there are 7 pigeons that each go into one of 3 holes:
  • There is at least one hole with exactly 3 pigeons in it.
  • There is at least one hole with at least 3 pigeons in it.
  • There is exactly one hole with at least 3 pigeons in it.

(b). By the Pigeonhole Principle, there will be at least one hole with at least \(\lceil \frac {7}{3} \rceil = 3\) pigeons in it.

c)
\((x+y)^n=\)
  • \(\sum _{k=0}^n \binom {n}{k} x^k y^{n-k}\)
  • \(\sum _{k=0}^n x^k y^{n-k}\)
  • \(\sum _{k=0}^n \binom {n}{k} x^{k}\)

(a). This is the definition of the Binomial Theorem.

d)
An event and sample space are, respectively:
  • The total set of possible outcomes; A subset of the event space
  • A subset of the sample space; The total set of possible outcomes
  • Some set of outcomes; Any other set of outcomes.

(b). By definition, the sample space (\(\Omega \)) encompasses all possible outcomes, and an event (\(E\)) is always a subset of the sample space (\(E \subseteq \Omega \)).

e)
True or False. It is always true that \(\mathbb {P}(E) = \frac {|E|}{|\Omega |}\).

False. This formula only holds if all outcomes in the sample space \(\Omega \) are equally likely.

f)
If \(A\) is the event that I eat an apple today,
  • \(\overline {A}\) is the event that I eat a banana today, and \(P(A) + P(\overline {A}) = 0.5\)
  • \(\overline {A}\) is the event that I do not eat an apple today, and \(P(A) + P(\overline {A}) = 0\)
  • \(\overline {A}\) is the event that I do not eat an apple today, and \(P(A) + P(\overline {A}) = 1\)

(c). \(\overline {A}\) is the complement of event A (the event that A does not happen). Because the sample space probabilities must normalize to 1, the probability of an event plus its complement is always exactly 1.

g)
True or False. For any two events \(A\) and \(B\), \(P(A\cup B) > P(A) + P(B)\).

False. The correct inequality is \(P(A\cup B) \leq P(A) + P(B)\). By the property of inclusion-exclusion for probability, \(P(A\cup B) = P(A) + P(B) - P(A\cap B)\). Because probabilities must be non-negative, subtracting \(P(A\cap B)\) means the union can never be strictly greater than the sum of the individual probabilities.

2  Thinking Combinatorially (8 points)

We saw in Lecture 3 that combinatorial proofs can be more elegant than algebraic proofs and also provide insights into an equation that goes beyond algebra.

Our goal in this problem is to develop the skill and intuition for such proofs. To this end, prove each of the following identities using a combinatorial argument

a)
Give a combinatorial proof of the following identity: \[n \binom {n-1}{r-1} = \binom {n}{r} r.\] Hint: Consider two ways to choose a team of size r out of a set of size n and a captain of the team (who is also one of the team members).

Scenario: We want to count the number of ways to form a team of size \(r\) from a pool of \(n\) people, and designate exactly one of those \(r\) team members as the captain.

  • Left Hand Side (\(n \binom {n-1}{r-1}\)):

    • Step 1: Choose the captain first from the total pool of \(n\) people (\(n\) choices).
    • Step 2: Choose the remaining \(r-1\) team members from the remaining \(n-1\) people (\(\binom {n-1}{r-1}\) choices).

    By the Product Rule, this gives \(n \binom {n-1}{r-1}\) ways.

  • Right Hand Side (\(\binom {n}{r} r\)):

    • Step 1: Choose the entire team of \(r\) people from the pool of \(n\) people (\(\binom {n}{r}\) choices).
    • Step 2: Choose the captain from within the \(r\) selected team members (\(r\) choices).

    By the Product Rule, this gives \(\binom {n}{r} r\) ways.

Conclusion: Since both sides count the exact same scenario, they must be mathematically equal.

b)
Give a combinatorial proof of \[\binom {a+b}{a}=\displaystyle \sum _{i=0}^a{\binom {a}{i}\binom {b}{i}} \;.\] (Note that \(\binom {a}{b}\) is 0 if \(b > a\).)

Scenario: We want to count the number of ways to choose a team of \(a\) people from a larger pool consisting of \(a\) right-handed people and \(b\) left-handed people (for a total of \(a+b\) people).

  • Left Hand Side \(\binom {a+b}{a}\): Choose the team of \(a\) people directly from the entire pool of \(a+b\) people. There are \(\binom {a+b}{a}\) ways to do this.

  • Right Hand Side \(\sum _{i=0}^a{\binom {a}{i}\binom {b}{i}}\): We partition the team selection based on the number of left-handed people on the team, which we will call \(i\). The value of \(i\) can range from \(0\) to \(a\).

    • Step 1: Choose \(i\) left-handed people from the pool of \(b\) left-handed people (\(\binom {b}{i}\) ways).
    • Step 2: To complete the team of \(a\) people, we must choose \(a-i\) right-handed people from the pool of \(a\) right-handed people (\(\binom {a}{a-i}\) ways). Since choosing \(a-i\) people to be on the team is identical to choosing \(i\) people to exclude from the team, \(\binom {a}{a-i} = \binom {a}{i}\).

    Applying the Product Rule, for a specific \(i\), there are \(\binom {a}{i}\binom {b}{i}\) ways to form the team. By the Sum Rule, we sum across all possible values of \(i\) to get \(\sum _{i=0}^a{\binom {a}{i}\binom {b}{i}}\).

Conclusion: Since both sides count the exact same scenario, they are equal.

3  GREED INNIT

Find the number of ways to rearrange the word “INGREDIENT”, such that no two identical letters are adjacent to each other. For example, “INGREEDINT” is invalid because the two E’s are adjacent.

We use the Principle of Inclusion-Exclusion (PIE) and Complementary Counting.

We want the size of the complement: \(|\Omega \setminus (A_I \cup A_E \cup A_N)| = |\Omega | - |A_I \cup A_E \cup A_N|\).

By PIE: \(|A_I \cup A_E \cup A_N| = |A_I| + |A_E| + |A_N| - (|A_I \cap A_E| + |A_I \cap A_N| + |A_E \cap A_N|) + |A_I \cap A_E \cap A_N|\).

Putting this together: \(\frac {10!}{2!2!2!}-\left (\binom {3}{1} \cdot \frac {9!}{2!2!} - \binom {3}{2} \cdot \frac {8!}{2!} + \binom {3}{3} \cdot 7! \right )\)

Repeat the question for the letters “AAAAABBB”.

We must place 5 A’s among the 3 B’s such that no A’s are adjacent. Let’s place the B’s down to create "slots" for the A’s: \(\_ \text { B } \_ \text { B } \_ \text { B } \_\) But this means we must place 5 A’s into 4 slots such that no slot contains two A’s. By an application of the Pigeonhole principle (PHP), this is impossible. To wit:

Since there are 5 pigeons and only 4 holes, by the PHP at least one hole must contain at least \(\lceil 5/4 \rceil = 2\) A’s. Therefore, at least two A’s would have to be adjacent.

Thus there are 0 ways to arrange the letters without adjacent A’s or B’s.

4  Pigeonhole Practice

For each of the following properties a group of people might possess, either give the minimum number of people that must be in a group to ensure that the property holds, or else indicate that the property need not hold even for arbitrarily large groups of people. In either case, justify your answer.

(i)
(2 points) At least 2 people were born on the same day of the year (ignore year of birth).

We use the Pigeonhole Principle.

  • Pigeons: The \(n\) people in the group.
  • Holes: The 365 possible days of the year.
  • Mapping: Each person is mapped to the day of the year on which they were born.

To guarantee that at least one day contains at least 2 people, we need \[ \left \lceil \frac {n}{365} \right \rceil \ge 2. \] Equivalently, we need \(n > 365\). Therefore, the minimum number of people required is \[ \boxed {366}. \]

(ii)
(2 points) At least 2 people were born on April 1.

Answer: The property need not hold, even for arbitrarily large groups.

The Pigeonhole Principle guarantees that some day of the year must be shared once the group is large enough, but it does not guarantee that a specific day is shared.

For example, it is possible to have an arbitrarily large group of people in which everyone was born on April 2. In that case, no one was born on April 1, so the property does not hold.

5  Friendships

Show that in any group of \(n\) people, there are two people who have the same number of friends within the group. (Friendship is bi-directional – i.e., if A is a friend of B, then B is a friend of A – and nobody is a friend of themselves.)

Solve the following two cases separately:

a)
Assume that everyone has at least one friend.

We use the Pigeonhole Principle.

  • Pigeons: The \(n\) people in the group.

  • Holes: The possible numbers of friends a person can have.

    Since everyone has at least one friend, and nobody can be friends with themselves, each person can have anywhere from \(1\) to \(n-1\) friends. Thus, there are \(n-1\) possible values.

  • Mapping: Map each person to the number of friends they have.

Thus, we are placing \(n\) pigeons into \(n-1\) holes. By the Pigeonhole Principle, at least two people must be mapped to the same hole. Therefore, at least two people have the same number of friends.

b)
Assume that at least one person has no friends.

We again use the Pigeonhole Principle.

  • Pigeons: The \(n\) people in the group.

  • Holes: The possible numbers of friends a person can have.

    Since at least one person has \(0\) friends, no person can have \(n-1\) friends: if someone were friends with all other \(n-1\) people, then in particular they would be friends with the person who has no friends, which is impossible. Therefore, the possible numbers of friends range from \(0\) to \(n-2\), giving again \(n-1\) possible values.

  • Mapping: Map each person to the number of friends they have.

Thus, we are placing \(n\) pigeons into \(n-1\) holes. By the Pigeonhole Principle, at least two people must be mapped to the same hole. Therefore, at least two people have the same number of friends.

6  Powers and divisibility

Prove that there exist two powers of 7 whose difference is divisible by 2003. (You may want to use the Pigeonhole principle and the division theorem.)

Recall the division theorem, which states that for any integer \(a\), there exist unique integers \(q,r\) such that \[ a = 2003q + r \;, \] where \(0 \leq r < 2003\). Notably, there are 2003 possible remainders (values that \(r\) can take).

Consider a sequence of powers: \[ 7^0 \quad ,\quad 7^1 \quad ,\quad 7^2 \quad ,\quad 7^3 \quad ,\quad \ldots \quad ,\quad 7^{2003} \;. \] The above sequence has 2004 elements. For the \(i\)-th member of the sequence (\(7^i\)), we can express it as \(2003q_i + r_i\).

We apply the Pigeonhole Principle:

By the Pigeonhole Principle, there must exist a pair, say \(7^n\) and \(7^m\) (where \(n > m\)), such that their remainders are equal (\(r_n = r_m\)).

Taking their difference: \[ 7^n - 7^m = (2003q_n + r_n) - (2003q_m + r_m) = 2003(q_n - q_m)\;, \] Because \(2003(q_n - q_m)\) is a multiple of 2003, the difference \(7^n - 7^m\) is divisible by 2003.

7  Dinner Party

At a dinner party, the \(n\) people present are to be seated uniformly spaced around a circular table. Suppose there is a nametag at each place at the table and suppose that nobody sits down at the correct place. Show that it is possible to rotate the table so that at least two people are sitting in the correct place.

We use the Pigeonhole Principle.

Label the seats \(0,1,\dots ,n-1\) clockwise. For each person \(i\), define \(r_i\) to be the number of clockwise rotations needed to move that person to their correct seat.

Since there are \(n\) people but only \(n-1\) possible rotation values, by the Pigeonhole Principle, there must exist two distinct people \(i\) and \(j\) such that \[ r_i = r_j. \]

If we rotate the table clockwise by this shared amount, both person \(i\) and person \(j\) will be moved to their correct seats simultaneously.

Therefore, it is possible to rotate the table so that at least two people are seated in the correct place.

8  Count the Solutions

9  Balls from an Urn

Say an urn contains one red ball, one blue ball, and one green ball. (Other than for their colors, balls are identical.) Imagine we draw two balls with replacement, i.e., after drawing one ball, with put it back into the urn, before we draw the second one. (In particular, each ball is equally likely to be drawn.)

a)
Give a probability space describing the experiment.

Sample Space: \(\Omega = \{B, R, G\}^2\) (all ordered pairs of the three colors).

Since the draws are with replacement and equally likely, \(|\Omega | = 3^2 = 9\).

Probabilities: \(\Prob {\omega } = 1/9\) for all \(\omega \in \Omega \).

b)
What is the probability that both balls are red? (Describe the event first, before you compute its probability.)

The event is \(A = \{RR\}\). Since \(|\Omega | = 9\) and outcomes are equally likely, its probability is: \(\Prob {A} = \frac {|{A}|}{|\Omega |} =\) \(\frac {1}{9}\).

c)
What is the probability that at most one ball is red?

This is \(A^c\), the complement of event \(A\) ("both balls are red"). By the corollary of the probability axioms: \(\Prob {A^c} = 1 - \Prob {A} = 1 - \frac {1}{9} =\) \(\frac {8}{9}\).

d)
What is the probability that we get at least one green ball?

The event is \(B = \{GR, GB, GG, RG, BG\}\). \(\Prob {B} = \frac {|{B}|}{|\Omega |} = \) \(\frac {5}{9}\).

e)
Repeat b)-d) for the case where the balls are drawn without replacement, i.e., when the first ball is drawn, it is not placed back from the urn.

The probability space changes. The outcomes \(RR, GG, BB\) are no longer possible. \(\Omega = \{BG, BR, GB, GR, RB, RG\}\). \(|\Omega | = 6\). All remaining elements have equal probability, so \(\Prob {\omega } = 1/6\).

  • For b), the event \(A = \{RR\}\) is empty. Therefore, \(\Prob {A} =\) \(0\).
  • For c), the complement \(A^c\) encompasses the entire sample space \(\Omega \). Therefore, \(\Prob {A^c} =\) \(1\).
  • For d), the event becomes \(B = \{GR, GB, RG, BG\}\). Therefore, \(\Prob {B} = \frac {4}{6} =\) \(\frac {2}{3}\).

10  Spades and Hearts

Given 3 different spades and 3 different hearts, shuffle them uniformly at random.

What is the sample space and how big it is (i.e., what what is its cardinality? Compute \(\Prob {E}\), where \(E\) is the event that the suits of the shuffled cards are in alternating order.

Since outcomes are equally likely, we compute the probability: \[\Prob {E} = \frac {|E|}{|\Omega |} = \frac {2\cdot (3!)^2}{6!} = \boxed {\text {0.1}}\]

11  Shuffling Cards

We have a deck of cards with 4 suits, with 13 cards in each. Within each suit, the cards are ordered Ace \(>\) King \(>\) Queen \(>\) Jack \(>\) 10 \(> \cdots >\) 2. Also, suppose we perfectly shuffle the deck (i.e., all possible shuffles are equally likely). What is the probability the first card on the deck is (strictly) larger than the second one?

Therefore: \[\Prob {E} = \frac {|{E}|}{|{\Omega }|} = \frac {1248}{2652} = \frac {13 \cdot 3 \cdot 2^5}{13 \cdot 3 \cdot 2^2 \cdot 17} = \boxed {\frac {8}{17}} \approx 0.47\]

12  Weighted Die

Consider a weighted die such that

What is the probability that the outcome is 3 or 4?

By the normalization axiom of probability, the sum of probabilities for the sample space must equal 1. \[\sum _{i=1}^{6}{\Prob {i}} = 1\]

We substitute the given equalities to express the entire sum in terms of \(\Prob {3}\): \[1 = \Prob {1} + \Prob {2} + \Prob {3} + \Prob {4} + \Prob {5} + \Prob {6}\] \[1 = (3 \cdot \Prob {3}) + (3 \cdot \Prob {3}) + \Prob {3} + \Prob {3} + \Prob {3} + \Prob {3}\] \[1 = 10 \cdot \Prob {3}\]

Solving algebraically, \(\Prob {3} = 0.1\). Because they are equal, \(\Prob {4} = 0.1\) as well. Since rolling a 3 and rolling a 4 are mutually exclusive events, we use additivity: \[\Prob {3 \text { or } 4} = \Prob {3} + \Prob {4} = 0.1 + 0.1 = \boxed {\text {0.2}}\]

13  Additivity of Probability

Use the additivity of probability to prove the Principle of Inclusion/Exclusion (PIE) for 3 events, i.e., \[ \Prob {A \cup B \cup C} = \Prob {A} + \Prob {B} + \Prob {C} - \Prob {A \cap B} - \Prob {A \cap C} - \Prob {B \cap C} + \Prob {A \cap B \cap C} \;. \]

We can now compute the probabilities of the events associated with the 7 distinct areas of the Venn Diagram:

A Venn diagram showing the intersection of sets A, B and C.

\[ \begin {aligned} a & = \Prob {A \setminus (B \cup C)} \\ b & = \Prob {B \setminus (A \cup C)} \\ c & = \Prob {C \setminus (A \cup B)} \\ d & = \Prob {(A \cap B) \setminus C} \\ e & = \Prob {(A \cap C) \setminus B} \\ f & = \Prob {(B \cap C) \setminus A} \\ g & = \Prob {A \cap B \cap C} \end {aligned} \]

By the additivity of probability for mutually exclusive regions: \[ \Prob {A \cup B \cup C} = a+b + c + d + e + f + g \;. \]

Also, we can build the standard intersections from these regions: \[ d + g = \Prob {A \cap B} \;,\;\;\; e + g = \Prob {A \cap C} \;,\;\;\; f + g = \Prob {B \cap C} \;, \] and the standard sets: \[ a + d + e + g = \Prob {A} \;,\;\;\; b + d + f + g = \Prob {B} \;,\;\;\; c + e + f + g = \Prob {C} \;. \] Now, we algebraically substitute these into the right side of the PIE equation and verify it matches the union: \begin {equation*} \begin {aligned} &(a + d + e + g) + (b + d + f + g ) + (c + e + f + g) - (d+g) - (e + g) - (f + g) + g \\ &= a + b + c + 2d + 2e + 2f + 3g - d - e - f - 3g + g \\ &= a + b + c + d + e + f + g \;. \end {aligned} \end {equation*} Which is exactly \(\Prob {A \cup B \cup C}\).