Problems

Tweedledum and Tweedledee were standing under a tree, each with an arm round the other’s neck. Last time Alice met them she knew immediately which was which, because one of them had “DUM” embroidered on his collar, and the other “DEE”. ‘No embroidery this time,’ she said to herself. ‘How do I distinguish them?’. ‘O, yes!’, she suddenly remembered that one of them always tells the truth, while the other always lies. ‘I have to ask one of them just one question, he will answer ‘yes’ or ‘no’, and I will know which is which’, she thought. What question was Alice going to ask?

Is “If you come here, then you are mad” the same thing as “If you are not mad, then you wouldn’t have come here”.

Is “if $x=y$ then $x^2=y^2$” the same thing as “if $x^2\ne y^2$ then $x\ne y$”?

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”?

Does the largest natural number exist?

The cat and Alice ate three cakes. Show that one of them ate at least two cakes.

You are given $11$ natural numbers. Show that you can choose two among those numbers such that the difference between the chosen numbers 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 \cdots \times 2\times 1$. Prove that if $n!+1$ is divisible by $n+1$, then $n+1$ is a prime number.