We proved that the Ö 2 is irrational early on in class. For that proof, we used the method of reductio ad absurdum, or proof by contradiction. A beautiful example of argument by cases:

C

Proves something amazing about irrational numbers and exponentiation. The claim is this:

Claim: There exist irrational numbers b,c such that b^c is rational.

Whats amazing is that we don’t have to provide an example of b and c to prove the claim. We reason this way:

Another nice example of argument by cases is the Clusters of Friends or Enemies problem.

Suppose you are in a suite with 5 other people, each of whom is either your friend or your enemy, as well as friends or enemies with each other. The claim to be proved is this: although there are 215 (approx. 32,000) different patterns of possible social arrangements just among the 6 of you, in all of them there is some cluster of 3 people who are all friends or all enemies. A cluster that is all friends or all enemies is called a clique. How could you prove this? One way is to enumerate all possible cases, and check each one to make sure there was a clique in each. But that would be daunting and it is doubtful anyone could do it reliably. Perhaps a machine could be programmed to check. But consider the following simple argument that serves just as well.

1) Consider your relationships with the other 5 people. Either 1A) at least three of them are your friends, or 1B) at least three of them are your enemies.

Case 1A) Say person1, person2, and person3 are your friends. Then 2A) either person1 and person2 are friends, or 2B) they are enemies.

So in every possibility under case 1A, there is a three person cluster of all friends or all enemies.

Case 1B) Similar reasoning.

----------

I have indented the cases to make the structure of assumptions easier to follow. Consider the following diagram, which makes things easier still. As soon as I hit a clique, I label it under the hypothetical box. You can see that under the left side, all leaves (bottom nodes) have cliques.