Problems
In certain kingdom there are a lot of cities, it is known that all the distances between the cities are distinct. One morning one plane flew out of each city to the nearest city. Could it happen that in one city landed more than \(5\) planes?
There are various ways to prove mathematical statements. One of the possible methods which might come in 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. Due to the contradiction, we have to conclude that the first assumption must have been wrong, so the statement is actually true.
A closely related method is called contrapositive proof. An example should make the idea quite clear. Consider the statement “if the joke is funny, then I will be laughing". Another completely equivalent way of saying it would be “if I am not laughing, then the joke is not funny". The second statement is known as the contrapositive of the first statement.
We can often prove a statement by proving its contrapositive. Many statements are proven by deriving a contradiction. However, one can often rewrite them as either a direct proof or a contrapositive proof.
Let’s take a look at both of these techniques.
Today we will solve some logic problems. This time, we are visiting a strange planet. This planet is inhabited by two kinds of aliens, Cricks and Goops. The physical differences between them are not enough for a human being to distinguish them, but they have another remarkable feature. They can only ask questions. Cricks can only ask questions whose answer is yes, while Goops can only ask questions whose answer is no.
In this sheet, we will look at basic counting problems. The fundamental principle is quite simple. If you have two independent choices to make, then the number of options for making both choices is calculated by multiplying the number of options for each choice.
An issue we frequently run into is that of overcounting. This means we count the same thing more than once. In the examples and problems today, you will see various ideas that we can use to correct for overcounting, or for avoiding it.
From the examples above, we see that we often need to pick \(k\) objects from \(n\) objects where the order of the \(k\) objects is ignored. The number of ways to pick them is notated with the special symbol \(\binom{n}{k}\), pronounced “\(n\) choose \(k\)". What’s a formula for \[\binom{n}{k}\]?
The pigeonhole principle is often called “Dirichlet’s box principle". Dirichlet made good use of this tool to show a fundamental result in Diophantine approximation, now commonly known as the Dirichlet Approximation Theorem. You will now prove it yourself!
Suppose \(\alpha\) is any irrational real number and \(N\geq 1\) is any positive integer. Show that there is an integer \(1\leq q\leq N\) and an integer \(p\) such that \[\left| q \alpha - p \right| < \frac{1}{N}.\]
Find the mistake in the sequence of equalities: \(-1=(-1)^{\frac{2}{2}}=((-1)^2)^{\frac{1}{2}}=1^{\frac{1}{2}}=1\).
A circle with center \(A\) is inscribed into a square \(CDFE\). A line \(GH\) intersects the sides \(CD\) and \(CE\) of the square and is tangent to the circle at the point \(I\). Find the perimeter of the triangle \(CHG\) (the sum of lengths of all the sides) if the side of the square is \(10\)cm.
The triangle visible in the picture is equilateral. The hexagon inside is a regular hexagon. If the area of the whole big triangle is \(18\), find the area of the small blue triangle.
In a pentagon \(ABCDE\), diagonal \(AD\) is parallel to the side \(BC\) and the diagonal \(CE\) is parallel to the side \(AB\). Show that the areas of the triangles \(\triangle ABE\) and \(\triangle BCD\) are the same.
