Grasshoppers

Four grasshoppers start at the ends of a square in the plane. Every second one of them jumps over another one and lands on its other side at the same distance. Can the grasshoppers after finitely many jumps end up at the vertices of a bigger square?

The answer is NO. In order to show this, assume they can and consider their reverse movement. Now the grasshoppers start at the vertices of some square, say with unit length sides, and end up at the vertices of a smaller square. Create a lattice in the plane using the starting unit square. It is easy to see that the grasshoppers at all times will land on vertices of this lattice. However, it is easy to see that every square with vertices coinciding with the lattice’s vertices has sides of length at least one. Therefore the assumption is wrong.

Missionaries, Cannibals

Three missionaries and three cannibals must cross a river with a boat which can carry at most two people at a time. However, if on one of the two banks of the river the missionaries get outnumbered by the cannibals, they will get eaten. How can all 6 men cross the river without anybody gets eaten?

Remark: The boat cannot cross the river with no people on board.

Label the missionaries M1, M2, M3 and the cannibals C1, C2, C3. Then:

1. M1 and C1 cross the river, M1 comes back.
2. C2 and C3 cross the river, C2 comes back.
3. M1 and M2 cross the river, M1 and C1 come back.
4. M1 and M3 cross the river, C3 comes back.
5. C1 and C2 cross the river, C1 comes back.
6. C1 and C3 cross the river.

Now, everyone is on the other side.

Friends and Enemies

Show that in each group of 6 people, there are either 3 who know each other, or 3 who do not know each other.

Let’s call the people A, B, C, D, E, F. Person A either knows at least 3 among B, C, D, E, F, or does not know at least 3 among B, C, D, E, F.

Assume the first possibility – A knows B, C, D. If B and C know each other, C and D know each other, or B and D know each other, then we find a group of 3 people who know each other. Otherwise, B, C, and D form a group in which no-one knows the others.

If A doesn’t know at least 3 among B, C, D, E, F, the arguments are the same.

Burn the Ropes

You have two ropes and a lighter. Each of the ropes burns out in exactly 60 minutes, but not at a uniform rate – it is possible for example that half of a rope burns out in 40 minutes and the other half in just 20. How can you measure exactly 45 minutes using the ropes and the lighter?

First, you light up both ends of the first rope and one of the ends of the second rope. Exactly 30 minutes later the first rope will burn out completely and then you have to light up the other end of the second rope. It will take 15 more minutes for the second rope also to burn out completely, for a total of 30 + 15 = 45 minutes.

Prisoners and Boxes

There are 100 inmates living in solitary cells a prison. In a room inside the prison there are 100 boxes and in each box there is a paper with some prisoner’s name (all different). One day the warden tells the prisoners that he has aligned next to the wall in a special room 100 closed boxes, each of them containing some prisoner’s name (all different). He will let every prisoner go to the room, open 50 of the boxes, then close them and leave the room the way it was, without communicating with anybody. If all prisoners find their names in the boxes they open, they will be set free, otherwise they will be executed. The prisoners are allowed to come up with a quick plan before the challenge begins. Can you find a strategy which will ensure a success rate of more than 30%?

The prisoners can assign numbers to their names – 1, 2, 3, … , 100. When prisoner X enters the room, he should open first the X-th box in the line. If he sees inside prisoner’s Y name, he should open next the Y-th box in the line. If he sees in it prisoner’s Z name, he should open next the Z-th box in the line and so on.

The only way which will prevent all prisoners from finding their names is if there is a long cycle of boxes (length 51 or more), such that the first box in the cycle directs to the second box in it, the second box to the third box, the third box to the fourth box and so on.

It is not hard to compute that the probability of having a cycle of length K>50 is exactly 1/K. Then the probability for failure will be equal to the sum 1/51 + 1/52 + … + 1/100, which is very close to ln(100) – ln(50) = ln(2) ~ 69%. Therefore this strategy ensures a success rate of more than 30%.

Four Chains

You have four metal chains and each of them has three links. What is the minimal number of cuts you need to make so that you can connect the chains into one loop with twelve links.

You need only three cuts – cut all of the links of one of the chains and then use them to connect the ends of the remaining three chains.

High Tide

A boat has a ladder with six rungs on it. The rungs are spaced one foot from each other, the lowest one starting a foot above the water. The tide rises with 10 inches every 15 minutes.

How many rungs will be still above the water 2 hours later?

Six rings – the ship and the ladder will be rising with the tide.