8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ There are irrationals $x, y$ such that $x^y \in \mathbb{Q}$. The proof by cases is not automatically apparent, in fact, what I have in mind is only the existence proof: Either $\sqrt{2}^\sqrt{2} \in \mathbb{Q}$, or it is irrational and can be raised to $\sqrt{2}$ to get $2 \in \mathbb{Q}$. $\endgroup$ – Benjamin Dickman Jun 15 '14 at 20:40
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Suppose otherwise, so $x_1+x_2>20$. Thus $x_3+x_4>20$, as well; then $x_5\geq x_4>10$. Therefore $\sum x_i > 20 + 20 + 10 = 50$. Contradiction. $\endgroup$ – Brendan W. Sullivan Jul 9 '14 at 17:35
  • 1
    $\begingroup$ My point is that, yes, this argument needs cases. (My claim that $x_3+x_4>20 \implies x_4>10$ does so implicitly.) But I think it's quite unintuitive to start with the cases as you did. I asked friends and they came up with essentially my argument. It's more natural to chase down the consequences of the assumptions and then realize that a mini "cases argument" is needed later on. $\endgroup$ – Brendan W. Sullivan Jul 9 '14 at 19:59
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Isn't the question asking for proofs? $\endgroup$ – JPBurke Jun 15 '14 at 17:44
  • $\begingroup$ I guess when I read "proof" I read it as statements that can be proved by cases. I can add a proof if the OP clarifies that he wants the actual proof (I know that's what @vonbrand said, but if he wants to come up with his own cases, I'll leave it without the proof for now). $\endgroup$ – ncr Jun 15 '14 at 18:22
  • $\begingroup$ Students often get the impression that a problem must be associated with a specific type of solution. This can interfere with problem solving as a practice, which either seeks not-previously-taught solutions to novel problems, or novel solutions to familiar problems. People may disagree with me on this, but I think it behooves us to be explicit that a proof is by case (or some other method) but that a statement or problem is not a proof by case example. Not only because the proof isn't there, but that we're talking about an approach, not a problem type. $\endgroup$ – JPBurke Jun 15 '14 at 18:31
  • 1
    $\begingroup$ I want to make it clear that my comment is not meant to say your answer is not valuable. And it may be exactly what vonbrand is looking for. I personally felt it was incomplete, and was an opportunity to make a point about math education and how we talk about problem types. Our (traditional) curriculum is very programmed in this way. I think it helps to be aware of it, even in situations like this. $\endgroup$ – JPBurke Jun 15 '14 at 18:34
  • $\begingroup$ Thanks, folks. I don't need the actual proofs, I'll have to look them up, check different alternatives and write them up for myself anyway. $\endgroup$ – vonbrand Jun 18 '14 at 1:57
1
$\begingroup$

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$

$\endgroup$
1
$\begingroup$
  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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.