Recitation 2

Recitation notes for the week of September 3, 2025.

Overview

Recitation 1 Review and HW0 Answers

Before we begin, go back and review the content from recitation 1, particularly the Reduction section where we go over Geometric Search.

In addition, the HW0 answer key has been posted here. Going forward, the answer keys will not be released on the course webpage, but instead will be posted on piazza (as a link to a PDF) on Wednesdays.

Common Mistakes

The common mistakes we saw in submissions were either:

  • Not using anything specific to the problem at hand (proving $n!$, but not how it relates to the problem.)
  • Simply restating the problem statement (while important to the proof, you need to show how the problem set-up proves a certain statement.)

Stable Matching Review

The problem

Input:

  • Set of $n$ men $M = \{m_1, m_2, \dots,m_n\}$
  • Set of $n$ women $W = \{w_1, w_2, \dots, w_n\}$
  • For every $m\in M$, $L_m$ a total ranking of all women
  • For every $w\in W$, $L_w$ a total ranking of all men

Output: A stable matching.

Stable Matching

A perfect matching that has no instabilities.

Perfect Matching

For every $m\in M$, $m$ is assigned exactly $1$ woman AND for every $w\in W$, $w$ is assigned exactly $1$ man.

Instability

Given two pairs $(m, w)$ and $(m', w')$, where $m$ prefers $w'$ to $w$ and $w'$ prefers $m$ to $m'$ the pair $(m, w')$ is an instability.

Exercise 1

(This is to make sure you remember how to propagate negations in first order logic statements.) How would you define a perfect matching to be a stable matching, directly in terms of the preferences (i.e. state logically what no instability means.)

Proof by Induction

We will review Q1 on Homework 0.

Exercise 2

Prove that the total number of perfect matchings when you have $n$ men and $n$ women is $n!$.

(Recall $n!=n\times(n−1)\times (n−2)\times\cdots\times 2\times 1$.)

Perfect matching $\neq$ Stable matching

In a perfect matching, we do not care about preferences, just that every individual is part of an exclusive pair.

Example 1

Consider the case of $n=3$, i.e. $W=\{w_1, w_2, w_3\}$ and $M=\{m_1,m_2,m_3\}$. In this case, an example of a perfect matching will be $\{(m_1, w_1), (m_2, w_2), (m_3, w_3)\}$.

Note that $m_1$ can be with $3$ women, (given $m_1$'s assignment) $m_2$ with $2$, and (given $m_1$ and $m_2$'s assignment) $m_3$ with the last woman. I.e. we have $3\times 2\times 1 = 3!$ choices.

Hint

When thinking about HW problems, it's almost ALWAYS super helpful to make and work through examples.

Overview of proof by induction

Inductive Proofs have 3 steps:

  1. Base Case (In the current example, $n = 1$).
  2. Inductive Hypothesis (In the current example, $n = k-1$ for some $k\ge 2$).
  3. Inductive Step (In the current example, prove for $n = k$).

Note

The values above (i.e. $n$ and $k$) are not set in stone: they can change depending on the problem statement.

Back to Exercise 2

Incorrect Proof by Induction

Before we go into a correct proof by induction of Exercise 2 (with properly separated proof idea and proof details), we go through an incorrect (or perhaps more precisely incomplete) proof details that will get you zero points.

(Incorrect/Incomplete) Proof Details

Let $P(n)$ denote the number of perfect matchings with $n$ men and $n$ women.

Base Case $P(1)=1!=1$

Inductive Hypothesis Assume that $P(n-1)=(n-1)!$

Inductive Step Note that $P(n)=n\cdot P(n-1)=n\cdot (n-1)!=n!$.

What is wrong with the above proof?

Before going ahead, pause to think for yourself: why is the above proof incorrect/incomplete?

A digression: how to debug a proof

One of the things that makes it hard to do proofs (at least at the beginning) is being able to "debug" your proofs. Again, at least when you start figuring our proofs, debugging your proof seems hard since there is no debugger that you can "run" your proof on (at least, not the kind we do in CSE 331.) However, like debugging code, there are certain "tests" one can "run" on your proof to see if you catch bugs. Below we mention two such strategies, which are very useful in catching bugs in your proof.

Debugging Strategy 1: Are you justifying all your steps?

Perhaps the most common mistake in proof is not to justify ALL the steps of your proof. Basically, your proof is a sequence of claims/steps, where each step is supposed to follow from the previous one (or from a fact that is given in the problem statement or is a known result--either in this class or another class like CSE 191). However, each step of your proof should be justified.

One common counter to the above is that in the above proof detail, the reasoning for each step is obvious so there is no reason to write down a reasoning. My counter to this is the following:

  • If you think the argument is so obvious, then just write down that obvious reasoning in one sentence.
  • If you cannot write it down in one sentence, perhaps it is not as obvious as you thought!
    • Note that what is obvious to you in your mind has to be communicated to the grader!. As mentioned in the homework policy document, in CSE 331 for grading of homeworks, if you do not provide a justification, we will assume that you do NOT know/understand the justification. If you are unsure, it is always better to give more detail than less!

The next strategy is perhaps bit more subtle than the above and this is something that you will need to actively work on to develop.

Debugging Strategy 2: Are you proving more than what is asked for?

The basic idea is to do the following mental exercise: does your proof actually prove an even stronger statement than what is asked for in the question?

Now, it is possible that you indeed do have a correct proof of a stronger statement than the one asked for in the question, but if you are just starting out doing proofs it is much much more likely that your proof is wrong!

A related strategy is to ask the following: does your proof use anything given in the problem statement? If not, then this almost surely means that your proof end up "proving" extra things (and in many cases it will end up "proving" an incorrect statement.)

Exercise 3

Before moving on, use the above two strategies to figure out where the "(Incorrect/Incomplete) Proof Details" for Exercise 2 went wrong.

Debugging the incorrect/incomplete proof details

Applying debugging strategy 1

The short answer is that none of the steps have been justified, so based on how we grade CSE 331 homework questions, the above proof details will get a $0$. But for the sake of completeness, let us walk through all four steps of the proof:

  1. The first one is just defining $P(n)$, so it seems odd to say that this step needs a justification. But there is an assumption: i.e. the number of perfect matchings only depends on the number $n$ and not the actual identities of the $n$ men and women. Of course, this is exactly what is argued in part (a) of the Q1 on HW0-- but the solution explicitly needs to refer to part (a) of Q1 to justify the definition.
  2. The second step is correct but there is no justification! To prove the base case, you should use something from the problem statement.
  3. The third step is actually fine, though if we were being pedantic, then the inductive hypothesis needs you to quantify the parameter that you are inducting on. In particular, the above inductive hypothesis step should be prefixed by "Assume that for all integers $n\ge 2$," (and then state the claim.)
  4. The issue with the fourth step is exactly the same issue as with the second step.

One could argue that what the above strategy shows that one just "missed" justifying the steps of the proof. So what's the big deal? Applying the 2nd debugging strategy shows what can go wrong.

Applying debugging strategy 2

As mentioned above, this strategy takes more getting used to, and we do not have any "rules of thumb" on how to go about applying this strategy. We just show how, in this case, the "proof" above actually proves something incorrect.

Assume that instead of counting the number of perfect matchings between $n$ men and women you are supposed to count the number of pairs among $n$ men and women, i.e. if $M$ and $W$ are the set of $n$ men and women, we want to count how many pairs $(m,w)\in M\times W$ exist? Hint: The answer is $n^2$ (if you do not see/remember why this is the case try and prove this claim!)

Below is an incorrect proof that the number of such pairs if $n!$:

(Definitely) Incorrect Proof Details

Let $P(n)$ denote the number of perfect matchings with pairs of $n$ men and $n$ women.

Base Case $P(1)=1!=1$

Inductive Hypothesis Assume that $P(n-1)=(n-1)!$

Inductive Step Note that $P(n)=n\cdot P(n-1)=n\cdot (n-1)!=n!$.

Note that the only change in the above "proof" detail from the previous incomplete proof details is that we changed the definition of $P(n)$ to now denote the number of pairs from the number of perfect matchings. So of course the proof is wrong, but note that if one agrees that the amount of details/justifications was enough for the previous proof details, then clearly the same argument should hold here.

Of course, we know that the proof is wrong since $n!\ne n^2$ for any $n\gt 1$. So here's a mini-exercise for you: where is the above proof wrong? (Hint: Look at the inductive step argument.)

Correct Proof by Induction

Next, we present a correct proof by induction of Exercise 2. Indeed, the proof detail below essentially fleshes out the missing justifications from the earlier incomplete proof details. Also for illustration purposes, we present the proof idea for Exercise 2 first.

Proof Idea

We'll prove this by induction on $n$, the number of people of each gender that we are matching. Our base case will be $n=1$, where it will be straightforward to show that the number of perfect matchings is $1!=1$. We will assume that for a set of $n=k-1$ people of each gender, the total number of possible perfect matchings is $\left(k-1\right)!$. Then we will use our assumption for $n=k-1$ to show that with one more man and one more woman, that our number of possible perfect matchings is $k\times (k-1)! = k!$.

Proof Details

Base Case (Prove for $n=1$.) Here we have $M=\{m_1\}$ and $W=\{w_1\}$. The only perfect matching is $\{(m_1, w_1)\}$ so there is $1$ perfect matching. $1 = 1!$ so there are $1! = n!$ perfect matchings.

Inductive Hypothesis Assume that for $n = k-1$ there are $(k-1)!$ perfect matchings.

Inductive Step (Prove that for $n = k$ there are $n! = k!$ perfect matchings.) Here we have $M = \{m_1, m_2,\dots, m_k\}$ and $W = \{w_1, w_2,\dots, w_k\}$. Consider $m_1$. There are $k$ possible choices for $m_1$. After the initial matching, regardless of choice there are $(k-1)$ men and $(k-1)$ women left. From the inductive hypothesis, we know that there are $(k-1)!$ perfect matchings when $n = (k-1)$. Therefore the total number of matchings is \[k\times (k-1)! = k\times (k-1)\times(k-2)\times(k-3)\times \cdots\times 1 = k! = n!.\]

Proof by Contradiction

(Not to be confused with proof by counterexample.)

Overview

Prove $x$.

Assume $\neg x$ and follow the logic until you reach a contradiction.

Aside (proof by counterexample)

Proof by counterexample

When you are able to prove a point by giving an example that makes the statement false, e.g. Prove that blah is or is not true.

If you are proving that a statement is not true, you can often use a counterexample. (This is not always the case, but it is the most common case where counterexamples are used.)

Exercise 3

Argue whether the following statement is true or false: There is no possible stable matching where everyone matches with his/her first choice.

Proof Idea

We will give an example with $n=3$, where all men have a unique most preferred woman and vice-versa. In this case, the most preferred pairs form a stable matching.

Proof Details

Let $M = \{m_1, m_2, m_3\}$ and $W = \{w_1, w_2, w_3\}$. Now consider the following preference lists: \[ L_{m_1}: w_1 > w_2 > w_3~~~~ L_{w_1}: m_1 > m_2 > m_3\] \[ L_{m_2}: w_2 > w_3 > w_1~~~~ L_{w_2}: m_2 > m_3 > m_1\] \[ L_{m_3}: w_3 > w_1 > w_2~~~~ L_{w_3}: m_3 > m_1 > m_2\]

In this case, $\{(m_1,w_1), (m_2,w_2),(m_3,w_3)\}$ is a stable matching.

Back to proof by contradiction

Exercise 4

Assume that the following 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 the movie Avatar. Please clearly state any assumptions that you needed to make in the proof.

Note

In the question above, we have color-coded the important predicates and constants in the logical statements above. We will not do this in the future and this is something you will have to identify on your own.

Proof Idea

Since we are using proof by contradiction, we assume that Jake Sully is NOT alive at the end of the movie Avatar. Using that as a premise (and statements in the problem we are given to be true), we will show that one of the problem's assumptions must be false, leading to a contradiction.

Proof Details

Assume the opposite of what you are trying to prove. Assume that Jake Sully is NOT alive at the end of the movie Avatar.

Assuming that Jake Sully is dead at the end of the movie Avatar, then we must assume that Jake Sully is not the hero of Avatar since the hero in a movie never dies.

In order to prove that Avatar has a hero at all, we need to show that show that Avatar is a blockbuster movie. Since the highest grossing movie ever is a blockbuster, and the movie Avatar has made the most money ever, we can conclude that it must have a hero, but that hero can not be Jake Sully from our previous assumption.

We know that Neytiri is the heroine of Avatar and that the heroine always dates the hero. Since Jake Sully is not the hero of Avatar, we can assume that Neytiri is not dating Jake Sully. This directly contradicts the statement from the problem’s assumptions: “Jake Sully and Neytiri are dating.” This results in a contradiction and our initial assumption must be false, so we know that Jake Sully must be alive at the end of Avatar.

Further Reading