Problems

Imagine you see a really huge party bus pulling out, an infinite bus with no seats. Instead everyone on board is identified by their unique name, which is an infinite sequence of \(0\)s and \(1\)s. The bus has every person named with every possible infinite sequence of \(0\)s and \(1\)s, someone is named \(00010000..00...\), someone else \(0101010101...\), and so on. Prove that this time you will not be able to accommodate all the new guests no matter how hard you try.

Prove that the set of all real numbers is not countable.

Prove the triangle inequality: in any triangle \(ABC\) the side \(AB < AC+ BC\).

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}\]?

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.

Suppose that \(p\) is a prime number. How many numbers are there less than \(p^2\) that are relatively prime to \(p^2\)?