Nice examples of proofs by cases?

Question

The setting is undergraduate students in Computer Science, a course in Discrete Mathematics (first proof-oriented course they take, they had a mostly computation oriented first course in calculus).

As examples I need nice proofs using cases, where the cases aren't automatically apparent (i.e., this mostly rules out proofs with absolute values). The restriction is also that not much more than high-school algebra (and perhaps a dash of common sense) is required.

Bonus points for proofs that aren't obviously "mathematical" (i.e., not algebra, no formulas).

Answer 1

Suppose that $x_1,\dots, x_5$ are numbers such that $x_1\le x_2\le x_3\le x_4\le x_5$ and $x_1+x_2+x_3+x_4+x_5=50$. Prove that $x_1+x_2\le 20$.

Proof: We consider the cases $x_2\le 10 $ and $x_2>10$. If $x_2\le 10$ then the conclusion is obvious. If $x_2>10$ then $x_3+x_4+x_5>30$ so $x_1+x_2<20$.

It's not so easy to prove this without cases.

Answer 2

Suppose any two people at a party have either met or not. If every pair of people in a group has met, we’ll call the group a club. If every pair of people in a group has not met, we’ll call it a group of strangers. Prove: Any six people at the party includes a club of 3 people or a group of 3 strangers.

Answer 3

I recommend the Hall's theorem which has a nice inductive proof by cases (some people like to call it "either it's trivial or it's trivial").

The formal wording is like this:

Let $G$ be a bipartite graph with bipartition $U \uplus V$ and denote by $\mathcal{N}(S)$ the set of neighbors of vertices in $S$. Then, there is a $U$-saturating matching in $G$ if and only if $$\forall S \subseteq U.\ |\mathcal{N}(S)| \geq |S| .$$

However, this can be rephrased in more friendly terms, for example:

Suppose there are two groups of girls and boys respectively, both with the same count. For any boy and girl (i.e. any potential pair) they would like to dance together or not. There is a perfect pairing (everybody has a dance partner) if and only if for any subset of boys there is at least the same number of girls willing to dance with them.

The proof proceeds by induction on the size of the set $U$ and the inductive step has two cases:

• $\forall \varnothing \neq S\subsetneq U.\ |\mathcal{N}(S)| \color{red}{>} |S|.$ In this case we match any pair and the pairing for the rest follows from inductive hypothesis.
• $\exists \varnothing \neq S \subsetneq U.\ |\mathcal{N}(S)| \color{red}{=} |S|.$ In this case let $S$ be such a set which is minimal with regard to inclusion. We split vertices of $G$ into $G_1$ and $G_2$ so that $U(G_1) = S$, $V(G_1) = \mathcal{N}(S)$ and by induction hypothesis each part has its own matching.

I hope this helps $\ddot\smile$

Answer 4

1. How about the proof $f(x)=2x^2+x+1$ has no zero in $\mathbb{Z}/3\mathbb{Z}$. Using modular arithmetic with $n=3$, $$ f(0)=1, \ \ \ f(1)=2+1+1=1, \ \ \ f(2) = 2(4)+2+1=2.$$ thus, $f(x)=2x^2+x+1$ has no zero in $\mathbb{Z}/3\mathbb{Z}$.
2. Another stub of an idea I had: Truth table arguments involve multiple cases. The proof technique is perhaps not so exciting, so perhaps you could combine the truth table proof with the method for finding a minimal expression which represents the logic. In particular, show them Karnaugh Maps.