Problems

Age
Difficulty
Found: 1986

In good conditions, bacteria in a Petri cup spread quite fast, doubling every second. If there was initially one bacterium, then in \(32\) seconds the bacteria will cover the whole surface of the cup.

Now suppose that there are initially \(4\) bacteria. At what time will the bacteria cover the surface of the cup?

A piece containing exactly \(4\) black cells is cut out from a regular \(8\) by \(8\) chessboard. You are only allowed to cut along the edges of the cells and the piece must be connected - namely you cannot have cells attached only with a vertex, they have to share a common edge.

Find the largest possible area of such a piece.

In a distant village, there are \(3\) houses and \(3\) wells. Inhabitants of each house want to have access to all \(3\) wells. Is it possible to build non-intersecting straight paths from each house to each well? All houses and well must be level (that is, none of them are higher up, like on a mountain, nor are any of them on lower ground, like in a valley).

Find all \(n\) such that a closed system of \(n\) gears in a plane can rotate. We call a system closed if the first gear wheel is connected to the second and the \(n\)th, the second is connected to the first and the third, the third is connected to the second and the fourth, the fourth is connected to the third and the fifth, and so on until the \(n\)th is connected to the \(n-1\)th and the first. In the picture, we have a closed system of three gears.

image

Show that there are no rational numbers \(a,b\) such that \(a^2 + b^2 = 3\).

There are infinitely many couples at a party. Each pair is separated to form two queues of people, where each person is standing next to their partner. Suppose the queue on the left has the property that every nonempty collection of people has a person (from the collection) standing in front of everyone else from that collection. A jester comes into the room and joins the right queue at the back after the two queues are formed.

Each person in the right queue would like to shake hand with a person in the left queue. However, no two of them would like to shake hand with the same person in the left queue. If \(p\) is standing behind \(q\) in the right queue, \(p\) will only shake hand with someone standing behind \(q\)’s handshake partner. Show that it is impossible to shake hands without leaving out someone from the left queue.

Suppose \(x,y\) are real numbers such that \(x < y + \varepsilon\) for every \(\varepsilon > 0\). Show that \(x \leq y\).

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.

Could you meet a person inhabiting this planet who asks you “Am I a Goop?"