Recitation 1

Recitation notes for the week of August 31, 2026.

Proof Idea vs. Proof Details

In CSE 331, you will be required to split your proofs into a proof idea and proof details.

Proof Idea

The proof idea is the TL;DR of the proof. It gives a high-level summary of the argument, including the proof method and the main reason the argument works.

Proof Details

The proof details are the complete formal proof. This is where you carry out and justify the steps described in the proof idea.

Why separate them?

A proof idea helps the reader see the strategy before working through the details. The proof details then establish that every step of that strategy is correct.

Matchings: Small Examples

Note

Matchings will also be discussed in class. Here, we will use small examples to become comfortable with the definitions and with reasoning about them.

Fix an integer $n \ge 0$. Let $M=\{m_1,m_2,\dots,m_n\}$ be a set of $n$ men and let $W=\{w_1,w_2,\dots,w_n\}$ be a set of $n$ women. A pair $(m,w)$ represents a potential relationship between a man $m\in M$ and a woman $w\in W$. For now, assume that every man can be paired with every woman.

Matching

A matching is a set of pairs in which no person appears in more than one pair.

Perfect Matching

A perfect matching is a matching in which every person appears in exactly one pair. Equivalently, every $m\in M$ is paired with exactly one woman, and every $w\in W$ is paired with exactly one man.

Examples with $n=3$

Suppose $M=\{m_1,m_2,m_3\}$ and $W=\{w_1,w_2,w_3\}$. Then

\[\{(m_1,w_1),(m_2,w_2),(m_3,w_3)\}\]

is a perfect matching. Every person appears exactly once.

$\{(m_1,w_2),(m_3,w_1)\}$ is a matching, but it is not perfect because $m_2$ and $w_3$ are unmatched.
$\{(m_1,w_1),(m_1,w_2)\}$ is not a matching because $m_1$ appears in two pairs.

Small Example

Let $M=\{m_1,m_2\}$ and $W=\{w_1,w_2\}$. List every possible perfect matching. How many are there?

Counting Perfect Matchings by Induction

Exercise 1

Assume that every man can be paired with every woman. Prove that the total number of perfect matchings between $n$ distinct men and $n$ distinct women is $n!$.

Recall that $n!=n\times(n-1)\times(n-2)\times\cdots\times2\times1$.

Begin with an example

When $n=3$, $m_1$ can be paired with any of the three women. After that choice, $m_2$ can be paired with either of the two remaining women, and $m_3$ must be paired with the final woman. Therefore, there are

\[3\times2\times1=3!\]

possible perfect matchings.

Hint

When thinking about a proof problem, it is almost always helpful to make and work through small examples.

Overview of proof by induction

Inductive proofs have three main steps:

Base Case: prove the claim for the smallest relevant value, here $n=1$.
Inductive Hypothesis: fix an arbitrary $k\ge2$ and assume the claim is true for $n=k-1$.
Inductive Step: use the inductive hypothesis to prove the claim for $n=k$.

Correct proof by induction

Proof Idea

We prove the claim by induction on $n$, the number of people in each set. For $n=1$, there is exactly one perfect matching. For the inductive step, fix one man. He has $k$ possible women with whom he can be paired. After choosing his partner, $k-1$ men and $k-1$ women remain, and the inductive hypothesis counts the perfect matchings among them. Thus, the total is $k\cdot(k-1)!=k!$.

Proof Details

Base Case Let $n=1$. Then $M=\{m_1\}$ and $W=\{w_1\}$. The only perfect matching is $\{(m_1,w_1)\}$. Therefore, there is $1=1!$ perfect matching.

Inductive Hypothesis Fix an arbitrary integer $k\ge2$. Assume that for any sets of $k-1$ men and $k-1$ women, where every man can be paired with every woman, there are $(k-1)!$ perfect matchings.

Inductive Step Consider $M=\{m_1,m_2,\dots,m_k\}$ and $W=\{w_1,w_2,\dots,w_k\}$. There are $k$ possible women to pair with $m_1$. After one woman is chosen, $k-1$ men and $k-1$ women remain. By the inductive hypothesis, the remaining people have $(k-1)!$ possible perfect matchings. Every perfect matching pairs $m_1$ with exactly one woman, and the collections corresponding to different partners for $m_1$ are disjoint. Thus, these $k$ collections partition all perfect matchings, so the total number is

\[k\cdot(k-1)!=k!.\]

Therefore, the claim holds for $n=k$, and hence for every integer $n\ge1$.

Stable Matching

So far, we have cared only about whether everyone is paired. We now give each person preferences over the people with whom they could be paired.

Preference List

A preference list ranks possible partners from most preferred to least preferred. For example,

\[L_{m_1}: w_2>w_1>w_3\]

means that $m_1$ prefers $w_2$ to $w_1$, and prefers $w_1$ to $w_3$.

Instability

Suppose a perfect matching pairs $m$ with $w$ and pairs $m'$ with $w'$. If $m$ prefers $w'$ to $w$, and $w'$ prefers $m$ to $m'$, then $(m,w')$ is an instability, also called a blocking pair.

Stable Matching

A stable matching is a perfect matching that has no instabilities.

The Problem

Input:

A set of $n$ men $M=\{m_1,m_2,\dots,m_n\}$.
A set of $n$ women $W=\{w_1,w_2,\dots,w_n\}$.
For every $m\in M$, a complete, strict preference list $L_m$ ranking all women.
For every $w\in W$, a complete, strict preference list $L_w$ ranking all men.

Output: A stable matching.

Exercise 2

State directly in terms of preferences what it means for a perfect matching to have no instability.

Answer

For every man $m$ and woman $w$ who are not paired with each other, either $m$ prefers his assigned partner to $w$, or $w$ prefers her assigned partner to $m$. In other words, there is no pair of people who are not matched to each other and both prefer one another to their assigned partners.

Proof by Counterexample

To disprove a universal statement, it is enough to give one example for which the statement is false.

Exercise 3

Argue whether the following statement is true or false: There is no possible stable matching in which everyone is paired with their first choice.

Proof Idea

We give an example with $n=3$ in which every person is paired with their first choice. Because no one prefers another person to their assigned partner, there can be no instability.

Proof Details

Let $M=\{m_1,m_2,m_3\}$ and $W=\{w_1,w_2,w_3\}$. Consider the following preference lists:

\[L_{m_1}: w_1>w_2>w_3 \qquad L_{w_1}: m_1>m_2>m_3\]

\[L_{m_2}: w_2>w_3>w_1 \qquad L_{w_2}: m_2>m_3>m_1\]

\[L_{m_3}: w_3>w_1>w_2 \qquad L_{w_3}: m_3>m_1>m_2\]

The perfect matching

\[\{(m_1,w_1),(m_2,w_2),(m_3,w_3)\}\]

pairs every person with their first choice. Therefore, no two people can both prefer one another to their assigned partners, so the matching is stable. This counterexample proves that the statement is false.

Proof by Contradiction

Overview

To prove a statement $x$ by contradiction, assume $\neg x$, follow the consequences of that assumption, and derive a contradiction.

Exercise 4

Assume that the following statements are true:

Every blockbuster movie has a hero.
Jake Sully and Neytiri are dating.
The highest-grossing movie ever is a blockbuster.
A hero in a movie never dies.
The movie Avatar has made the most money ever.
The heroine always dates the hero if the movie has one.
Neytiri is the heroine of Avatar.

Prove by contradiction that Jake Sully is alive at the end of Avatar. Clearly state any additional assumptions needed in the proof.

Additional Assumptions

Each movie has one designated hero.
Dating is symmetric and exclusive: if two people date, each dates the other and neither dates anyone else.
“The hero never dies” means that the hero is alive at the end of the movie.

Proof Idea

Assume that Jake Sully is not alive at the end of Avatar. Use the given statements to show that Avatar has a hero who dates Neytiri. The additional assumptions then force that hero to be Jake Sully, contradicting the earlier deduction that Jake is not a hero of Avatar.

Proof Details

Assume for contradiction that Jake Sully is not alive at the end of Avatar. Under our interpretation that a hero who never dies is alive at the end, Jake cannot be a hero of Avatar.

Since Avatar has made the most money ever, it is the highest-grossing movie. The highest-grossing movie is a blockbuster, and every blockbuster has a hero. Therefore, Avatar has a designated hero; call this person $h$.

Neytiri is the heroine of Avatar, so she dates $h$. We are also given that Jake Sully and Neytiri are dating. By the additional assumptions that dating is symmetric and exclusive, $h$ must be Jake Sully. This contradicts the earlier deduction that Jake is not a hero of Avatar.

Therefore, our original assumption was false, and Jake Sully is alive at the end of Avatar.