One of the most useful tools for proving mathematical statements is the Pigeonhole principle. Here is one example: suppose that a flock of \(10\) pigeons flies into a set of \(9\) pigeonholes to roost. Because there are \(10\) pigeons but only \(9\) pigeonholes, at least one of these \(9\) pigeonholes must have at least two pigeons in it.
Show the following: Pigeonhole principle strong form: Let \(q_1, \,q_2,\, . . . ,\, q_n\) be positive integers. If \(q_1+ q_2+ . . . + q_n - n + 1\) objects are put into \(n\) boxes, then either the \(1\)st box contains at least \(q_1\) objects, or the \(2\)nd box contains at least \(q_2\) objects, . . ., or the \(n\)th box contains at least \(q_n\) objects.
How can you deduce the usual Pigeonhole principle from this statement?
Each integer on the number line is coloured either yellow or blue. Prove that there is a colour with the following property: For every natural number \(k\), there are infinitely many numbers of this colour divisible by \(k\).
Let \(r\) be a rational number and \(x\) be an irrational number(i.e. not a rational one). Prove that the number \(r+x\) is irrational.
If \(r\) and \(s\) are both irrational, then must \(r+s\) be irrational as well?
Definition: We call a number \(x\) rational if there exist two integers \(p\) and \(q\) such that \(x=\frac{p}{q}\). We assume that \(p\) and \(q\) are coprime.
Prove that \(\sqrt{2}\) is not rational.
Let \(n\) be an integer. Prove that if \(n^2\) is divisible by \(2\), then \(n\) is divisible by \(2\).
Let \(n\) be an integer. Prove that if \(n^3\) is divisible by \(3\), then \(n\) is divisible by \(3\).
The numbers \(x\) and \(y\) satisfy \(x+3 = y+5\). Prove that \(x>y\).
The numbers \(x\) and \(y\) satisfy \(x+7 \geq y+8\). Prove that \(x>y\).
There exist various ways to prove mathematical statements, one of the possible methods, which might come handy in certain situations is called Proof by contradiction. To prove a statement we first assume that the statement is false and then deduce something that contradicts either the condition, or the assumption itself, or just common sense. Thereby concluding that the first assumption must have been wrong, so the statement is actually true.