Jason has \(20\) red balls and \(14\) bags to store them. Prove that there is a bag, which contains at least two balls.
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. Prove that 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?
There are \(24\) children in the class and some of them are friends with each other. The following rules apply:
If someone (say Alice) is a friend with someone else (say Bob), then the second student (Bob) is also a friend with the first (Alice).
If Alice is friend with Bob and Bob is friend with Claire, then Alice is also friend with Claire.
Find a misconception in the following statement: under the above conditions Alice is friend with herself.
Theorem: All people have the same eye color.
"Proof" by induction: This is clearly true for one person.
Now, assume we have a finite set of people, denote them as \(a_1,\, a_2,\, ...,\,a_n\), and the inductive hypothesis is true for all smaller sets. Then if we leave aside the person \(a_1\), everyone else \(a_2,\, a_3,\,...,\,a_n\) has the same color of eyes and if we leave aside \(a_n\), then all \(a_1,\, a_2,\,a_3,...,\,a_{n-1}\) also have the same color of eyes. Thus any \(n\) people have the same color of eyes.
Find a mistake in this "proof".
Let’s prove that \(1\) is the largest natural number.
Let \(n\) be the largest natural number. Then, \(n^2\), being a natural number, is less than or equal to \(n\). Therefore \(n^2-n=n(n-1)\leq 0\). Hence, \(0\leq n\leq 1\). Therefore \(n=1\).
Recall that \((n+1)^2=n^2+2n+1\) and after expansion we get \((n+1)^2-(2n+1)=n^2\). Subtract \(n(2n+1)\) from both sides \((n+1)^2-(2n+1)-n(2n+1)=n^2-n(2n+1)\) and rewrite it as \((n+1)^2-(n+1)(2n+1)=n^2-n(2n+1)\).
Now we add \(\frac{(2n+1)^2}{4}\) to both sides: \((n+1)^2-(n+1)(2n+1)+\frac{(2n+1)^2}{4}=n^2-n(2n+1)+\frac{(2n+1)^2}{4}\).
Factor both sides into square: \(((n+1)-\frac{2n+1}{2})^2=(n-\frac{2n+1}{2})^2\).
Now take the square root: \((n+1)-\frac{2n+1}{2}=n-\frac{2n+1}{2}\).
Add \(\frac{2n+1}{2}\) to both sides and we get \(n+1=n\) which is equivalent to \(1=0\).
Let’s prove that \(1=2\). Take a number \(a\) and suppose \(b=a\). After multiplying both sides we have \(a^2=ab\). Subtract \(b^2\) from both sides to get \(a^2-b^2=ab-b^2\). The left hand side is a difference of two squares so \((a-b)(a+b)=b(a-b)\). We can cancel out \(a-b\) and obtain that \(a+b=b\). But remember from the start that \(a=b\), so substituting \(a\) for \(b\) we see that \(2b=b\), dividing by \(b\) we see that \(2=1\).
John drunk a \(\frac16\) of a full cup of black coffee and then filled the cup back up with milk. Then he drunk a third of what he had in the cup. Then, he refilled it back to full with milk again, and after that, drunk a half of the cup. Finally, he once again refilled the cup with milk and drunk everything he had. What did he drink more of - coffee or milk?
A round necklace contains \(45\) beads of two different colours: red and blue. Show that it is possible to find two beads of the same colour next to each other.