CSE 312 – Section 2


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|\)
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.
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}\)
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.
e)
True or False. It is always true that \(\mathbb {P}(E) = \frac {|E|}{|\Omega |}\).
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\)
g)
True or False. For any two events \(A\) and \(B\), \(P(A\cup B) > P(A) + P(B)\).

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

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.

Repeat the question for the letters “AAAAABBB”.

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).
(ii)
(2 points) At least 2 people were born on April 1.

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.
b)
Assume that at least one person has no 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.)

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.

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.
b)
What is the probability that both balls are red? (Describe the event first, before you compute its probability.)
c)
What is the probability that at most one ball is red?
d)
What is the probability that we get at least one green ball?
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.

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.

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?

12  Weighted Die

Consider a weighted die such that

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

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} \;. \]