What is common between the two examples above? In fact, if you want to know some fancy words (you should understand what they mean, of course), we just stated that a direct proof and a proof by contrapositive is the same thing. In simple words it means that “If A then B” is the same thing as “If not B, then not A”.
A proof by contrapositive can be very useful. In some problems it is much easier to prove “If not B, then not A” compare to “If A then B”. Let’s consider another example, where a proof by contrapositive can be very useful
There are 10 lines drawn on the plane, all intersecting at the same point. Show that there will be at least two lines with angle between them less than \(18^o\).
Is “If you are not mad, then you growl when you are angry and wag your tail when you are pleased” the same thing as “If you don’t growl when you are angry or don’t wag your tail when you are pleased, then you are mad”?
The cat and Alice ate three cakes. Show that one of them ate at least two cakes.
You are given at least \(11\) natural numbers. Show that you can choose two among those numbers such that their difference is divisible by \(10\).
A rectangle \(5 \times 9\) is cut into 10 small rectangles with sides of integer lengths. Show that there are two identical rectangles among them.
Let \(n!= n\times (n-1) \times(n-2)\times \dots \times 2\times 1\). Prove that if \(n!+1\) is divisible by \(n+1\), then \(n+1\) is a prime number.
Denote by \(\overline{ab} = 10a +b\) the two-digit number whose first and second digits are \(a\) and \(b\) respectively. Do there exist two \(2\)-digit numbers \(\overline{ab}\) and \(\overline{cd}\) such that \(\overline{ab} \times \overline{cd} = \overline{abcd}\)? (Here \(\overline{abcd}\) is a four-digit number with digits \(a\), \(b\), \(c\) and \(d\), i.e. \(\overline{abcd} = 1000a + 100b +10c +d\).)
Sixty children came to the maths circle. Among any group of ten children, there are always at least three who go to the same school. Prove that there must be at least fifteen children from one school among all sixty who came to the maths circle.
The people of Wonderland are having an election. Each voter writes the names of 10 candidates on their ballot paper (they cannot write the same name twice on their ballot paper).
There are 11 ballot boxes in total and each ballot box has at least one ballot paper inside. The March Hare, who is counting the votes, notices something:
If he takes one ballot paper from each ballot box (so 11 ball together), there will always be at least one candidate whose name appears on all 11 of those papers.
Prove that there is at least one ballot box and a candidate’s name such that every ballot paper on that box contains the name of that candidate.