Nine pirates have captured a treasure chest. In order to protect it, they decide to lock it using multiple locks and distribute several keys for each of these locks among them, so that the chest can be opened only by a majority of the pirates. What is the minimum number of keys each of the pirates should get?
SOLUTION
First, we show that for every four pirates, there exists a lock which cannot be opened only by them and can be opened by everyone else. We choose an arbitrary group of four pirates. If they can open every lock, then they can access the treasure without the need of a majority. If any of the remaining pirates cannot open that lock, then he, together with the initial group of four still cannot access the treasure. Thus, the claim is proved and to each group of four pirates we can assign a unique lock. These are \binom{9}{4}=126 locks in total. Finally, every pirate should get keys for \binom{8}{4}=70 of these locks, one for each group of four additional pirates he can be a group of.
A hundred fish are swimming along a stream at different velocities. If one fish catches up to another fish, it eats it and continues swimming. What is the expected number of fish that will survive?
SOLUTION
Notice that the N-th fish in the stream survives if and only if it is the fastest among the first N fish. The probability of this event happening is equal to 1/N. Since the expected number of fish that survive is equal to the sum of the survival probabilities for each of them, the answer is 1+1/2+1/3+…+1/N.
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.
Please note:
This action will also remove this member from your connections and send a report to the site admin.
Please allow a few minutes for this process to complete.
