There is a perfectly spherical apple with a radius 50mm. A worm has entered the apple, made a tunnel of length 99mm through it and left. Prove that we can slice the apple in two pieces through the center, so that one of them is untouched by the worm.
SOLUTION
Let the entering point is A, the leaving point is B and the center of the apple is C. Consider the plane P containing the points A, B and C and project the worm’s tunnel on it. Since 99 < 2×50, the convex hull of the tunnel’s projection will not contain the center C. Therefore we can find a line L through C, such that the tunnel’s projection is entirely in one of the semi-planes of P with respect to L. Now cut the apple with a slice orthogonal to P passing through the line L and you are done.
A hundred prisoners are locked up in a prison. The warden devises the following game: he writes 100 different numbers on the foreheads of the prisoners. Then, each of the prisoners inspects the numbers on the foreheads of the others and decides to put either a black or a white hat on his head. Once the prisoners put their hats on, the warden arranges them in a line according to the numbers on their foreheads, starting with the lowest one and ascending to the highest one.
If the hats in the resulting line alternate their colors, then the prisoners will be set free. If not, the prisoners will be executed.
Can the prisoners devise a strategy that will guarantee their freedom?
SOLUTION
Once the warden writes the numbers on the prisoners’ foreheads, they form a mental circle, arranging themselves alphabetically in it (or according to any other order they agree on). They include the warden in this mental circle and imagine he has infinity written on his forehead.
Then, each prisoner examines the sequence of 100 numbers written on the foreheads of the others, and computes the number of inversions, i.e. the pairs which are not in their natural order. The prisoners which count an even number of permutations put black hats on, and the prisoners that count an odd number of permutations put white hats on. The infinity symbol is treated as the largest number in the sequence.
For example, if a prisoner sees the sequence {2, -6, 15.5, ∞, -100, 10}, then he counts seven inversions, which are the pairs (2, -6), (2, -100), (-6, -100), (15.5, -100), (15.5, 10), (∞, -100), (∞, 10), and puts a white hat on.
Next, we prove that the devised strategy works. We consider two prisoners, P1 and P2, who are adjacent in the final line the warden forms. These two prisoners split the mental circle in two arcs: A and B.
The number of inversions P1 counts is:
I_1 = I(A)+I(B)+I(A,B)+I(A, P_1) + I(P_1, B),
where I(X) denotes the number of inversions in a sequence X, and I(X, Y) denotes the number of inversions in a pair of sequences (X, Y):
I(X) = \|x_i, x_j \in X : \quad i < j, \quad x_i > x_j\| \\
I(X, Y) = \|x \in X, y \in Y : \quad x > y\|
Similarly, the number of inversions P2 counts is:
I_2 = I(A) + I(B) + I(B, A) + I(B, P_2) + I(P_2, A)
We sum I_1 and I_2 to get:
\begin{align*}
I_1 + I_2 &= 2I(A) + 2I(B) + I(A, B) + I(B, A) \\
&+ I(A, P_1) + I(P_2, A) + I(P_1, B) + I(B, P_2) \\
&= 2(I(A) + I(B)) + \|A\|\|B\|+\|A\|+\|B\|
\end{align*}
Since \|A\| + \|B\| = 99 is an odd number, we see that I_1+I_2 is also odd. Therefore, one among P1 and P2 would have counted an even number of inversions, and one would have counted an odd number of inversions. Thus, their hats have alternating colors.
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?
SOLUTION
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.
They start with 10 nodes on a sheet of paper and, taking turns, connect any two of them which are not already connected with an edge. The first player to make the resulting graph connected loses.
Who will win the game?
Remark: A graph is “connected” if there is a path between any two of its nodes.
SOLUTION
The first player has a winning strategy.
His strategy is with each turn to keep the graph connected, until a single connected component of 6 or 7 nodes is reached. Then, his goal is to make sure the graph ends up with either connected components of 8 and 2 nodes (8-2 split), or connected components of 6 and 4 nodes (6-4 split). In both cases, the two players will have to keep connecting nodes within these components, until one of them is forced to make the graph connected. Since the number of edges in the components is either C^8_2+C^2_2=29, or C^6_2+C^4_2=21, which are both odd numbers, Player 1 will be the winner.
Once a single connected component of 6 or 7 nodes is reached, there are multiple possibilities:
The connected component has 7 nodes and Player 2 connects it to one of the three remaining nodes. Then, Player 1 should connect the remaining two nodes with each other and get an 8-2 split.
The connected component has 7 nodes and Player 2 connects two of the three remaining nodes with each other. Then, Player 1 should connect the large connected component to the last remaining node and get an 8-2 split.
The connected component has 7 nodes and Player 2 makes a connection within it. Then, Player 1 also must connect two nodes within the component. Since the number of edges in a complete graph with seven nodes is C^7_2=21, eventually Player 2 will be forced to make a move of type 1 or 2.
The connected component has 6 nodes and Player 2 connects it to one of the four remaining nodes. Then, Player 1 should make a connection within the connected seven nodes and reduce the game to cases 1 to 3 above.
The connected component has 6 nodes and Player 2 connects two of the four remaining nodes. Then, Player 1 should connect the two remaining nodes with each other. The game is reduced to a 6-2-2 split which eventually will turn into either an 8-2 split, or a 6-4 split. In both cases Player 1 will win, as explained above.
Napoleon has landed on a deserted planet with only two policemen on it. He is traveling around the planet, painting a red line as he goes. When Napoleon creates a loop with red paint, the smaller of the two encompassed areas is claimed by him. The policemen are trying to restrict the land Napoleon claims as much as possible. If they encounter him, they arrest him and take him away. Can you prove that the police have a strategy to stop Napoleon from claiming more than 25% of the planet’s surface?
We assume that Napoleon and the police are moving at the same speed, making decisions in real time, and fully aware of everyone’s locations.
SOLUTION
First, we choose an axis, so that Napoleon and the two policemen lie on a single parallel. Then, the strategy of the two policemen is to move with the same speed as Napoleon, keeping identical latitudes as his at all times, and squeezing him along the parallel between them.
In order to claim 25% of the planet’s surface, Napoleon must travel at least 90°+90°=180° in total along the magnitudes. Therefore, during this time the policemen would travel 180° along the magnitudes each and catch him.
There are 7 loaves of bread that need to be shared equally among 12 people. How would you do this if you are not allowed to split any loaf into 12 pieces?
SOLUTION
Split 4 of the loaves into 3 pieces and the other 3 loaves into 4 pieces. Then, give each person one of both types of pieces.
A thousand people stand in a circle in order from 1 to 1000. Number 1 has a sword. He kills the next person (Number 2) and gives the sword to the next living person (Number 3). All people keep doing the same until only one person remains. Which number survives?
SOLUTION
First, we note that if the number of people is a power of 2, then the first person will survive every round. The greatest power of 2 that is less than 1000 is 512. Therefore, after 488 people die, there will be 512 remaining and the first one to kill the 489-th person will survive. This person has number 1+2×488=977.
A string is wound around a circular rod with circumference 10 cm and length 30 cm. If the string goes around the rod exactly 4 times, what is its length?
SOLUTION
Imagine the circular rod is actually a paper roll and the string is embedded inside the paper. When we unroll it, we get a paper rectangle 30cm×40cm with the string embedded along the diagonal. Using the Pythagorean theorem, we find that the length of the string is 50cm.
You are lost in the middle of a forest, and you know there is a straight road exactly 1 km away from you, but not in which direction. Can you find a path of distance less than 640 m which will guarantee you to find the road?
SOLUTION
Imagine there is a circle with a radius of 100 m around you, and you are at its center O. Let the tangent to the circle directly ahead of you be t. Then, follow the path:
Turn left 30 degrees and keep walking until you reach the tangent t at point A for a total of 100×2√3/3 meters, which is less than 115.5 meters.
Turn left 120 degrees and keep walking along the tangent to the circle until you reach the circle at point B for a total of 100×√3/3 which is less than 58 meters.
Keep walking around the circle along an arc of 210 degrees until you reach point C for a total of 100×7π/6 which is less than 366.5 meters.
Keep walking straight for 100 meters until you reach point D on the tangent t.
An ant is positioned at one of the vertices of a cube and wants to get to the opposite vertex. If the edges of the die have length 1, what is the shortest distance the ant needs to travel?
SOLUTION
We unfold a cube to get a cross-shaped figure. Then, the problem is to find the shortest path between two points separated by a horizontal distance of 2 units and a vertical distance of 1 unit.
It is easy to see that the path in question is the one passing through the middle of the edge between the start and end points, and which has a distance of √5.
