You need to turn over the ace and the red-backed card:

• If the ace doesn’t have a black back, the rule is broken.
• If the red-backed card is an ace, the rule is also broken.

Note that both the face-down card with a black back and the queen can have anything on the other side without violating the rule.

Commentary

This is also known as the Wason selection task.

Out of the 5 drawn cards, the assistant chooses 2 cards which have the same suit.

Represent the value of the cards as their face value, with Ace=1, Jack=11, Queen=12, King=13.

Call the difference between the values of the two cards \(d\). Out of the two chosen cards, if the \(d > 6\) then select the highest value card; otherwise select the lowest value card.

Pass the selected card back to the audience. Put the other card down on the table - this will form the bottom of the pile for the magician.

Use the 3 remaining cards to encode a value, \(p\). If \(d \le 6\) then set \(p = d\), otherwise set \(p = 13 - d\). Place the 3 cards on the pile.

The magician can now look at the pile. From the bottom card in the pile the magician knows the suit of the selected card.

Let the value of the bottom card be \(v\). From looking at the order of the 3 top cards the magician can determine \(p\). If \(p + v < 13\) then the value of the selected card is \(p + v\) otherwise it is \(p + v - 13\).

Proof

It will always be the case there there are 2 cards of the same suit in the 5 drawn cards because there are only 4 suits (by the pigeon-hole principle).

Call the values of the 2 cards with the same suit \(v_1\) and \(v_2\) such that \(v_1 < v_2\). It is the case that either \(v_1 + p = v_2\) or \(v_2 + p \equiv v_1 \pmod{13}\) for some \(0 < p \le 6\).

If it was the case that \(v_1 + p = v_2 \text{ s.t. } 6 < p < 13\) then we could write it equivalently as \(v_1 + 13 - p \equiv v_2 \pmod{13} \text{ s.t. } 0 < 13 - p \le 6\).

Let \(d = v_2 - v_1\) (i.e. the difference between the values). If \(d \le 6\) then \(p = d\), otherwise \(p = 13 - d\) as in the description of the trick.

There are 6 possible values for \(p\): 1, 2, 3, 4, 5 and 6. We can encode \(3! = 6\) numbers by controlling the order of 3 cards. Thus we are able to encode \(p\) with the order of our three remaining cards.

The maximum size deck the trick can be performed with is 124.

In the general case the audience member draws \(n\) cards, we select one, and use the other \(n - 1\) cards to tell the magician the selected card. Here the maximum sized deck is \(n! + n - 1\) cards.

Algorithm

We will use the following definitions:

• Let the size of the deck be \(N = n! + n - 1\).
• Let the cards in the deck be represented by numbers from \(0\) to \(N - 1\).
• Let \(c_i\) be the values of the cards drawn by the audience member such that \(0 \le i < n \text{ and } c_i < c_{i+1}\).
• Let \(c_i^\prime\) be the values of the cards seen by the magician such that \(0 \le i < n - 1 \text{ and } c_i^\prime < c_{i+1}^\prime\).
• Let \(s = \left(\sum c_i\right) \mod n\).
• Let \(s^\prime = \left(\sum c_i^\prime\right) \mod n\).
• Let \(p = \left\lfloor \frac{c_s - s}{n} \right\rfloor\).

Choose \(c_s\) as the selected card.

Encode \(p\) as a permutation of the \(n - 1\) remaining cards, and set them in an pile.

The magician then looks at the pile and calculates \(p\) from the permutation of the cards in the pile and \(s^\prime\) from the sum of the cards in the pile. From that the magician calculates the value:

The magician then can claim that \(c_s\) is the \(\chi\)th card which is not in the pile (not in \(c_i^\prime\)). Formally:

Proof of correctness

We will split this proof into two parts. The first will prove that assistant will be able to follow the instructions, and the second part will prove that the magician can correctly guess the selected card.

Choosing \(c_s\) and \(p\)

There are at least \(n - s\) cards greater than or equal to \(c_s\): \(\{c_i \mid s \le i < n\}\).

There are at least \(s\) cards smaller than \(c_s\): \(\{c_i \mid 0 \le i < s\}\).

We can now see from the definition of \(p\) that \(0 \le p < (n - 1)!\) and therefore \(p\) can be encoded as a permutation of \(n - 1\) cards. In addition, \(s\) is a number taken modulo \(n\) thus \(0 \le s < n\) and therefore it is always possible to select a card \(c_s\).

Determining \(c_s\)

Define \(q\) and \(r\) as follows:

Using the definition of \(s\) and \(s^\prime\):

Rearranging to solve for \(q\) we find that:

Substituting our calculated values for \(q\), \(r\) and using the equation for \(\chi\):

Given this it is sufficient to show that \(k = s\) is a unique solution to the equation for \(c_s\) used by the magician.

Let \(k = s + \Delta\):

Only the \(\Delta = 0\) case is true and therefore \(k = s\) is the unique solution. Thus the magician correctly calculates \(c_s\).

Proof of optimality

The maximum number of different messages we can send the magician is limited by \(n!\). We have two choices:

• The card to select of which there are \(n\) options.
• The order of the remaining \(n - 1\) cards of which there are \((n - 1)!\) options (permutations).

This gives a total of \(n (n - 1)! = n!\) options. In addition, the magician will be able to see the \(n - 1\) cards in the pile.

This results in a upper-bound for the card deck of \(N = n! + n - 1\) cards.

Use the following strategy:

• Keep the first card if it is 10 or greater, otherwise go to the second.
• Keep the second card if it is 9 or greater, otherwise go to the third.
• Keep the third card if it is 8 or greater, otherwise choose the fourth.

This will come out on ahead, on average.

Proof

Let us initially assume that there is an infinite deck for simplicity. There are an equal number of all face values, and now each card is independent of the previous ones.

For the 4th card the expected value is:

For the 3rd card, if it is more than \(E_4\), we should keep it. Otherwise, look at the fourth. Thus the expected value is:

Likewise for the 2nd card, if it is more than \(E_3\), we should keep it. Otherwise, look at the third, giving the expected value is:

And finally, for the first card:

Thus our strategy gives us an expected value of $10.138 per game. Note that we assumed that there was an infinite number of cards. In reality, when a card is chosen, it wont appear again. Since we only reject low cards, this reduces our chances of getting more low cards. Thus our proof gives a lower bound on the expected value

This gives us an expected value of \(> $10\), letting you come out ahead.

In general, our strategy generalises to \(n\) initial cards with:

The following hands result in Tex drawing dead:

Proof

Tex can’t win on a pair because P3 already has a higher pair (pair of As). In addition, no pair of As can come out on the board because all As are accounted for.

Tex can’t win on a three-of-a-kind because all the other K are accounted for. Three of any other card would result in a full house discussed later.

Tex can’t win on a straight. If 2 to 6 comes up on the board, P5 and P6 split the pot because they both will have 3 to 7 straights. If 8 to Q comes up on the board, P2 will win with a 10 to A straight. No other straights can come up on the board.

Tex can’t win on a flush. All the As are accounted for by other players, so they will have a higher flush than anyone.

Tex can’t win on a full house. If three of some card come up on the board, P3 will win with a higher full house. Tex can’t get another K as they are all accounted for.

Tex can’t win on a four-of-a-kind. If a four-of-a-kind comes up on the board P1, P2 and P2 will split the pot because all have the highest kicker, A. Tex can’t get four Ks as all the other Ks are accounted for.

Select the last (52nd) card.

Proof

Each position has an equal chance of being a black ace (since the deck is well shuffled). However, for all but the last card, some of the probability is that it is the first black ace. Thus the last card has the highest probability of being the second black ace.

\(2 \pi \approx 6.28\) meters of rope is required.

Proof

Let \(c\) be the original length of rope, \(r\) the radius of the earth.

Let \(\Delta c\) and \(\Delta r\) be the added rope and radius respectively.

Thus the change in the length of rope is \(2 \pi \Delta r\) regardless of the original radius! In our problem \(\Delta r = 1\) m.

Adding 0.75 mm is sufficient to lift the rope up 1m!

Proof

The length of the rope can be given by \(2 (\pi - \alpha) r + 2d\), thus the extra rope required is:

\(\Delta c = 2 (\pi - \alpha) r + 2d - 2 \pi r = 2 d - 2 \alpha r\) where \(\alpha = \arctan\left(\frac{d}{r}\right)\)

We can calculate \(d\) using Pythagoras’ forumla:

Combining:

Using \(r = 6378 \text{ km}\) and \(h = 0.001 \text{ km}\):

The belt can be divided into straight and curved sections. The lengths of the straight sections are the same as the distances between the centers of the pulleys, and the curved sections total one complete circumference. So the total length is \(3 + 4 + 6 + \pi \approx 16.1\) m.

We can trivially do better by cutting an X through the plot, cutting lines from opposite corners. This gives a length of \(2 \sqrt{2} \approx 2.83\) km.

We can do better by cutting two adjacent sides, then cutting a line from the opposite corner to the center. This gives a length of \(2 + \frac{\sqrt{2}}{2} \approx 2.71\) km.

We can improve this slightly by bringing in the two lines along the side until they meet at 120 degrees:

The short diagonal has a length of \(a = \frac{\sqrt{2}}{2}\). This gives a total length of \(2 \frac{2 a}{\sqrt{3}} + 2 a - \frac{a}{\sqrt{3}} \approx 2.64\) km.

(This may not be optimal.)

North pole

The simplest place with this property is the north pole. After you walk south, any amount of distance walking west will leave the north pole one kilometer north of you.

Other solutions

However, there are also an infinite number of places near the south pole with this property. Consider the circle centered on the south pole, with a circumference of one kilometer. Walking west for one kilometer from anywhere on this line will return you to the same position. Thus if we start one kilometer north of this circle, then we also satisfy the problem.

Walking once around the south pole is not the only way to stay in the same place. We could choose a smaller circle such that walking west one kilometer would circle the south pole \(n\) times, for any positive integer \(n\).

The circumference of a circle on a sphere is given by \(c = 2 \pi R \sin\left(\frac{r}{R}\right)\) where \(R\) is the radius of the sphere (the Earth). Since the circumference must be \(\frac{1}{n}\) we have:

Since we need to start one kilometer north of any of these circles, that means that we need to start at any point:

\(\left(R \arcsin\left(\frac{1}{2 \pi R n}\right) + 1\right)\) kilometers north of the south pole for any positive integer \(n\).

Set up two equilateral triangles ABC and BCD with unit sides which share a side. Let the color of A be green.

If B or C are green then we are done. Likewise if D is the same color as B or C.

This leaves the case where D is green. Since the triangle can be oriented in any direction, all points the same distance from A as D is colored green. This describes a green circle.

The circles has a larger than unit diameter, and thus there are an infinite number of points on the circle which are a unit distance from each other.

From point \(O\) travel:

• 1155 km to point \(A\)
• 577 km to point \(B\)
• 3665 km around the radius of the circle to point \(C\)
• 1000 km to point \(D\)

This will guarantee to come across the river.

Proof

Let the distance to the river be \(r\). The problem is equivalent to finding a curve that intersects with all of the tangents of a circle of radius \(r\).

To minimise the distance travelled we want to:

• Go directly to some tangent line (all are equivalent by symmetry)
• Follow it until we reach the circle
• Follow the circle around for some distance
• Then go to the closest point on our original tangent.

We will pick some arbitrary tangent, as all are equivalent. We choose the vertical tangent on the right side.

We need to head to some point \(A\) on the tangent, which we will say is an \(\theta_1\) from the horizontal. The length of the line from \(O\) to \(A\) is given by:

Next we travel from \(A\) to be \(B\), and this distance is given by:

Next we travel around the circle from \(B\) to \(C\). This covers and angle of \(2 \pi - 2 \theta_1 - 2 \theta_2\). This gives adds a distance of:

Finally, to head from point \(C\) to point \(D\):

This gives a total distance of:

We wish to minimise \(d\) thus we require that both of the following hold:

Solving for \(\theta_1\):

Solving for \(\theta_2\):

Substituting \(\theta_1\) and \(\theta_2\) into the equation for \(d\):

For our problem, \(r = 1000\) this gives a total distance of:

\(A\) will definetly hit \(D\).

Proof

Plot the path of the ships in 3 dimensions, with time as the third dimension.

The paths of ships \(B\) and \(C\) form a plane (since they are different headings).

The path of \(A\) is on the same plane since it intersects with both \(B\) and \(C\). Likewise for \(D\). Hence the paths of \(A\) and \(D\) are co-planar.

\(A\) and \(D\) are on different headings, hence their paths intersect. They’ve both been sailing for a long time, hence their paths don’t intersect in the path, so they must intersect in the future.

Let \(r\) be the radius of the lake.

First note that the simple strategy of rowing directly away from the monster fails. You need to travel a distance of \(r\), the monster needs to travel \(\pi r\) but does so 4 times faster.

However, you can travel further away from the center while keeping the monster on the opposite side. If you are closer than \(\frac{r}{4}\) from the center then you can row in a circle faster than the monster can circle the lake.

So first row to a distance of \(\frac{r}{4}\) from the center while keeping the monster opposite you. From there you can row directly to the closest shore. The monster will still have to travel a distance of \(\pi r\), but you only have to travel \(\frac{3}{4} r\).

Even though you are 4 times slower, you will reach the shore first because \(\pi r < 4 \times \frac{3}{4} r = 3 r\).

Extension

This strategy works as long as the monster is no more than \(\pi + 1 \approx 4.14\) times faster.

However, this strategy is not optimal and you can escape a monster who is up to ~4.6 times faster. For a proof see this blog post.

Fix any direction and call it “north.” Look at the north poles of all planets. A north pole is private if and only if there are no planets further to the north. Therefore, only the northernmost planet has a private north pole.

Since north was arbitrary, this is true for any direction. If we take the surface a single planet, every point on that planet corresponds to a direction. Thus each point on this surface maps to exactly one hidden point - the hidden point for that direction. Similarly, all hidden points map to a unique direction and thus a unique point on the surface of the planet.

First note that it is not true in general if we have \(n\) points and \(n\) coins. Any layout of coins will always have gaps, and will fail to cover a sufficiently dense set of points.

Instead consider a infinite hexagonal packing of circles. The density of such a packing is \(\frac{\pi}{2\sqrt{3}}\). Take a randomly translated close packing. Then:

Note that this is true regardless of the covariance of the probabilities. Covariance can only lower the calculated probability.

Since there the probability is less than 1, there is some probability that a random translation of the hexagonal packing will cover all the points. If there were no valid translations, then the probability would be 0, thus a convering translation must exist.

Finally, we note that at most 10 of the coins in the infinite packing must be covering points because each point can only be under at most one coin. Thus we only need to use 10 coins.

First consider the problem for a circle instead of a ball.

Let \(A\) and \(C\) be the entry and exit points of the worm. Let \(B\) be the point opposite the worm’s entry point.

Note that the worm can never travel from \(A\) to be \(B\) as the distance is 62 mm.

Draw a line that bisects \(C\) and \(B\) and goes through the circle’s center (hence cuts the circle in two). By construction, all points on the line are equally far from \(C\) and \(B\). Thus if the tunnel touches the line, then it could also have reached \(B\). Since a tunnel between \(A\) and \(B\) is impossible, the tunnel cannot touch the line.

Cutting the apple along the line leaves the tunnel completely on one side, leaving the other side untouched by the worm.

For a sphere, replace the bisecting line with a bisecting plane where all points on the plane are eqi-distant from the points \(B\) and \(C\). The rest of the proof carries through.

You only need to make one round trip.

Proof

Starting in the first building number:

1. Label 1 wire with \(A\).
2. Connect the next 2 wires and label them with \(B\).
3. Connect the next 3 wires and label them with \(C\).
4. Connect the remaining 4 wires and label them with \(D\).

This accounts for all the wires as \(1+2+3+4 = 10\).

Now go to the second building. Using the battery and lightbulb, test every pair of wire against the others (45 tests) to check if they are connected.

Label the wire that is not connected to any other wire as \(A\), the wires that are only connected to each other as \(B\), the group of 3 connected wires as \(C\), and the group of 4 connected wires as \(D\).

Update the labels as follows:

1. Take one wire from each group and connect them together. Append \(A\) to their labels - this will result in labels \(AA\), \(BA\), \(CA\) and \(DA\).
2. Take another wire from each group (which has not yet been updated) and connect them together. Append \(B\) to the label. Only 3 of the groups will have a spare wire for this.
3. Continue in this way connecting wires, appending \(C\) and \(D\) in turn. Each will have one less group with spare wires to update.

As before this accounts for all the wires as \(1+2+3+4 = 10\). Each wire now has a unique 2 letter label, because each wire in a given group got a different letter appended.

Now return to the first building. Disconnect the original connections. Using the battery and lightbulb, test every pair of wire against the others (45 tests) to check if they are connected.

Append \(D\) to the wire that is not connected to any other wire, \(C\) to the wires that are only connected to each other, \(B\) to the group of 3 connected wires, and \(A\) to the group of 4 connected wires.

The labels of the wires in the two building should now match, with each wire having a unique 2 letter label.

This strategy works for any triangular number numbers of wires.

The prisoner at the front had a red hat.

Proof

The prisoner at the back can see the colours of the other two prisoners. If the hats were both blue then the prisoner could deduce that their own colour was red, and they would instantly say this. Since the prisoner at the back remained quiet we (and the two prisoners in front) know that least one of the front two prisoners has a red hat.

The middle prisoner can only see the colour of the front prisoner’s hat. If it was blue then the prisoner could deduce that their own hat colour was red. However, they do not speak. This means that the colour of the hat on the front prisoner must be red.

Number the switches #1, #2 and #3. Use the following strategy:

• Turn on switch #1.
• Wait a suitably long time (we will arbitrarily choose one hour).
• Turn off switch #1.
• Turn on switch #2.
• Enter the room with the lamp.

• Examine the lamp:

  • If the lamp is on, switch #2 controls the lamp.
  • If the lamp is off, but the lightbulb is warm to the touch, switch #1 controls the lamp.
  • Otherwise switch #3 controls the lamp.

32 knights:

All the knights are on black squares, and knights on black squares can only attack white squares.

Proof

Pair up squares as in the following diagram. Paired squares are identified by the same piece.

A knight can only be placed on one of each pair of squares. Since this arrangement can be tiled across the entire chessboard, the knights can take up at most half the chess board: 32 squares.

We need to be able to represent all numbers for 01 to 31.

0, 1 and 2 need to be paired with every number hence need to be on both cubes. The remaining numbers don’t need to be paired with each other, thus can be placed on either of the cubes.

This leaves us 6 remaining faces, but we have 7 remaining numbers. We can take advantage of the fact that the same face can represent both 6 and 9 by placing the face upside down.

Thus the following layout works:

• Cube 1: 0, 1, 2, 3, 4, 5
• Cube 2: 0, 1, 2, 6/9, 7, 8

Move a die from one pile to the other, so you have a pile of 6 dice and a pile of 4 dice. Flip all the dice in the pile of 4. The two piles will have the same sum.

Proof

First note that opposite sides of a dice add up to 7. Thus flipping the dice changes the value from \(x\) to \(7-x\). Filling a group of \(n\) dice changes the total from \(x\) to \(7n-x\).

The sum of the all the dice in front of you is 28. Thus if the total of one group is \(x\) then the total of the other group would be \(28-x\). If a group only had 4 dice then we could make the groups equal by flipping the 4 dice. The flipped group would have a total of \(7\times4-(28-x) = x\).

If we shift a die from one group to the other the overall total remains 28, but now we have a group of 4 which we can flip.

Arbitrarily split the coins up into a group of 20 and a group of 80. Now flip all the coins in the group of 20. Now both groups have the same number of heads up.

Proof

Let the number of coins in the group of 80 be \(h_{80}\).

There are 20 coins with heads up initially, so immediately after we split up the groups, the number of heads in the group of 20 is \(20 - h_{80}\).

When we flip the coins in the group of 20, the number of heads in the group becomes \(20 - (20 - h_{80}) = h_{80}\). Thus now the two groups have the same number of heads showing.

This is possible in one cut.

Cut a single link, the third one, dividing the chain into lengths of 1, 2, and 4. Then follow this day-by-day plan:

1. Give 1 link.
2. Give 2 links, get 1 link as change.
3. Give 1 link.
4. Give 4 links, get 3 links as change.
5. Give 1 link.
6. Give 2 links, get 1 link as change.
7. Give 1 link.

This is equivalent to counting in binary.

The man shook hands with 4 people.

Proof

Let us label each person with the number of people they have shaken.

Everyone has shaken hands with at most 8 people, since there are only 8 people at the party besides that person and their spouse. So for every number between 1 and 8, there is a person who has shaken that many hands.

#8 must have shaken hands with everyone else other than their spouse. Thus the spouse must be #0, since everyone else has shaken at least one hand (#8’s). By the same logic, since all of the remaining people have shaken hands with #8, and none with #0, #7 must be married to #1. Likewise, #6 is married to #2 and #5 is married to #3.

The only people left are #4 and the man. Thus the man must be married to #4. Thus the man must have shaken hands with #8, #7, #6 and #5, but not #0, #1, #2, #3 or his wife #4. This gives 4 handshakes.

Note that the necklace must be divided at two opposite points, as each thief will have to end up with the same number of jewels.

Start with arbitrary provisional cutting points which divide the necklace in two. If one side has more diamonds than the other, you rotate the cut by one jewel. If the switched jewels were the same, it changes nothing and you rotate again. If they’re different, the number of diamonds on one side will either go up one or down one. Eventually, by the time you’ve rotated the cut 180 degrees, the sides of the original cut will have swapped.

Since each rotation changes the number by one, and the diffence in the number of diamonds has been negated, then at some point they must have been equal. If the diamonds are equal then the rubies are also equal since each half has the same number of jewels.

You only need to draw one marble.

Proof

Draw a marble from the can labelled “mixed”.

If you draw a black marble it must be the “black” can since it cannot actually be the “mixed” can. Thus the can currently labelled “black” is the white can, since it cannot be either the “black” or “mixed” cans. Finally the can labelled “white” must be the mixed can.

Similarly if a white marble is drawn, the can labelled “mixed” is really “white”, the can labelled “white” is really “black” and the can labelled “black” is really “mixed”.

You need to draw two marbles.

Proof

First note that one marble is not sufficient since there are 3 possible swaps. Single marble can only distinguish between two possibilities.

Start by drawing a marble from the can labelled “mixed”.

If a white marble draw a marble from the can labelled “black”. If this second marble is white, then the “mixed” can is correct, and the “black” label was swapped with the “white” label. If the second marble is black then the “black” can is correct and the “mixed” was swapped with the “white”.

If the first marble drawn was black then follow the above analysis with black and white reversed.

On the 100th day, all 100 prisoners with an X mark will leave. On the day after 101st day, the 100 remaining prisoners with the O mark will leave.

Proof

In the case of one prisoner with the X mark, he looks around and sees that no one else has an X. Thus he is the only one the guard could be referring to. Thus we have:

Theorem 1: If there is only one prisoner with an X mark, he leaves on the first night.

Let us set up the hypothesis that:

Hypothesis 1: If there are \(n\) prisoners with the X mark, nothing will happen for the first \((n-1)\) nights, then they will all leave on the \(n\)th night.

If there are \((n+1)\) prisoners with the X mark, then they all see \(n\) other prisoners with the X mark. Thus they can all deduce that there must be either \(n\) or \((n+1)\) prisoners with the X mark.

If we assume Hypothesis 1, then on the first \(n\) nights nothing will happen. After the \(n\)th night they will be determine that there can not be exactly \(n\) prisoners with the X mark. Hence they can all deduce that they each have an X mark and they will all leave on the next night, the \((n+1)\)th night. Thus we have:

Theorem 2: If Hypothesis 1 is true for a given \(n\) then it is also true for the case \((n+1)\).

We can see that Hypothesis 1 is true for the case \(n = 1\) by Theorem 1. Then using induction with Theorem 2 we can see that Hypothesis 1 is true for all \(n \ge 1\).

In our problem, we have the case where \(n = 100\) thus all the prisoners with the X mark will leave on the 100th day. The prisoners with the O mark will see them leave and can deduce that they do not have an X. Since O is the only other option they will leave on the next day, the 101st day.

Each prisoner already knew that there was at least one X marked prisoner. They also all knew they everyone else knew, and they everyone knew that everyone knew. However this does not continue indefinitely.

In our problem, everyone knew that there were at least 99 X marked prisoners. But when we get to meta-knowledge, we can only say that everyone knew that everyone knew that there are at least 98 X marked prisoners. Continuing further, our strongest statement of meta-meta-knowledge is that, everyone knew that everyone knew that everyone knew that there are at least 97 X marked prisoners.

This continues until we can’t say anything about the number X marked prisoners.

When the informer speaks, the fact that there is at least 1 X marked prisoner becomes common knowledge. Importantly, now everyone knows that everyone knows that there is at least X marked prisoner. And everyone knows that everyone knows that everyone knows… and so on indefinitely. Sufficiently deep in this meta-knowledge, this adds new information. This is known as Common knowledge.

The car in space 87.

This becomes more obvious if we turn the image upside down. The lots are actually numbered from 86-91:

First we determine that there must be at least 2 of each hat colour. If there was a person with a unique hat colour, then they could in no way determine that their was even a valid colour. However, the host said that everyone has enough information to solve the puzzle and leave. Thus there must be at least two people with each hat colour.

We now form a hypothesis and prove it via induction:

Hypothesis: If there are \(n\) people with a hat of colour \(c\), then they will all leave on the \((n-1)\)th bell.

If there are only two people for a given colour \(c\), then both of them will count only one hat of colour \(c\) in the group. Thus they will both know that their own hat colour must also be \(c\). Therefore they both leave on the first bell, satisfying the Hypothesis.

Suppose there are \(n\) people with hats of a given colour \(c\), and suppose the Hypothesis is true for \(n-1\). Then everyone with hat colour \(c\) will see \(n-1\) people with colour \(c\). On the \((n-1)\)th bell none of them will leave, thus they will all conclude there must be more than \(n-1\) people with a hat of colour \(c\). Thus they will determine that they must have a hat of colour \(c\).

Therefore, because the Hypothesis is true for \(n=2\), and the Hypothesis being true for \(n-1\) implies it is true for \(n\), we have that the Hypothesis is true for all \(n \ge 2\).

Therefore, everyone eventually leaves. (Compare this with Marked prisoners).

As each prisoner enters, they simply join the line at the point between an adjacent black and white hat. If there are only hats of one color they can join at either end of the line.

This always preserves the property that the line is always valid at all times. Note, that the prisoners don’t need to communicate beforehand.

Do the following in order until you escape:

1. Push buttons on two opposite walls.
2. Push buttons on two adjacent walls.
3. Push buttons on two opposite walls.
4. Push any one button.
5. Push buttons on two opposite walls.
6. Push buttons on two adjacent walls.
7. Push buttons on two opposite walls.

You should be free by the end of the last instruction at latest.

Proof

Let us label all the states we could be in:

• \(A\): Two buttons ON, on opposite sides.
• \(B\): Two buttons ON, on adjacent sides.
• \(C\): Three buttons in the same state, and other other different.

If we push two opposite buttons, then if we are in state \(A\), then we go free. The other states remain the same. Thus first we carry this out, and if we are still in the room, we must be in state \(B\) or \(C\).

Now, if we are in state \(B\) and we push two adjacent buttons, then we either go free or go to state \(A\). But from above we know how to escape from state \(A\). Thus we push two adjacent buttons, then two opposite buttons. If we are still in the room, the starting position must have been state \(C\).

Note that up to this point we have been pushing two buttons at a time, so this always leaves state \(C\) the in state \(C\).

Now we know that we are in state \(C\). Pushing any one button will convert the state to either \(A\) or \(B\). But we know how to escape for \(A\) or \(B\), so we just repeat the procedure above.

In summary the possible states we are in after each step are:

\(\{A,B,C\}\) \(\xrightarrow{1} \{B,C\}\) \(\xrightarrow{2} \{A,C\}\) \(\xrightarrow{3} \{C\}\) \(\xrightarrow{4} \{A,B\}\) \(\xrightarrow{5} \{B\}\) \(\xrightarrow{6} \{A\}\) \(\xrightarrow{7} \{\}\)

\(B\) is taller.

Proof

There are three different cases:

• If \(A\) and \(B\) stand in the same row, then \(B\) is taller, since we know that \(B\) is the tallest student in their row.

• If \(A\) and \(B\) stand in the same column, then again \(B\) is taller, since we know that \(A\) is the shortest student in their column.

• If \(A\) and \(B\) share neither a row nor a column, then let \(C\) be the student who’s in the same column as \(A\) and the same row as \(B\). Then \(C\) is shorter than \(B\) (who is the tallest in their row) and taller than \(A\) (who is the shortest in their column), so \(B > C > A\).

In every case, \(B\) is taller than \(A\).

3 inches.

Proof

The front of volume 1 is directly next to volume 2 when arranged on the shelf. Likewise, the back of volume 5 is next to volume 4.

Thus the bookworm does not eat through volume 1 and 5, only 2, 3 and 4. It travels 3 books, thus 3 inches.

23 people.

Proof

For simplicity, ignore leap years. This won’t significantly affect the result.

Assume that all birthdays are equally likely. If birthdays are unequally distributed, then it only makes it more likely that people share a birthday.

We will determine the probability that no one shares a birthday with anyone. Adding people one at a time:

• The first person won’t share a birthday (as they are the only person). i.e. they have a \(1 = \frac{365}{365}\) chance of being unique.
• The second person only has to avoid the first person’s birthday for a \(\frac{364}{365}\) chance of being unique.
• The \(n\)th person has to avoid \(365-(n-1)\) days for a \(\frac{366-n}{365}\) chance of being unique.

Then the probability \(P'(n)\) that no one shares a birthday is the product that each individual has a unique birthday:

The probability that there are two people who share a birthday \(P(n)\) is the complement:

23 is the smallest number for which \(P(n) > 0.5\).

Other values

By the pigeonhole principle, you need 366 people to be guaranteed to be two people who share a birthday (367 to include leap years).

However chance climbs very quickly to be close to 1 with much smaller groups:

Position 20.

Proof

Your probability of getting a free ticket when you are the nth person is line is (probability that none of the first n-1 people share a birthday) \(\times\) (probability that you share a birthday with one of the first n-1 people):

We want the first \(n\) such that \(P(n) > P(n+1)\):

Solving for \(n\) we find roots at \(n \approx -18.6\) and \(n \approx 19.6\). The negative root is invalid for this problem.

Thus we need \(n > 19.6\) giving a minimum of \(n = 20\).

Yes, the caterpillar does reach the other side, eventually.

Proof

Because the relative position of the caterpillar remains the same when the bungee cord is stretched, we will look at the position of the caterpillar as a fraction of the bungee cord length, \(L\). It starts at position \(0L\), and must reach position \(1L\).

In the first step, the caterpillar walks \(\frac{1}{100} L\). In the next step, the caterpillar walks \(\frac{1}{200} L\), then \(\frac{1}{300} L\), and so on. The total distance the caterpillar has travelled after \(n\) steps is:

We require the distance to equal \(1L\) for the caterpillar to reach the other side, hence we need some \(n\) such that:

\(\sum_{x=1}^n \frac{1}{x}\) is the harmonic series, which diverges. Thus it will eventually exceed 100 for some (very large) value of \(n\). Therefore the caterpillar will reach the other side. In general, this is true for any length cord.

By the Euler-Maclaurin formula, the harmonic series is approximated by:

\(H_n \approx \ln n+\gamma\) where \(\gamma \approx 0.5772\)

We need to reach \(H_n > 100\). Thus an approximation for the number of steps taken by the caterpiller is:

No, the chameleons can never all be the same colour.

Proof

Let \(c_B\) be the number of blue chameleons, \(c_G\) be the number of green chameleons, and \(c_R\) be the number of red chameleons.

Let’s look at the number of each colour modulo 3. For any arrangement of colours \(i\), \(j\) and \(k\) at any time \(t\) the number of chameleons, \(N_t\) is:

Now let’s assume a chameleon of colour \(i\) and \(j\) meet, by our rules the new numbers are:

Thus the difference between the numbers can never change (modulo 3).

Initially we have:

For all the chameleons to be the same colour we would require the other two colours to both have 0 chameleons. However, from our initial condition this can never happen because none of the initial numbers are the same modulo 3.

The stick will be clear of ants in, at most, 1 second.

Proof

When two ants reverse direction, it is equivalent to the two ants moving past each other because the identity of each ant doesn’t matter. Thus for the 1m long stick, all ants will have fallen off after 1 second.

Ant #1 and will have moved 50 cm counter-clockwise along ring (it will be on the opposite side of the ring).

Proof

As with the ants on a stick, two ants colliding is equivalent to them passing past each other if we don’t care about their identities. Thus at \(t=1\) there will be an ant on each of the position where there was \(t=0\), though this maybe a different ant to the original ant.

However, since the ants actually reverse direction when they collide, the relative order of the ants remain unchanged. Ant #1 remains between #2 and #100, ant #2 remains between #1 and #3, etc.

Since all ants end on one of the starting points at \(t=1\), ant #1 shifts counter-clockwise by \(x\) cm for some integer \(-100 \le x \le 100\). Because the relative order of the ants remains the same, and there is an ant on each of the original positions at \(t=1\), all ants must have shifted counter-clockwise by the same distance \(x\) cm.

At any point in time, 25 ant are moving clockwise and 75 ants are moving counter-clockwise as there are 25 prime numbers in the first 100 positive integers. This gives a total velocity of all the ants of 50 cm/s counter-clockwise for any time \(t\). Thus at time \(t=1\) the ants will all have moved counter-clockwise by 50 cm, meaning each individual ant will have moved counter-clockwise by 50 cm.

An interesting thing to note is that if we had four numbers instead of three then for any \(x \ne 0\):

100! has 24 zeros.

Proof

The number of zeros at the end of a number tells us how many times 10 divides into the number. Each 10 that divides a number can be broken down into a 5 and a 2.

For factorial, factors of 2 are very common - every even number adds at least one 2. Thus for every 5, there will always be a 2 available. Therefore we only need to count how many times 5 goes into the factorial.

Every multiple of 5 introduces another 5 to the factorial’s factors. There are \(\left\lfloor \frac{n}{5} \right\rfloor\) 5s in the numbers up to \(n\). However, we also need to count an extra 5 for every multiple of \(5^2\), and so on for all powers of 5. We can only stop when the powers of 5 exceed \(n\).

Thus to calculate the number of times 5 divides \(n!\), and thus the number of zeros at the end, we have:

For \(n=100\):

Let \(n\) be the number of people at the party.

Since no one can be friends with themselves, everyone has between 0 and \(n-1\) friends.

If someone has \(n-1\) friends then that person is friends with everyone else, so no one can have 0 friends.

Likewise if someone has 0 friends, no one can have \(n-1\) friends (be friends with everyone).

Thus there are \(n-1\) possible numbers of friends and \(n\) people, so by the pigeon-hole principal, at least two people have the same number of friends.

Imagine the 6 people. Of them, some person \(X\) either has at least 3 friends among the other 5, or at least 3 strangers.

If \(X\) has at least three friends, then either:

• The 3 of them are all mutual strangers.
• At least 2 of them are friends. Then the these 2 and \(X\) are all mutual friends.

Both of these satisfy the condition.

If \(X\) has at least three strangers, then either:

• The 3 of them are all mutual friends.
• At least 2 of them are strangers. Then the these 2 and \(X\) are all mutual strangers.

Both of these also satisfy the condition.

General case

In general, if we require there be either a group of \(a\) mutual strangers or \(b\) mutual friends then the minimum sized group of people required is called the Ramsey number: \(R(a,b)\). The case explored in this problem is \(R(3,3) = 6\).

Given \(N\) canisters, there is at least one canister with enough fuel to reach the next canister. Otherwise the total fuel in the canisters would not be sufficient to make it around the circuit.

Combine the next canister with the current canister at the location of the current canister, such that there are now \(N-1\) canisters. The total fuel is still \(L\). If the problem can be solved with these \(N-1\) canisters, the original problem can be solved since we’ve established that there was enough fuel to reach the next canister.

Now the same reasoning can be used to reduce the problem down to 1 canister which contains all \(L\) liters of fuel, at which point the problem is trivial.

Choosing this as the starting point allows us to solve the original problem.

The daughters are 2, 2 and 9 years old.

Proof

The possible ages that multiply to 36 are (along with their sums):

• 1, 1, 36 (38)
• 1, 2, 18 (21)
• 1, 3, 12 (16)
• 1, 4, 9 (14)
• 1, 6, 6 (13)
• 2, 2, 9 (13)
• 2, 3, 6 (11)

Bob knows the sum of the ages because he can see the house number. Since knowing the sum is not enough to determine the ages, the sum must be one of the sums that is not unique.

The only sum that is not unique is 13, which is the sum of (1, 6, 6) and also (2, 2, 9).

Next Alice tells Bob about her oldest daughter. This means that the ages cannot be (1, 6, 6), since there is no oldest daughter in this case.

Hence the ages are 2, 2 and 9.

Only 2 queries are required.

Proof

Let the polynomial you are trying to guess be \(p(x) = \sum c_i x^i\).

First, attempt to determine \(p(x)\) with only one query: \(a\). This would not allow us to distinguish between the polynomials \(p_1(x) = x\) and \(p_2(x) = a\) - both would evaluate to \(a\).

To solve the problem with two queries, first ask for \(p(1)\):

Let \(b=r_1+1\). Since the coefficients of \(p(x)\) are non-negative, \(b\) is greater than all \(c_i\).

Next evaluate \(p(b)\):

\(r_2 = p(b) = \sum c_i b^i\).

The coefficients of the polynomial can be read off as the digits of \(r_2\) when it is written in base \(b\).

Only 2 vectors are required.

Proof

Let the vector you are trying to guess be \(\mathbf{x} = [x_1, x_2, \ldots, x_n]\).

First, attempt to determine \(\mathbf{x}\) with only one query, \(\mathbf{y} = [y_1, y_2, \ldots, y_n]\). Assume \(n > 1\). All entries in \(\mathbf{y}\) must be non-zero. If some value \(y_i\) was zero, then we would have no information about entry \(x_i\). However, now we cannot tell the difference between the vectors \(\mathbf{x} = [y_2, 0, x_3, x_4, \ldots, x_n]\) and \(\mathbf{x} = [0, y_1, x_3, x_4, \ldots, x_n]\). Both result in the dot product of \(\mathbf{x} \cdot \mathbf{y} = y_1 y_2 + \sum_{i=3}^n y_i x_i\).

Thus we must use at least 2 vectors, \(\mathbf{y}_1\) and \(\mathbf{y}_2\). Let \(\mathbf{y}_1 = [1, 1, \ldots, 1]\). This will result in the value \(r_1\) which is the sum of all values in \(\mathbf{x}\):

Let \(b = r_1+1\). Since the values in \(\mathbf{x}\) are non-negative, \(b\) is greater than all \(x_i\).

Now construct our second vector \(\mathbf{y}_1 = [1, b, b^2, b^3, \ldots, b^{n-1}]\). Our second result, \(r_2\) will be:

The numbers \(x_i\) can be read as the digits of \(r_2\) when it is written in base \(b\).

The lockers left open are the square numbers: 1, 4, 9, 16, 25, 36, 49, 64, 81 and 100.

Proof

The lockers that are left open are those that have been changed an odd number of times.

Since student \(n\) changes all the lockers that have \(n\) as a factor, the lockers that have changed are those that have an odd number of factors.

Factors come in pairs (\(n = f_1 \times f_2\)), so for there to be an odd number of factors, a factor \(f\) must repeat itself in a pair (\(f = f_1 = f_2\)). In this case \(n = f \times f\), thus \(n\) is a square number.

You can always find a spot such that you were there at the same time on both the first and the second day.

Proof

Imagine a second hiker, who starts climbing the same path at 6 am on the second day. Now assume that the second hiker walks at exactly the same speed you did on the first, and takes the same breaks you did.

Now on the second day, since you both start at opposite ends of the path at 6 am and finish at opposite ends at 6 pm, you must have met each other along the way. The point where you meet gives a point where you were at the same position at a given time on both days.

An example is:

Proof

Suppose that \(f(x) = y\) for some \(x\) and \(y\). Then:

Therefore continued application of \(f\) results in a cycle: \(x \rightarrow y \rightarrow -x \rightarrow -y \rightarrow x\).

This implies that \(f(0) = 0\) because we require that \(x = f(0) = f(-0) = -x\).

For all other integers we need to partition them into groups of 4, each which contain some \(x\), \(y\) and their negations. To construct such a mapping, let us make the simplest choice of letting \(f(1) = 2\). This then forces the following cycle: \(1 \rightarrow 2 \rightarrow -1 \rightarrow -2 \rightarrow 1\).

Likewise we can let \(f(3) = 4\) and in general for \(k > 0\) we can let \(f(2k-1) = f(2k)\) which forces: \(2k-1 \rightarrow 2k \rightarrow -2k-1 \rightarrow -2k \rightarrow 2k-1\). Thus we can define how the function acts on a number based on whether it is positive or negative and whether it is even or odd:

When \(n < 0\) we are always adding 1, and when \(n > 0\) we are always subtracting \(1\). Thus the above simplifies to:

Now \((-1)^n = 1\) when \(n\) is even, and \((-1)^n = -1\) when \(n\) is odd. This allows us to simplify the above to our solution: \(f(n) = \operatorname{sgn}(n) - n(-1)^n\)

By construction it satisfies \(f(f(n)) = -n\) for \(n \ne 0\), and we can evaluate \(f(0)\) to check that it indeed holds for \(0\) as well. Thus our solution is correct.

Light both ends of the first fuse and one end of the second fuse. When the first fuse has completely burnt, light the other end of the second fuse. When the second fuse has completely burnt, 45 minutes has passed.

Proof

When both ends of a fuse are lit, the fuse will burn in half the time. This is true however unevenly the fuse burns.

The first fuse will burn out completely in 30 minutes. At that time the second fuse is now has 30 minutes remaining.

We can think of the second fuse now as 30 minute fuse. If we light the other side, it will burn out in half the time: 15 min. Thus 30 + 15 = 45 minutes will have passed.

Extensions

In this problem we measured out a time which was \(\frac{3}{4}\) of the total fuse length.

In general the times we can measure with some number of fuses which burn in a unit length of time are called Fusible numbers.

Follow these steps:

Note, that this assumes that a half-finished timer will measure the same time when turned upside-down. This may not be true in physical systems. (For real hourglasses with sand, this is going to be accurate enough).

To solve the puzzle without this assumption, set-up 7 minutes before you need to start timing:

You only need 1 weighing.

Proof

Number each bag from 1 to 100. Onto the scale put \(i\) marbles from bag #\(i\). That is put 1 marble from bag #1, 2 marbles from bag #2 and so on.

The total number of marbles, \(M\), on the scale is:

The difference between the actual weight and 5050 grams divided by 0.001 will give you the number of the bag with the slightly heavier marbles.

We can do it in 2 weighings.

If we only have 3 marbles, we can determine the heaviest with one just weighing: Put a marble on each side of the scale, and leave one aside.

• If the scale is unbalanced then the heavier side is the heavy marble.
• Otherwise the marble left aside is the heavy marble.

To solve the problem for 8 marbles, first weigh 3 marbles on each side of the scale, leaving 2 aside:

• If the scale is unbalanced, take the 3 marbles on the heavy side and determine the heavy marble with one weighing as above.
• Otherwise weigh the 2 remaining marbles to determine which is heavier.

We can do it in 3 weighings.

First note, that if we have 3 marbles with 1 odd marble then we can find the odd marble in one weighing if we know that the odd marble is heavier or lighter. Simply weigh 2 of the 3. If the scale is unequal then we’ve identified the odd marble, otherwise the odd marble is the remaining marble.

First group the marbles into 3 groups of 4. Weigh 2 of the groups:

• If the groups are of equal weight:
  • Mark all eight marbles weighed as good.
  • Take 3 of the 4 remaining marbles and weigh them against 3 good marbles:
    • If the two sides wiegh the same then the last marble is the odd marble. Weigh it against a good marble to determine if it heavier or lighter.
    • If the two sides are unequal, then we know that the odd marble is in the group of 3, and we know whether it is heavier or lighter. This is just the 3 marble case which can be solved in one weighing.
• If the groups are unequal:
  • The 4 remaining marbles are good.
  • From the scale we have a heavy group of 4 and a light group of 4.
  • Now will weigh 3 marbles from the light group and one from the heavy group against 3 good and 1 from the light group:
    • If the side with 3 light and 1 heavy is heavier then the odd marble is either the 1 from the heavy group, or the 1 from the light group on the light side. Comparing either of these with a good marble will identify the odd marble.
    • If the side with 3 light and 1 heavy is lighter, then one of the 3 from the light group is the odd marble. This is just the 3 marble case which can be solved in one weighing.
    • If the scale is equal then the odd marble is one of the 3 remaining marbles from the heavy group. This is just the 3 marble case which can be solved in one weighing.

Person two notes where the water level is on the bottle. They can do this by making a mark, or simply keeping their finger there. They then turns the bottle upside down (with a lid on). If there the water level is below the place that was noted earlier, then person one drank more than their fair share.

Follow these instructions:

• Fill the 5-liter jug from the 8-liter jug.
• Fill the 3-liter jug from the 5-liter jug.
• Pour the 3-liter jug in the 8-liter jug.
• Pour the 2 remaining liters from the 5-liter jug to the 3-liter jug.
• Fill the 5-liter jug from the 8 liter-jug.
• Fill the 3-liter jug from the 5-liter jug. Since only 1 more liter fits in the 3-liter jug, there will be 4 liters left in the 5-liter jug.
• Pour the 3-liter jug into the 8-liter jug.

Since we haven’t lost any water, there is now 4 liters in the 5-liter jug, and hence the other 4-liters in the 8-liter jug.

You can measure out any multiple of \(\gcd(A, B)\).

Proof

First note that at the end of any action, both jugs can’t be partially full. There are no markings on the jugs, so we can only stop pouring when either the source is empty or the destination is full. Thus is it is never useful to empty a partially full jug - that would just leave us with the other jug completely full or empty which can be reached directly from the start.

This leaves the only useful actions as:

1. Fill an empty jug
2. Empty a full jug
3. Pour a full jug into the other jug until either the other jug is full, or the first jug is empty

Let \(a\) and \(b\) be the current amounts of water in jug \(A\) and \(B\) respectively. If we plot the valid paths on a cartesian grid, then valid region that we can be within is along the perimeter where \(a=0\), \(a=A\), \(b=0\) or \(b=B\). This forms a rectangle.

Valid paths in this space will be:

• Horizontal lines between the top and bottom edges: Filling or emptying jug \(A\)
• Vertical lines between the left and right edges: Filling or emptying jug \(B\)
• Negative diagonal lines from one side to the another: Pouring one jug into the other.

Instead of the moving horizontally or vertically, we can instead imagine it continuing in a straight line into a copy of the rectangle. In this case, the real quantities will be given by \(a \mod A\) and \(b \mod B\) to bring as back into the original rectangle:

Since we start with empty jugs, all valid paths start at \((0, 0)\), hence all valid paths can be mapped to the negative diagonal line \(a = -b\).

The strategy

Traveling up along the negative diagonal corresponds to the following strategy:

• If \(A\) is empty, fill \(A\)
• If \(B\) is full, empty \(B\)
• Otherwise pour as much water as possible from \(A\) into \(B\).
• Stop when you have the required quantity.

Traveling down along the line simply swaps \(A\) and \(B\) in this strategy. This will reach all possible values.

Valid values

Suppose the final quantity is in jug \(B\). Then jug \(A\) is either full or empty and in either case \(a = 0 \mod A = x A\) for some integer \(x\). \(b\) can also be written as \(b' + y B\) for some integer \(y\). In combination with our path equation:

By Bézout’s theorem the values of \(b'\) that satisfy this are the multiples of \(\gcd(A, B)\). By symmetry we get the same result if we want the final quantity to finish in jug \(A\).

If the desired quantity doesn’t fit in a single jug then we can first measure out and keep aside a multiple of either \(A\) or \(B\) and then follow the strategy above once the required value fits in a single jug.

More than 2 jugs

This extends to more than 2 jugs. See a discussion here.

Wait until you are on the walkway.

Proof

Imagine two people walking together at the same speed. One stops right before the walkway, and the other stops right as the walkway starts. That is, they stop very close to each other.

However, while they are stopped the person on the walkway continues moving and increases the distance between the two. When they both start walking again (at the same time) now they are separated by the distance that the walkway has moved during this time.

Since they walk at the same speed, this separation will remain.

Wait until you are off the walkway to sprint.

Proof

• Let your walking speed be \(v\)
• Let your sprinting speed be \(v'\).
• Let the length of time you sprint be \(t\).
• Let \(w\) be the the walkway speed.

Assume if you sprint on the walkway then the entire sprint talks place on the walkway. If any sprinting occurs after the walkway, that doesn’t correspond to any change in separation.

We compare the time saved in each scenario compared not sprinting:

1. If sprinting off the walkway you sprint for a distance \(d = v't\). This would have taken a time \(t+\Delta t = \frac{d}{v}\) to walk. The time saved is: \(\Delta t_1= \frac{v't}{v}-t = t\left(\frac{v'}{v}-1\right)\).
2. If sprinting on the walkway you sprint for a distance \(d = (v'+w)t\). This would have taken a time \(t+\Delta t = \frac{d}{v+w}\) to walk. The time saved is: \(\Delta t_2= \frac{(v'+w)t}{v+w}-t = t\left(\frac{v'+w}{v+w}-1\right)\).

We want to sprint off the walkway if \(\Delta t_1 > \Delta t_2\):

Since you sprint faster than you walk, you should sprint once off the walkway.

Note that the converse also holds. If you want to slow down (or stop completely as in the first part), then do so on the moving walkway.

We can get 833 apples to the other town.

Proof

Let the town you are in be town #1 and the destination be town #2. Let the distance between them be \(D\), and the number of apples be \(A\), and the capacity of the car be \(C\) apples.

A couple of observations:

• Since our friend will finish of a partially eaten apple, there is no benefit in travelling non-integer distances.
• If our friend travels a distance \(d_1\), then they could equally travel the same distance in two steps. First travel a distance \(d_0 < d_1\), then travel the rest of the distance. The apples can even be stored at \(d_0\) while the friend does other things.

Taking these together, we can consider the problem 1 km at a time. Thus we just need to determine the most efficient way to transport \(a\) apples 1 km.

Given that a 1 km trip can’t be broken up and that each trip will cost exactly 1 apple, we need to minimize the number of trips. To do this we fill up the car as much as possible (up to \(C\) apples) for each trip, giving us:

Where \(n\) is the number of car trips, and the number of apples eaten. Afterwards, there will be \(a-n\) apples left. Now we can calculate the number of apples at any distance with:

In our case, \(a_0 = 3000\) gives \(a_{1000} = 833\).

We can simplify the calculation by realizing that while \(\left\lceil \frac{a_{d+1}}{C} \right\rceil = \left\lceil \frac{a_d}{C} \right\rceil\) we don’t need to set the apples down as the number of trips will remain the same.

Thus we can travel as far as we can until the apples can be split across one fewer trips - when the total number of apples is the next lower multiple of \(C\). The distance traveled is determined by the number of apples we have to spare and the number of trips:

Because we only deal with integer distances, if we are required to go a non-integer distance \(d\) we round up.

Applying this strategy to our problem:

• Stage 1
  • Take 1000 apples at a time to \(d = \left\lceil \frac{1000}{3} \right\rceil = 334\)
  • We now have 1998 apples left, at a distance of 334 km
• Stage 2
  • Take 998 apples a further \(d = \frac{998}{2}= 499\)
  • We now have 1000 apples left at 833 km
• Stage 3
  • Take 1000 apples until the end, which is \(d = 167\) km away
  • We end up with 833 apples at the destination.

The eldest pirate ends up with 951 gold coins.

Proof

Number the pirates in order of age, so the eldest is #1000 and the youngest is #1.

Let \(P_N\) be the strategy for dividing up the \(C\) coins among \(N\) pirates. Let \(P_N(n)\) be the amount that pirate \(n\) gets when there are \(N\) pirates and pirate \(N\) proposes the optimal plan:

We will prove via induction that the optimal strategy, \(P_N\), is:

Note that we require that \(R \ge 0\). Thus this strategy is only valid for \(N \le 2 (C + 1)\).

We see that for \(P_N\):

• There is one pirate with \(R\) coins
• There are \(\left\lfloor \frac{N-1}{2} \right\rfloor\) pirates with 1 coin
• There are \(\left\lfloor \frac{N}{2} \right\rfloor\) pirates with 0 coins

Consider the case where there is only one pirate left, #1. Then he gets all \(C\) gold:

We see that \(P_1\) is consistent with \(P_N\). In addition, we can write \(P_{N+1}\) as:

Now we know that if \(P_N\) is the optimal strategy, then \(P_{N+1}\) is strictly better than \(P_N\) for at least half the pirates:

And we cannot reduce the number of coins \(R\) that pirate #\((N+1)\) gets without falsifying this equation.

Comparing \(P_N\) with \(P_{N+1}\) we see that:

• The \(\left\lfloor \frac{N}{2} \right\rfloor\) pirates who got 0 coins in \(P_N\) get 1 coin in \(P_{N+1}\)
• Pirate #\((N+1)\) who is dead in \(P_N\) gets \(R\) coins in \(P_{N+1}\)
• The other pirates all get 0 coins

Thus \(\left\lfloor \frac{N}{2} \right\rfloor + 1\) are better off under \(P_{N+1}\) than \(P_N\). We require \(\left\lceil \frac{N+1}{2} \right\rceil\) votes for \(P_{N+1}\) to be valid:

Thus we have exactly the amount of votes required. In addition, we used the minimum number of coins possible to secure those votes, just 1 coin to each pirate from whom we can secure a vote. Hence \(P_{N+1}\) is optimal given \(P_N\). We already have that \(P_1\) is optimal, therefore by induction the strategy \(P_N\) is optimal for all \(N \ge 1\).

In the case where \(N = 100\) and \(C= 1000\), all even number pirates other than the eldest (pirate #100) gets 1 coin each. Thus 49 coins go to these pirates. The odd numbered pirates get nothing. Finally, the eldest gets the rest which is:

\(1000 - 49 = 951\) coins.

The eldest pirate gives the coin to 6th youngest pirate.

Proof

Again, number the pirates in order of age, so the eldest is #10 and the youngest is #1. We will look a each case from 2 to 10 pirates.

2 pirates: Pirate #2 just keeps the gold coin.

3 pirates: Pirate #3 will have to give away the gold coin, otherwise #2 and #1 will both vote against him. There is no point giving it to #2 who will get the coin anyway if pirate #3 dies. Hence he gives it to pirate #1, securing the vote from pirate #1 and thus the majority.

4 pirates: Pirate #4 can’t give a coin to pirate #1 since he will get a coin anyway if pirate #4 dies. But he can give a coin to either pirate #2 or pirate #3 and secure the majority of votes.

5 pirates: Pirate #5 can only get a maximum of 2 votes, his own, and the pirate he gives the coin to. That leaves 3 pirates who get 0 coins and thus have no incentive to vote for him. Thus pirate #5 dies, no matter what he does.

6 pirates: Pirates #6 can be guaranteed the vote of pirate #5, because pirate #5 will die otherwise. He needs one more vote. He can give a coin to either pirate #4 or pirate #1 who both receive nothing under the 4 pirate case.

7, 8 or 9 pirates: The eldest pirates in these cases have no way of getting enough votes.

10 pirates: Pirate #10 can get a votes each from #7, #8 and #9 who will all die otherwise. He can give a coin to #6 who would get nothing in the 6 pirate case. Along with his vote, he can get 5 votes, which is enough to survive.

Let the number of pirates be \(N\), and the number of coins be \(C\).

\(N \le 2 (C + 1)\)

The strategy in the 100 pirate, 1000 coin case above works for any \(N \le 2 (C + 1)\).

\(N > 2C\)

We know that for \(N \le 2 C\), the eldest pirate gets at least 1 gold coin. Let us call the smallest case where the eldest pirate has to give up all coins just to survive \(N_0 = 2 C + 1\).

We have for \(N_0\) that there are \(C\) pirate who get coins, and \(C+1\) pirates who do not get coins. We also know that the \(C\) pirates who get coin in \(N_0\) don’t get any in the case \(N_0 - 1\). In addition, the \(C+1\) pirates who don’t get any coins in \(N_0\) are either dead or get one coin in \(N_0 - 1\). Thus we cannot change the arrangement of who gets given coins.

Also note that for any plan \(P_N\), if the eldest pirate dies then plan \(P_N\) is equivalent to plan \(P_{N-1}\).

Let us set up the stricter condition that a pirate \(n\) will vote against a plan \(P_N\) if there is a chance that he gets at least that much gold under \(P_{N-1}\). Call this assumption \(A\).

Let us prove via induction that:

Hypothesis: When there are \(N\) pirates, the eldest pirate has a strategy (\(P_N\)) for survival if there are at least \(C\) pirates who have no chance of receiving any gold. In addition there are at least \(C\) candidates that may receive the gold piece each.

Let us assume assume that the Hypothesis is true for some \(N\), where the eldest pirate has a strategy such that he can survive. Now consider the case \(N' > N\) to be the next case where the eldest pirate has a strategy for survival. The eldest pirate will not gain any votes by offering a gold coin to the \(C\) pirates who received one in the \(P_N\), thus those \(C\) pirates will have no chance of getting any gold under \(P_{N'}\).

The eldest pirate can gain \(C\) votes by offering a gold coin each to the \(C\) pirates who had no chance of receiving anything in \(P_N\).

Thus we have that the Hypothesis is true for \(N\), it is also true for \(N' > N\) being the next case where the eldest pirate has a strategy for survival. We can also saw that the Hypothesis is true for \(N_0\), thus the Hypothesis is true for all \(N \ge N_0\) where the eldest pirate has a strategy for survival.

Note that if we neglect assumption \(A\), then as soon as there are more than \(C\) possible pirates for the eldest pirate to give a coin to in \(P_N\) there is ambiguity in who will recieve the coins. If none of the pirates know for sure if they are getting a coin or not they would be better of with a coin in \(P_{N + 1}\). In this case, as soon as there is any doubt as to who will get the coins, the eldest pirate can give one coin to any other \(C\) pirates and secure \(C\) votes.

And thus we have that in either of these cases the eldest pirate can find \(C\) pirates who will be better of with one gold coin. In addition he will always vote for his own plan, giving:

Theorem 1: In a case \(N \le N_0\) where the eldest pirate has a strategy for survival, the eldest pirate can secure \(C+1\) votes.

The eldest pirate needs \(\left\lceil \frac{N}{2} \right\rceil\) votes to win. The only way he can secure votes of other pirates who get 0 coins are if they are guaranteed to die. Thus the preceding plan for those pirates must have failed, giving:

Theorem 2: For \(N \ge N_0\), then the eldest pirates survives if and only if the next eldest \(\left\lceil \frac{N}{2} \right\rceil - C - 1\) pirates will all fail to come up with a successful strategy.

Now let the function \(S(n) = N\) be the \(n\)th pirate who survives for all \(N \ge N_0\), where \(S(0) = N_0\). Hence we want the smallest \(S(n)\) satisfying:

Thus we have:

From this we can see that \(S(n)|_{even} > S(n)|_{odd}\) for any \(S(n-1)\) where \(n \ge 1\). We want the smallest \(S(n)\), hence \(S(n)\) is always even for \(n \ge 1\):

Solving for \(S(n)\) with \(S(0) = N_0 = 2C + 1\) gives us:

Giving us the set of all \(N\) such that the eldest pirate survives in the case of \(N \ge N_0\) pirate:

All \(N, C\)

Combining all of the above, we have that the set of all cases where there is a surviving eldest pirate is given by:

For any \(N \in N_s\) the eldest pirate can live by offering \(P_N(n)\) coins to each pirate \(n\), where:

This strategy is not unique for \(N > 2C + 1\).

The locksmith should make 1716 locks and give each pirate 924 keys. The method of distributing the keys is discussed in the proof.

Proof

Let \(N\) be the number of pirates, \(n\) be the number required to open the safe.

Any group of \(n-1\) pirate should together be unable to open some non-empty subset \(S\) of all the locks. If \(S\) was empty then they would be able to open all the locks with just \(n-1\) pirates.

We have that for each group of \(n-1\) pirates \(P\) there must be a distinct non-empty subset of locks \(S_P\) that cannot be opened by them. Furthermore, all subsets \(S_P\) must be disjoint. Therefore we need at least one lock for each group of \(n-1\) pirates, meaning at we require \(L \ge {N \choose n-1}\).

We will enumerate each group of \(n-1\) pirates and create a lock for each. Thus we have:

Each pirate needs to be able to join any group of \(n-1\) pirates that he is not part of, and open their lock. Since these locks are distinct for each group, he needs to be able to open \(k \ge {N-1 \choose n-1}\) locks. If he has any less keys, there will be some groups who’s lock he wont be able to open. Thus we set the number of keys for each pirate to be:

Now for each lock you distribute the keys to all pirates, except the selection of \(n-1\) pirates corresponding to that lock. Consider a group of \(n-1\) pirates. There will be a single lock that they cannot open together. However, any pirate other than these \(n-1\) will be able to open that lock, thus any group of \(n\) pirates will be able to open all the locks.

For \(N=13\), \(n = \left\lceil \frac{N}{2} \right\rceil = 7\), we have that \(L = 1716\) locks and \(k = 924\) keys for each pirate.

You need at most 14 drops.

Proof

Let the maximum number of drops be \(d\). If we have 1 marble we can only test \(d\) floors by starting from the bottom and working our way up.

With 2 marbles, we know if we break the first marble on the first drop, we will only have 1 marble and \(d-1\) drops. Therefore our first drop should be floor \((d-1) + 1 = d\), since we can test the lower floors with one marble is required.

If the first drop succeeds we still have 2 marbles, but only \(d-1\) drops. Therefore if the second drop fails we can only test \(d-2\) floors with 1 marble. Thus we should go \(d-1\) floors above where we are, or floor number \(d + (d-1)\).

Continuing like this we can see that the maximum number of floors we can test is given by:

The smallest \(d\) such that we can test 100 floors is 14.

Drop the first marble on floors \([14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99]\) until it breaks. Then with the second marble, incrementally test the floors starting from one above the last good drop.

General case

With \(M\) marbles and \(D\) drops, the number of floors you can test is given by:

Firstly note, having more than \(M > D\) is useless because even if a marble broke on every drop, we would only need \(M = D\) marbles. Thus we will restrict the number of marbles to \(M = \min(M, D)\) without loss of generality.

In any given strategy, decide how many marbles will break, and call it \(m\). If you know which drops those marbles broke on that is enough to tell you the floor number (given you know the strategy used to pick the floors).

There are \({D \choose m}\) different ways of choosing the positions where the marbles break. If we sum over all possible numbers of marbles broken it will give us the maximum number of different floors we can test with \(M\) marbles and \(D\) drops, with any strategy.

Any strategy that achieves this limit is thus optimal.

Let us define such a strategy. We will use the variables:

• \(d\) for the current number of drops left
• \(m\) for the current number of marbles left
• \(x_{max}\) for the maximum floor number we can safely drop a marble from.
• \(x\) for the current floor number

Initially set \(d=D\), \(m=M\), \(x_{max} = 0\) and \(x = 0\). Then proceed as follows:

• Set \(x = x_{max} + F(m-1, d-1) + 1\)

• Drop a marble from from floor \(x\), and set \(d = d-1\)

  • If it survives set \(x_{max} = x\)
  • If it breaks set \(m = m - 1\)
• If \(d > 0\) and \(m > 0\) jump back to the top
• Otherwise stop, the maximum safe floor is \(x_{max}\)

2 rotations!

Proof

The easiest way to see this is to first draw a line equal to the coins circumference. It will take the coin one rotation to roll along the length of the line. Now with the start of the line fixed and the coin fixed at the end of the line, curve the line into a circle. The coin will rotate one more during this process.

When the coin rolls along the outside of a circle, both these rotations happen at once: one from rolling and one from traveling along a curve.

Also see the Coin-rotation paradox. page on Wikipedia.

You can’t divide through by \(a-b\). Since \(a = b\), this is dividing by 0.

Square roots have 2 solutions in general. When taking the square root in the proof, on one side we took the negative square root and on the other side we took the positive square root.

If on the other hand we took the positive square root on both sides we would have:

This is obviously true.

We can’t differentiate a sum whose number of terms is dependant on \(x\) by simply taking the sum of the derivatives. To make the fallacy here more explicit, write out the sum formally:

There are a few fallacies here. Firstly this equation is not meaningful for non-integers. Functions are only differentiable on a continuous space such as the real numbers.

For the second fallacy, note that in the proof, we took the derivative with respect to each term in the sum, but not with respect to the number of terms. The number of terms is a function of \(x\) and has to be taken into account.

Since the sum is a function of \(x\), we must use the chain rule when evaluating this. However this approach does not get us very far. Let the function that the sum denotes be called \(g(x)\). Unsurprisingly we find that \(g(x) = x^2\), leaving us with the same problem.

This problem illustrates an improper application of integration by parts. When using the formula, a constant of integration \(C\) must be added. Up the second last line the equations are correct. However, the last line does not follow, as you cannot cancel \(\int \frac{1}{x}dx\), because they are not necessarily equal. There are an infinite number of antiderivatives of \(\frac{1}{x}\), which all differ by a constant factor.

In reality the last line should read:

Which is trivially true.

The equation is not actually quadratic in \(x\). It doesn’t depend on \(x\) at all, and hence has an infinite number of solutions for \(x\).

Proof

The original equation:

Multiply by \((a-b)(b-c)(a-c)\):

Expand:

Collecting \(x\) terms:

Thus all the \(x\) terms cancel out, leaving an equation that is always true.

The original quadratic has roots at:

However, when we combine the rearranged equations, we form a cubic equation. This adds a solutions, so now:

And indeed, these are the three cube roots of one.

In general setting two equations equal to each other can generate more solutions, that don’t satisfy the original equations independently. This is because you are removing constraints, in this case, the constraint that both equations equaled \(-1\).

Neither of the \(13 \times 5\) “triangles” is a true triangle, because what appears to be the hypotenuse is bent. In the first “triangle” the hypotenuse bends inwards, and in the second it bends outwards.

Specifically, the blue triangle in the image has a slope of \(\frac{2}{5} = 0.4\) while the red triangle has a slope of \(\frac{3}{8} = 0.375\). This discrepancy accounts for the extra square.

The flaw is in assuming it is possible to find a horse who was not excluded by either of the groups of \(n\) in the inductive case.

For the two exluded horses to be the same color, there must be a third horse in the group to compare against.

Thus the induction fails for \(n=2\).

Yes.

The water imparts an upward force on your finger as you immerse it, so you must exert a downward force to overcome it. That force is transferred to the cup and then to the scale, which sinks.

Place the bars so they form a “T” with the blue magnet as the top. A magnet’s field is strong at its poles, but nearly non-existent in the middle. If the bars stick, the red bar is a magnet, otherwise it is the blue bar.

Yes, the plane can take off.

Proof

The power for the engines come from the turbines, which is acting against the air. Thus the plane will develop a velocity relative to the air around it. With enough thrust it will gain enough speed relative to the air to take off.

The conveyor belt only acts on the wheels, making them rotate faster, but does not impede the motion of the plane.

• Put the beta emitting cookie in the lead box. That will protect you from that cookie.
• Put the alpha emitting cookie in your pocket. Alpha radiation is easily stopped by a piece of paper (or your pants).
• Eat the gamma cookie. Gamma radiation is the least ionizing of the three, so it is the least likely to do damage once inside your body. In addition, it is energetic enough that much of it is likely to escape your body without interacting with it.

The effective resistance is \(\frac{5}{6} \Omega\) .

Proof

Let’s call one of the corners point \(A\) , through which we will force 1 A of current into the circuit. Call the opposite corner point \(B\) , through which we will draw 1 A of current from the circuit. Thus overall, 1 A is flowing from \(A\) to \(B\) . We will set the voltage at \(B\) to \(V_B = 0\) .

Now look at the 3 corners adjacent to \(A\) , call them \(A_1\) , \(A_2\) and \(A_3\) . By symmetry, the current through an edge between \(A\) and any \(A_i\) is:

Thus the voltage drop \(V_1\) , between \(A\) and any point \(A_i\) is given by:

Now look at the 3 corners adjacent to \(B\) , call them \(B_1\) , \(B_2\) and \(B_3\) . The situation is the same as above with the current flowing in the opposite direction, hence the voltage drop \(V_2\) between any point \(B_i\) and \(B\) is given by:

Now there are 6 equivalent ways for the current to flow in the middle resistor, between the points \(A_i\) and \(B_i\) . Thus the current flowing through each path is \(\frac{1}{6}\) A. The voltage drop \(V_3\) between any connected \(A_i\) and \(B_i\) is given by:

The total voltage drop between \(A\) and \(B\) can be found by following any path from \(A\) to \(B\) , thus:

Finally, use Ohm’s law to find the effective resistance:

The effective resistance is \(\frac{1}{2} \Omega\) .

Proof

Label the two adjacent points \(A\) and \(B\) . We will superimpose two ways of applying current to this circuit:

• Force 1 A into the circuit at point \(A\) while holding the voltage 0 at infinity. Since each path out of \(A\) is equivalent, the current from \(A\) to \(B\) must be \(I_1 = \frac{1}{4}\) A.
• Draw 1 A into the circuit at point \(B\) while holding the voltage 0 at infinity. Since each path out of \(A\) is equivalent, the current from \(A\) to \(B\) must be \(I_2 = \frac{1}{4}\) A.

Now we superimpose the two cases to get the situation where we have 1 A of current flowing from \(A\) to \(B\) , giving a current \(I = I_1 + I_2\) through the resistor:

The voltage difference between \(A\) and \(B\) is, by Ohm’s law:

But overall, 1 A of current is going from \(A\) to \(B\) , thus the effective resistance, by Ohm’s law is:

The water level goes down.

Proof

The rock is currently displacing the amount of water equal to its mass. When it is dropped to the bottom, it is only displacing the amount of water equal to its volume.

It is more dense than water, so the amount of water displaced by its volume is less than the amount of water displaced by its mass.

Therefore less water is displaced after the rock is thrown overboard, and hence the water level goes down.

Your best strategy is to shoot into the air the first round, then keep firing at the survivor in subsequent rounds.

Proof

Let’s call you person #1, #2 the next best shot, and #3 the person who always hits.

First note that if anyone other than #3 shoots, they must shoot #3. If they shoot the other person and kill them, then they will be in a duel with #3 with #3 going first. #3 wins this duel since #3 never misses.

Therefore it is in #3’s best interest to turn it into a duel as soon as possible, otherwise the other two are just shooting at #3. Thus if #3 survives to their turn then they must shoot. #3 would rather be in a shoot-out with the weaker shooter, hence they would shoot and kill #2.

Thus when it is #2’s turn they must shoot at #3 and hit to survive at all. From this we can tell that by the end of the first round, either #2 or #3 will have been shot.

Finally we look at #1. We’ve already established that if #1 shoots anyone, it must be #3. If #1 shoots and kills #3 then #1 will be in a duel with #2, with #2 going first. If #1 misses then they will be in a duel with the survivor of #2 and #3, with #1 going first.

The probability that #1 wins if they shoot and kill #3 is:

The probability that #1 wins if they shoot and miss #3 is:

Thus #1 has a higher chance of winning if they miss their shot!

Therefore you should intentionally miss the first shot by shooting into the air. After the first round, you will be in a duel with one of the other two people. You will win about 40% of the time.

Number the people #1, #2 and #3 such that the probability that a person hits their target is \(x_p\), with \(x_1 < x_2 < x_3\). Also, define \(\bar{x}_i = 1 - x_i\).

Define the probability \(P_{p_1, p_2, p_3}(p)\) that person \(p\) wins when the shooting order is \(p_1, p_2, p_3\) in the 3 person case.

Similarly, define \(P_{p_1, p_2}(p)\) for the 2 person case. For convenience let \(P_{p_1, p_2}(p) = 0\) if \(p \notin {p_1, p_2}\).

2 person case

We will do the 2 person case first, since the 3 person case reduces to this once a person is hit.

Each person can shoot at the other, or intentionally miss. Clearly, intentionally missing is bad because their opponent is always going to shoot at them: if their opponent hits they die; if their opponent misses they are back to where they started, but have given the opponent a free shot. Because the shooters must shoot, we can say for either person #\(i\):

Combining these equations we get:

The probability that the other person #\(j\) wins when #\(i\) shoots first is just the complement:

Simplifying:

Note that it is always better to start shooting first.

3 person case - Who shoots

Each person has three options, shoot either of the remaining people, or intentionally miss (shoot the air).

If person #\(i\) does shoot at a person then they are hoping to hit (otherwise they would shoot the air). If it hits then person #\(i\) will be in a duel with the survivor, where #\(i\) goes second. Thus they shoot #\(j\) instead of #\(k\) if:

Hence, we have:

Lemma 1: If anyone shoots at another person, they will always shoot at the person with the higher accuracy.

If everyone shoots in the air then no one dies and the dispute is never resolved, in which case the probability of being the lone survivor for any of the people is 0. Thus at least one person shoots. Even in the case where shooting leads to certain death, this is the same as not resolving the dispute and hence we can assume either.

If one person is shooting then the other two can’t both be intentionally missing. In this case it is always better for the person that the shooter is shooting at to shoot back (assuming they haven’t been shot yet). Therefore we have:

Lemma 2: At least two people are shooting in any round where everyone survives.

#3 must either shoot #2 by Lemma 1 or shoot in the air.

• If #3 is shoots in the air then by Lemma 2 both #1 and #2 are shooting, and by Lemma 1 they are both shooting at #3. If they both miss, #3 is back to where they started and #3 shoots in the air again. The other two would continue shooting at #3 until they hit, giving #3 no chance of winning.
• If #3 shoots at #2 then #3’s chance of winning in this case is \(x_3 P_{1,3}(3) + \bar{x}_3 P_{1,2,3}(3) > 0\).

Thus #3 shoots at #2.

#2 must either shoot #3 by Lemma 1 or shoot in the air.

• If #2 shoots #3, they are hoping for a duel with #1. Since #1 would start the duel, the probability that #2 would win is \(P_{1,2}(2)\).
• If #2 shoots in the air, then #2’s best case scenario is that #3 will miss their shoot at #2 then #1 will hit #3. This results in a duel with #1 where #2 shoots first. Even allowing that #1 definitely hits, then the probability that #2 wins is \(\bar{x}_3 P_{2,1}(2)\).

#2 shoots at #3 if #2 would prefer hitting to missing:

This is always true so #2 will shoot at #3.

#1 will either shoot #3 by Lemma 1 or shoot in the air.

• If #1 shoots #3 they are hoping for a duel against #2 where #1 goes second. In this case #1 has a probability of winning of:

  \[P_{2,1}(1) = \frac{\bar{x}_2 x_1}{1 - \bar{x}_2 \bar{x}_1}\]

• If #1 shoots the air, then the other two will shoot at each other. This will continue until either #2 or #3 is shot. In both cases #1 duels with the survivor, and gets to shoot first. The probability that #1 wins in this case is:

  \[\begin{align} P_{1 \text{air}} & = x_2 P_{1,2}(1) + \bar{x}_2 (x_3 P_{1,3}(1) + \bar{x}_3 P_{1 \text{air}}) \\ & = x_2 P_{1,2}(1) + \bar{x}_2 x_3 P_{1,3}(1) + \bar{x}_2 \bar{x}_3 P_{1 \text{air}} \\ & = \frac{x_2 P_{1,2}(1) + \bar{x}_2 x_3 P_{1,3}(1)}{1 - \bar{x}_2 \bar{x}_3} \\ & = \frac{x_1}{1 - \bar{x}_2 \bar{x}_3} \left( \frac{x_2}{1 - \bar{x}_1 \bar{x}_2} + \frac{\bar{x}_2 x_3}{1 - \bar{x}_1 \bar{x}_3} \right) \end{align}\]

#1 will shoot at #3 if and only if #1 would prefer hitting to missing:

Thus #1 will shoot at #3 when:

3 person case - Probabilities

Let \(x'_1\) be the probability that #1 hits when there are 3 players. This is the same as \(x_1\) when #1 aims, but is \(0\) when #1 intentionally misses.

Then the probability that person #n wins is:

Which resolves to:

Original problem

For this problem we have:

From this we get \(C \approx -0.6 < 0\), hence #1 simply shoots the air. The probability #1 wins (which is true for any values where \(C < 0\)) is given by:

Solving this with our values, we agree with our previous result:

The probability is \(\frac{2}{3}\)

Proof

There are 4 possible two-child families:

1. Boy Boy
2. Boy Girl
3. Girl Boy
4. Girl Girl

(4) is not possible, since we know that the family has a boy. There are 3 possibilities and in 2 of the the other child is a girl.

This gives a probability of \(\frac{2}{3}\).

The unintuitive result is because the probability of a family having both a boy and a girl is twice as likely as having 2 boys (or 2 girls).

The probability is \(\frac{1}{2}\)

Proof

List the 4 possible two-child families. The older child is listed first, then the younger.

1. Boy Boy
2. Boy Girl
3. Girl Boy
4. Girl Girl

This time only (1) and (2) are possible since we know that the older child is a boy. In only 1 of these 2 possibilities is the other child a girl.

This gives a probability of \(\frac{1}{2}\).

The ratio of boys to girls is 1:1.

Proof

Let’s assume for now that we don’t know the strategy that the families use to decide whether to have another child. However, the births are statistically independent.

For each birth in the country, we have a \(\frac{1}{2}\) chance of having a girl, and a \(\frac{1}{2}\) chance of having a boy. Thus after \(n\) births, we expect to have on average \(\frac{n}{2}\) girls and \(\frac{n}{2}\) boys.

This gives a ratio of 1:1. Further this is true regardless of what strategy the families use to decide when to have children.

In this specific case we can also determine the expected number of girls per family as:

This represents that there is a 50% chance of having at least one girl. Given one girl, there is a 50% chance of having at least 2 girls, and so on. Since each family stops at one boy, there is on average 1 boy and 1 girl in each family.

If you see an \(x\), guess “larger” with probability \(p(x)\) and “smaller” with probability \(1-p(x)\), where \(p(x)\) is a monotonically increasing function from \(\mathbb{R}\) to \((0,1)\) . A possible function is:

Proof

Suppose the distinct numbers are \(a\) and \(b\) with \(a < b\) .

The probability, \(P\), of guessing correctly is:

From this we can see that:

But since \(p(x)\) is monotonically increasing and \(b > a\), we have \(p(b) > p(a)\). Thus the overall probability of winning is greater than \(\frac{1}{2}\).

Always switch.

Proof

We can assume that we always pick the first door without loss of generality (because each door has a \(\frac{1}{3}\) chance of having the car).

After we pick the door, these are 6 possible (equally likely) arrangements:

C - -
C - -
- C -
- C -
- - C
- - C

Where C stands for car, and - stands for the goat.

After Monty opens one of the door we didn’t pick, and shows nothing. If there is a goat behind the first door then Monty has no choice about which door to open. Thus we have:

C X -
C - X
- C X
- C X
- X C
- X C

Where X represents an open door.

We can see that in 4 of the 6 cases, it is better to switch. This means that if we switch we have a \(\frac{2}{3}\) chance of winning the car.

This time it doesn’t make a difference! Both doors have a 50% chance of having the car.

Proof

As before, we can assume that we always pick the first door without loss of generality (because each door has a \(\frac{1}{3}\) chance of having the car).

After we pick the door, these are 6 possible (equally likely) arrangements:

C - -
C - -
- C -
- C -
- - C
- - C

Where C stands for car, and - stands for the goat.

After Monty opens one of the door we didn’t pick. However this time, the choice is random so there is a possibility that Monty reveals the car:

C X -
C - X
- X - (Car is revealed!)
- C X
- X C
- - X (Car is revealed!)

Where X represents an open door.

We know we aren’t in the 2 cases where the car is revealed, so there are 4 possible scenarios we can be in. In 2 of these 4 cases it is better to switch giving a \(\frac{1}{2}\) chance of winning the car.

First, number each prisoner from 1 to 100. When a prisoner goes into the room they:

• Looks in the box corresponding to their number.
• If they don’t find their name they looks in the box corresponding to the name of the prisoner in the box they just opened.
• They continue until they find their name, or they cannot open any more boxes.

This strategy results in a ~31.2% chance of winning.

Proof

Let us generalise the problem to \(N\) prisoners, where each prisoner is allowed to open \(n = \lceil c N \rceil\) boxes, where \(\frac{1}{2} \le c \le 1\).

In the strategy given, a given prisoner succeeds if they are part of a cycle of at most \(n\) in the permutation of names. For all prisoners to succeed there must be no cycles of size greater than \(n\). We can also see that if there is a cycle of size greater than \(n\), then it is the only such cycle because \(\frac{1}{2} \le \frac{n}{N} \le 1\).

We first find the probability, \(P_L(k)\), that there is some cycle of length \(k\) for some \(k > n\):

• A cycle of length \(k\) occurs on \(k\) of the \(N\) elements, so there are \({N \choose k} = \frac{N!}{k!(N-k)!}\) possibilities for this.
• Within a cycle there are \((k-1)!\) ways to arrange the elements.
• Outside the cycle there are \(N-k\) elements that can be arranged in \((N-k)!\) ways.
• In total there are \(N!\) arrangements.

Thus we have:

Therefore the probability, \(P\), that the strategy succeeds is:

For \(N = 100\) and \(n = 50\) we get \(P \approx 0.3118\).

Large \(N\)

Let \(P(N)\) be the probability that our strategy succeeds with \(N\) prisoners, where each prisoner is allowed to choose \(n = \lceil c N \rceil\) boxes, where \(\frac{1}{2} \le c \le 1\).

We have from the equation above that:

As \(N \rightarrow \infty\) we have:

For \(c = \frac{1}{2}\) we have \(P \approx 0.3069\).

All values of \(0 \le c \le 1\)

If we generalise the problem, we require more than a unique cycle \(n = \lceil c N \rceil\) for our solution to fail.

Let us find the probability \(P_l(k)\), that a given box is part of a cycle of length \(k\). We see that:

• A cycle of length \(k\) occurs on \(k\) of the \(N\) elements. One element is chosen for us so, there are \({N - 1 \choose k - 1} = \frac{(N-1)!}{(k-1)!(N-k)!}\) possibilities for this.
• Within a cycle there are \((k-1)!\) ways to arrange the elements.
• Outside the cycle there are \(N-k\) elements that can be arranged in \((N-k)!\) ways.
• In total there are \(N!\) arrangements.

Thus we have:

Let \(P_l = \frac{1}{N}\). We require that the probability of there being no cycles of length \(k > n\).

Let the probability \(P_L(k, N)\) be the probability that the longest cycle is of length \(k\) in a problem of size \(N\).

We start by looking at the first element. It has a \(P_l\) chance of being in a loop of length \(1\), in which case the probability the longest cycle is be of length \(k\) will be \(P_L(k, N-1)\).

Likewise it has a \(P_l\) chance of being in a loop of length 2, in which case the probability the longest cycle is be of length \(k\) will be \(P_L(k, N-2)\).

In general it has a \(P_l\) chance of being in a loop of length \(i\), in which case the probability the longest cycle is be of length \(k\) will be \(P_L(k, N-i)\), for \(i \le k\) or 0 for \(i > k\). Thus we have:

Let \(P(N)\) be the probability that the longest cycle in a problem of size \(N\) is \(n\):

All three prisoners follow the same rule:

• If the other two prisoners have matching hat, guess the opposite colour.
• If the other two prisoners have different colour hats, abstain.

This results in a 75% chance of victory.

Proof

If all 3 hats are the same, all 3 prisoners will guess wrong. This happens with probability \(\frac{2}{8}\). If there are 2 hats the same, and 1 different then one prisoner will guess right, and the others will abstain. This will happen with probability \(\frac{6}{8} = 75\%\).

For every possible arrangement where a prisoner \(P_i\) guesses right, there must be an arrangement where prisoner \(P_i\) guesses wrong. By having all prisoners be wrong in the same arrangement, we can cover many different arrangements where only one person guesses, and is correct.

Extension

This problem can be generalised to the case where there are \(2^k - 1\) prisoners, where \(k\) is positive integer. To do this we use the Hamming code.

We can represent the prisoners as bits, with (red, blue) being equivalent to (0, 1). For a problem of size \(2^k - 1\) We can obtain the code Hamming\((2^k - 1, 2^k - k -1)\). Let us refer to those arrangements which represent valid strings under the Hamming code as “good” arrangements.

Our strategy for each prisoner is to check if they looks like they are in a “good” arrangement. If they are, then they write down the opposite of what the arrangement says. Otherwise, they abstain.

We can see that in a “good” arrangement, everyone guesses wrong. This happens in \(2^{2^k-k-1}\) arrangements.

However, in all other arrangements, exactly one person writes down their hat colour (correctly), and all the others abstain. This is because the Hamming code corrects for one bit errors. This happens in \(2^{2^{k}-1} - 2^{2^k-k-1}\) arrangements.

This is optimal since when we are wrong, all prisoners are wrong together. However, when we are right, only one prisoner votes.

The probability that we are right, \(P\), can be given by the number of arrangements in which we are right, over the total number of arrangements:

We can see that as the number of prisoners grows we get higher chances of winning.

The best strategy for Player 1 to tell the truth if they roll higher than \(\frac{1}{e}\), or otherwise lie, reporting in the range \(\left[\frac{1}{e}, 1\right]\) according to the probability density function:

Proof

Suppose Player 1 has chosen a strategy, and has reported a value in the range \([x, x+dx]\). This is referred to as the range “near” \(x\) .

If Player 2 chooses to trust, then they will win with probability:

If Player 2 chooses to accuse, then their probability of winning depends on how often Player 1 lies “near” \(x\). Let \(L(x) dx\) be the probability that Player 1 lies and reports a value in the range \([x, x+dx]\). The probability that the roll really was in the range \([x, x+dx]\) is \(dx\). Therefore, Player 2 will win when accusing with probability:

Player 2 should only accuse if:

Now if Player 1 ever wants to report “near” \(x\) they should make sure that there are enough lies “near” \(x\) so that Player 2 is indifferent to trusting and accusing:

• If Player 1 doesn’t lie “near” \(x\) often enough, then Player 2’s best choice will be to trust. Knowing this, Player 1 can lie a little more often “near” \(x\) rather than reporting “near” \(y\) for any \(y<x\).
• If Player 1 lies too much “near” \(x\) , then Player 2’s best choice will be to accuse. Knowing this, Player 1 can lie a little less often “near” \(x\) and instead report “near” \(z\) for the largest \(z\) that doesn’t get lied “near” often enough (even if \(z < x\)).

Therefore, for any \(x\), Player 1’s best strategy will involve either never reporting “near” \(x\), or lying “near” \(x\) with probability:

We can see that this means that \(P_{accuse} = P_{trust}\), and thus Player 2 will be indifferent to trusting or accusing. Thus we can assume that Player 2 will trust.

Given that Player 2 will trust always in this strategy, Player 1 should report high values as often as possible, and never report low values. Thus values less that some \(N\) will never be reported, and values greater than \(N\) will be lied “near” with a probability \(L(x)\).

We require that the probability of lying for \(x > N\) be the same as the probability for rolling \(x < N\):

Now we require that for rolls where \(x < N\), Player 1 will lie, reporting “near” \(y\) with probability \(cL(y)\), and that the sum of all probabilities of \(y\) in the range \([N, 1] = 1\):

Giving the required probability distribution in the equation: \(p(x) = e \left( \frac{1}{x} - 1 \right)\)

Put 1 red marble in one jar, and put all the other marbles in the other jar.

Proof

For each jar we have the chance that we get a red marble will be \(\frac{\text{# red marbles in jar}}{\text{# total marbles in jar}}\) . We can maximise our chance of getting red marble in one jar by making all the marbles in that jar red.

However we would like as many marbles as possible in the other jar to have a high chance of getting red in that one also. The minimum number of marbles we can use is 1, hence we put a single marble in the first jar.

By putting the rest of the marbles in the second jar we get nearly a 75% chance of picking a red marble. Suppose we have \(n \ge 1\) of each type of marble, then the probability of finding a red marble will be:

For our problem we have \(n = 50\) , \(P = 0.7475\) .

Note that as \(n\) goes to \(\infty\) we have:

Thus for any \(n\) we can’t get better than \(\frac{3}{4}\) chance.

The last passenger has a 50% chance of finding their seat free.

Proof

From the point of view of the last passenger, it is an equivalent problem if the previous passengers all kick the distracted passenger out of the seat if it belongs to them. In this situation the distracted passenger chooses a different free seat.

They continue being dislodged until they ends up in either their own seat, or the seat of the last passenger. Both of these situations are equally likely, and hence the last passenger has a 50% chance of finding their seat free.

On average about 3 people will be taller than everyone in front of them.

Proof

Let \(E(n)\) be the expected number of people who are taller than the people in front for a line of \(n\) people.

Suppose we add a person of random height to the end of the line of length \(n-1\), so the length is now \(n\). This does not affect what any of the existing people in the line see. The person added sees everyone, and thus must be the tallest overall to be taller than everyone in front. There is a \(\frac{1}{n}\) chance that this person is the tallest out of the group of \(n\) random people. Hence:

In an empty line 0 people are taller than anyone so \(E(0) = 0\). Hence:

\(E(n) = \sum_1^n \frac{1}{n} = H_n\) where \(H_n\) is the nth harmonic number.

For our problem, \(E(11) \approx 3.02\).

No, it is impossible.

Proof

Label the grid cells with letters A-D as follows, filling in each diagonal line with each successive label:

Note that anywhere you place a 1x4 tile, it will cover one of each label A-D. Thus each letter will be covered the same number of times.

However, the grid has an unequal count of each letter. Note that each row has either two or three of each letter. Looking at just the letters A and B:

There are 5 rows with 3 As, but 6 rows with 3 Bs. Hence there is one more B than As in the grid. Thus any tiling that covers every A will leave a B uncovered.

It is not possible.

Proof

First colour the chessboard in the normal checkered pattern.

We know that a domino must cover both a black and a white square. However, both the squares missing are black. This means that no matter how you lay the dominoes there will always be two uncovered white squares, which cannot be paired with a black one.

It is not possible.

Proof

First colour the chessboard and the tetraminos in the normal checkered pattern.

There are two possible patterns for the tetraminos.

We will put the tetramino such that its colours match with the colour of the squares it is covering. Each of the first kind of tetramino adds three black squares and only one white square. Each of the second kind of tetramino adds three white squares and only one black square.

There’s an equal number of black and white squares, so there must be equally many of both kinds of tetraminos. But there are only \(15 \times 4\) squares left, so there can’t be equal numbers of each kind.

Note that in both the square and triangle case, we can divide the remaining 3 shapes again into 4 parts. We need to pick 3 of the smaller parts to make the new identical shape. If we pick the part from each of the 3 shapes that are next to each other, we automatically get the required shape.

The cut required is shown in red:

Make a vertical cut that goes through the midpoints of the original cake, and the midpoint of the missing section.

Proof

Cutting a rectangle through its midpoint will always divide it in half. Thus each half in our divided cake will have half of the original cake with half of the missing section.

This makes the size of each slice exactly equal.

The required lines are shown in red:

Join the midpoints of the outer square’s edges to create a square at a 45 degree angle. Then join the midpoints of the edges of that square to create a small square in the center.

An example solution:

To construct:

• Start with a middle row of 3 equally spaced trees.
• Place a center tree in the top row at any distance from the center.
• Place a center tree in the bottom row at the same distance from the center as the top.
• The positions of the remaining trees are forced by extending the top and bottom rows parallel with the center row.

The ball costs 5c.

Proof

Let the cost of the ball in dollars be \(x\). Then:

Commentry

This is a classic problem because the intuitive answer when hearing the problem is 10c until you stop and calculate it.

50 kg.

Proof

Being 99% water, the potatoes are originally 99 kg water and 1 kg solid. When dried, the solid weight remains the same, but is now 2% of the weight. Thus 1 kg is now 2% \(= \frac{1}{50}\)th of the weight, giving a total weight of 50 kg.

After 13 days the lily pads covered half the pond.

Since the lily pads doubles each day, on the next day the pads will double to cover the whole pond, as required.

Up to rotations and reflections, the grid must be filled in like this:

Construction

There are 8 ways to use the numbers 1-9 to add to 15:

• 1+5+9
• 1+6+8
• 2+4+9
• 2+5+8
• 2+6+7
• 3+4+8
• 3+5+7
• 4+5+6

This lines up with the 8 different 3 cell lines we need to fill in, so each sum must be used once. Count the how many times each number appears in a sum - this constraints where it can appear in the grid:

From this we can tell that:

• 5 is the only number that appears 4 times, so it must be in the center.
• The remaining odd numbers appear 2 times each, so they must be in the middle of the edges. Place 1 and 9 opposite each other, then 3 and 7 in the remaining spots. This is symmetric up to rotations and reflections.
• All the even numbers appear 3 times, so they must be in the corners. Their positions are forced by the numbers that are already filled in. e.g. 2 must be adjacent to the 7 and the 9.

The bee travels 1000 km.

Proof

We don’t need to calculate the bees back-and-forth path, which would involve calculating an infinite sum. Instead we can consider the bees journey as a whole.

Let the length of the tunnel be \(L\), the speed of the trains be \(v_t\), and the speed of the bee be \(v_b\). Also set \(t = 0\) when the trains enter the tunnel.

The trains collide at the middle of the tunnel after traveling a distance of \(\frac{L}{2}\). When this happens the time is:

During this time the bee has a constant speed of \(v_b\). Thus it travels a distance:

For this problem, \(v_b = 1000\) km/h, \(v_t = 100\) km/h and \(L = 200\) km giving \(d = 1000\) km.

The prisoner at the back will guess red if they sees an even number of red hats in front of them, or blue if they sees an odd number of red has in front of them. When the other prisoners are asked their colour, they add together the number of red hats the sees with the number of times they hear someone say red behind them. If it is even they say red, if it is odd, they say blue.

Proof

This works because the last prisoner makes known the parity of red hats for all the prisoners in front, and then the prisoners can update the parity based on what each subsequent prisoners says.

This saves the 99 people in the front with certainty, and the last prisoner with 50% chance. We can’t do any better than chance for the last prisoner as they have no information about their hat color.

First, if \(n\) is even, throw one processor out. Now start a stack of processors, initially, it is empty. Now:

• If the stack is currently empty, pick a processor from the remaining processors and push it onto the stack.

• If the stack is not empty, pick a processor and use it to test the processor on the top of the stack.

  • If the testing processor reports that the top of the stack is bad, then throw both the testing and tested processors.
  • If the testing processor reports that the top of the stack is good, the push it onto the stack so it becomes the new top.
• If the number of processors in in the stack is greater than the number of processors in the remaining pile, stop. The processor at the bottom of the stack is good.
• Otherwise repeat from the top.

Proof of correctness

If \(n\) is even there are at least 2 more good processors than bad processors, so throwing out a processor keeps the majority. Now we can assume the number of processors is odd.

Note that when processor reports that another processor is bad, at least one of the tester or the tested must be bad. This is because two good processors will never report bad when testing each other. Hence if we throw out the tester and the tested processors on every test that reports bad we preserve the fact that the good processors are in majority. Thus:

Lemma 1: The number of good processors in the stack and remaining piles combined always outnumber the bad.

Because we start out with an odd number of processors, and we only throw out processors 2 at a time, we have:

Lemma 2: The number of processors in the stack and remaining pile combined is always odd.

Every iteration we always remove one processor from the remaining pile. Therefore, unless both the stack and the remaining pile have zero processors, the remaining pile will eventually have less processors than the stack. However, by Lemma 2 we have that the number of processors in the stack and remaining pile combined can never be zero (as zero is not an odd number). Thus:

Lemma 3: Our strategy always terminates.

Now every processor in the stack reported that the one before it was good. This can only happen if the stack has zero or more good processors at the bottom, followed by zero or more bad processors. There can be no good processors on top of bad processors, otherwise the they would have reported bad when testing.

Lemma 4: If our stack contains any good processors, then they located in a contiguous chain at the bottom of the stack.

If the number of processors in the stack is greater than the number of processors in the remaining pile then:

• By Lemma 1 there must be at least one good processor in the stack.
• By Lemma 4 the processor at the bottom of the stack must be good.
• By Lemma 3 our strategy is guaranteed to terminate.

Thus our strategy always finds a good processor.

Proof of runtime

We know that the first processor never does any testing, because it is added to the chain straight away.

Furthermore the last remaining processor never does any testing:

• If the stack is empty, then it is added to the stack without being tested.
• The stack cannot have just one processor, or the total number of processors would be 2, violating Lemma 2.
• If the stack has more than 1 processor, then our strategy has already terminated, without the last processor being tested.

Each processor only performs a test when it is removed from the remaining pile. Thus each processor performs a maximum of one test each. Because the first and the last processors never perform any tests, we have that the maximum number of tests performed is \(n-2\).

First note that making the fastest person the torch-bearer and having them shuttle the others across takes 17 minutes, and thus isn’t sufficient. The time can be improved by sending the two slowest people over the bridge at the same time.

Start by searching the 2nd house. Then search each house in order up to the 16th house. Then do the same in reverse, searching from the 16th house down to the 2nd house (i.e. the 16th house gets searched twice in a row).

By the end the fugative would have been found.

Proof

First note that the fugative alternates odd and even houses because they always move to an adjacent house. This is also true for the officer for each of the two passes. Thus on each pass the officer and fugative maintain the same parity difference.

Suppose the fugative starts on an even numbered house. On the first pass the officer starts at the 2nd house, hence when the officer is searching an even house the fugative is at an even house, and similarly, when the officer is searching an odd house the fugative is at an odd house. As the officer moves along the street, the fugative can never get to the other side of the officer as the fugative can never be on either of the houses adjacent to the officer. Thus the officer will eventually find the fugative on the first pass if the fugative starts on an even numbered house.

If the fugative is not found on the first pass, then when the officer searches the 16th house for the first time the fugative must be at an odd numbered house. When the officer then searches the 16th house again for the second pass the fugative must have moved to an even numbered house.

Now on the second pass the same logic applies, except we know that the fugative starts on an even numbered house. Hence the officer catches the fugative by the time the officer reaches the 2nd house.

No, the game isn’t fair. The first player always has a winning strategy.

Proof

The following is the winning strategy for the first player:

Put the first coin exactly in the center.

Next, for each coin player #2 puts down, place one directly opposite it. That is, place it so that the center of the table is exactly half way between the two coins.

This will generate a completely symmetric layout of coins on the table. Whenever the player #2 selects a free space to place a coin in, the space opposite is guaranteed to be free as well. Since player #1 is always guaranteed an open

Use the following program:

go:
    FORWARD
    IF(CHUTE) THEN GOTO run
    BACKWARD
    FORWARD
    GOTO go
run:
    FORWARD
    GOTO run

Proof

First note that the engines always travel forwards overall. Since they are both facing the same direction they will continue going forward (in the go loop) at the same speed until the one who is following finds the parachute of the other. It will then start moving at a faster speed than the first (in the run loop), as it no longer has to do a BACKWARD FORWARD every iteration. Thus it will eventually catch the first.

First number the three people, #1, #2 and #3. Let the salary of person \(i\) be \(s_i\). Also, make each person come up with a random number \(r_i\).

Then use the following strategy:

• #1 writes the value \((s_1 + r_1)\) on a piece of paper and hands it to #2.
• #2 adds the value \((s_2 + r_2)\) to the value they see on the paper that #1 gave. They write this new value \((s_1 + s_2 + r_1 + r_2)\) on a new piece of paper and hand it to #3.
• #3 adds the value \((s_3 + r_3)\) to the value they see on the paper that #2 gave. They write this new value \((s_1 + s_2 + s_3 + r_1 + r_2 + r_3)\) on a new piece of paper and hand it to #1.
• #1 subtracts \(r_1\) from the value they see on the paper that #3 gave. They write this new value \((s_1 + s_2 + s_3 + r_2 + r_3)\) on a new piece of paper and hand it to #2.
• #2 subtracts \(r_2\) from the value they see on the paper that #1 gave.= They write this new value \((s_1 + s_2 + s_3 + r_3)\) on a new piece of paper and hands it to #3.
• #3 subtracts \(r_3\) from the value he sees on the paper that #2 gave. They then divide the result by 3 to obtain the average \(\frac{s_1 + s_2 + s_3}{3}\), which they tell everyone.

Add all the numbers, then subtract the total from 5050 (the sum of the numbers from 1 to 100). The result is the missing number.

Number the bottles 0 to 999. Number the servants 0 to 9. Each servant drinks from bottles whose number has its \(i\)th bit set to 1.

After waiting for 24 hours, see which servants have died. Discard the bottle whose \(i\)th bit is 1 if the \(i\)th servant died, but 0 otherwise. This uniquely identifies the bottle.

In general this can be done for \(n\) bottles as long as the king has at least \(\lceil \log_2 n \rceil\) servants.

• Every prisoner starts off with a count of 1.
• Designate one prisoner as the “collector”.
• If the light is off when a prisoner enters the room, and their count is 1, they turn the light on and decrease their count.
• If the light is on when the collector enters the room, they turn the light off and increase their count.
• When the collector’s count reaches 100, they notify the warden.

Proof and runtime

Every prisoner turns on the light at most once. The light is initially off, so when the collector has seen the light come on 99 times they knows that all other prisoners have been in the room. At this point the collectors count will be 100 and they alert the warden.

The probability \(p\) for a previously uncounted prisoner to arrive between the collectors visits (given \(n\) prisoners and \(x\) uncounted prisoners) is:

The expected time between visits for the collector is \(n\) days. Thus the expected time taken for a collector to see the light turn on is:

Thus the expected time for the prisoners to escape is:

When \(n = 100\) this evalutes to about 10418 days, or about 28.5 years.

Note that this is not optimal. There are trivial improvements to this algorithm such as dynamically choosing the collector. For example, selecting the prisoner brought in on the second day, they can immediately count the prisoner on the first day and shorten their stay by an average of \(n\) days.

The algorithm for a known state already works if the prisoners don’t know how often they are brought to the room, so we just need to deal with the unknown state.

• Every prisoner starts off with a count of 1.
• Designate one prisoner as the “collector”.
• If the light is off when a prisoner enters the room, and their count is 1, and they have previously observed the light in both states (on and off), they turn the light on and decrease their count.
• If the light is on when the collector enters the room, and they didn’t turn it on, and it is not their first time in the room, they turn the light off and increase their count. In all other cases they toggle the light switch.
• When the collector’s count reaches 100, they notify the warden.

Proof

As with the algorithm for a known state, every prisoner turns on the light at most once.

The collector is always the first prisoner to change the initial state of the light switch. When a prisoner has seen the light in the both states, they can be sure that the collector has started counting. Hence, when a prisoner turns on the light the collector will count it.

If no other prisoners are turning on the light, the collector is toggling the light on and off between visits. This ensures that eventually all prisoners will see the lightbulb in both states.

Note that this solutions here is not optimal, it is a simple example of feasibility.

Let \(n\) be the number of prisoners. The previous algorithms can be easily adjusted to take advantage of multiple states with the following differences:

• The collector resets the state to 0 (in the unknown initial state problem they toggle between 0 and the maximum value).
• Prisoners increment the state unless it is already at its maximum value.
• The collector increments their count by the value they see.

This will reduce the expected runtime by a factor equal to the number of switch states, when there are up to \(n - 1\) states.

If there are \(n\) or more states the first time a prisoner visits the room they update the switch from \(x\) to \(x + 1 \mod n\). The first prisoner to see the switch set to \(x \mod n\) (where \(x\) is the value they first saw) can alert the warden that all prisoners have visited the room.

This works even when the initial state and time between visits is unknown. The expected runtime for this is:

For \(n = 100\) this is about \(519\) days.

As with the previous algorithms, this solution is not optimal.

This can be solved for any board with \(2^k\) squares. For a chessboard \(k = 6\).

Index the squares \(0, 1, \ldots, 2^k - 1\) and let:

Determine the xor sum of the squares whose coins show heads:

Let the index of the Magic Square be \(m\). Flip the coin of the square \(m \oplus a\). The magic square can be determined as the xor sum of all the squares which show heads:

Proof

Let the index of the square flipped be \(r\):

Given this, \(S_i\) can be defined as:

The using the properties of xor:

This is the same as the equation to determine the square, thus we correctly find the magic square.

Alternative proof

Let \(n\) be the number of squares and define \(k\) such that \(n = 2^k\). We will create \(k\) sets \(C_i \mid 0 < i \le k\) where:

We can see by construction that each square is in a unique subset of sets \(C_i\), and thus can be identified by which sets it is a member of. This can be seen by the fact that the set membership can be read off the binary representation of the square’s index.

Define the parity of \(C_i\) as the parity of the the number of heads in \(C_i\). Then the initial calculation (\(a = \bigoplus \left( i S_i \right)\)) calculates the parity of \(C_i\) as the \(i\)th bit of the result \(a\).

We wish to change the parity of the sets \(C_i\) so that they reflect the parity of the bits in \(m\). That is we want to flip a coin that is in all sets \(\left\{ C_i \mid \text{ parity } C_i \ne i \text{th bit of } m \right\}\). This is exactly what \(m \oplus a\) calculates.

Now the bits of \(m\) can be read off as the parity of the sets \(C_i\).

Boards with \(n \ne 2^k\) squares

If \(n\) is not a power of 2 then there is no possible solution. Note that there are \(2^n\) possible board states and we want to transmit one of \(n\) value. Each board state has \(n\) adjacent states it can transition to with the flip of a coin (one for each coin we can flip).

For any mapping there must exist a value which maps to at most \(\left\lfloor \frac{2^n}{n} \right\rfloor\) states by the pigeon-hole principle. This value can be adjacent to at most \(n \left\lfloor \frac{2^n}{n} \right\rfloor\) states.

\(n \left\lfloor \frac{2^n}{n} \right\rfloor < 2^n\) unless \(n | 2^n\). \(n | 2^n\) is only true when \(n\) is a power of 2. Thus if \(n \ne 2^k\) a solution is not possible because in any given strategy there will be some values which can’t be reached from all states.

Let:

• F stand for the farmer
• W stand for the wolf
• G stand for the goat
• H stand for the hay

The side with the boat is surrounded with brackets.

Let:

• T stand for a thief
• A stand for an assassin

The side with the boat is surrounded with brackets.

Let:

• F stand for the father
• M stand for the mother
• W stand for a female friend (woman)
• G stand for a male friend (guy)
• S stand for the son
• C stand for the dog (canine)

The side with the boat is surrounded with brackets.

We will generate an algorithm by induction.

The base case is trivial, we start with an empty room and then let the one person in. This covers both possible states.

Now, assume that we have a solution for \(n\) people. We will show that we can construct a solution for \(n+1\) people. Note that the solution for \(n\) people also works in reverse, because the change will still be .

• We start by running the solution for \(n\) people - this covers all combinations which exclude the last person.
• Now we let the last person in and then run the solution for \(n\) people in reverse - this covers all combinations which include the last person.

At the end of the process, the last person will be the only one in the room.

This is known as a Gray code.

Look the grid of integer points on the Cartesian plane. Starting at \((0,0)\), visit each point in turn one every minute. Fire at \(f(t) = x + y t\) . This will guarantee to eventually hit the sub.

Proof

Let the sub’s position be given by \(s(t) = x_0 + v t\) . Note that both \(x_0\) and \(v\) are the set of integers ( \(\mathbb{Z}\) ). Since \(\mathbb{Z}\) is countable, we know that the set of all trajectories is countable also, as it is of size \(\mathbb{Z}^2\) .

Thus if we enumerate all possible trajectories and try each on in turn, we will eventually hit the sub.

In fact, this works if the sub can move to any rational number, algebraic number or any other countable set.

Color the intersections as follows so that every move alternates between red and blue nodes, apart from the top node:

In the starting position, both the spider and the fly are on the same color. As long as the spider and fly stay on the red and blue nodes, they will always be on the same color after they both move. In this case the spider can’t catch the fly because the spider will always be forced to move to a node of the opposite color to the fly on its turn.

The only way to change this is to move up to the top green node. Once at the green node the spider can move so that it is on the same color as the fly after the spider’s move. The spider has changed the relative parity of their positions.

After this it can corner the fly by moving towards the fly’s position. The fly can’t get past the spider, because the spider controls of all the nodes around it. Since these controlled nodes are now the same color that the fly wants to move into, it controls the fly’s mobility.

Once in a corner, the fly has no choice but to move to a node where the spider can move to and catch it.

This is a type of Pursuit-evasion problem.

Ask “Is Bob a liar?” Only Bob will answer “No”.

Proof

There are four possibilities:

• You speak to Bob and he tells the truth: “No”.
• You speak to Bob and he lies: “No”.
• You speak to his brother and he tells the truth: “Yes”.
• You speak to his brother and he lies: “Yes”.

So it can be seen that Bob will always answer “No” and his brother will always answer “Yes”.

Ask a question to which you both know the answer. For example, “Are you a mushroom?”

They can’t both be knaves, otherwise the inhabitant would have lied about it. Hence the statement was a lie, and the speaker was a knave. This means the other must be a knight.

Since the statements are different their types must be different, hence the second person is speaking the truth and is a knight. The first must therefore be a knave.

You need 8 questions.

Proof

There are \(\binom{10}5 = 252\) possible combinations you need to disambiguate. This requires a minimum of \(\lceil log_2(252) \rceil = 8\) questions.

One strategy for this is to first identify one of the villagers. Ask one of the villagers a question with a known answer (e.g. “Are you a mushroom?”) to determine if they are a knight or a knave. We will now be able to reliably determine the truth based on their answers - if they are a knave we just need to invert their responses.

This leaves us with 7 questions to disambiguate the remaining \(\binom{9}{5} = 126\) combinations, which is less than \(2^7 = 128\) hence is still possible.

You thus use the identified villager to binary search through the possible combinations.

Ask “If I chose a stone out of the two that you didn’t pick, would it be darker than yours?”

• If they have a black stone, they answer “No”.
• If they have a white stones, they answer “Yes”.
• If they have a grey stone, they must say “I don’t know”.

Ask one of the gods “If I were to ask the other god which path leads to heaven, what would he say?” Then take the opposite path.

Proof

First let us consider the question “Which path leads to heaven?”

To this the truthful god will point to the path to heaven, and the lying god will point to the path that leads to hell.

Now if we look at the question given in the solution, the truthful god will answer honestly and point to the path to hell (which is what the lying god would say leads to heaven). The lying god will also point to the path that leads to hell, because the it is the opposite of the path that the truthful god would say leads to heaven.

Thus whoever you ask, they will point to path that leads to hell. We simply pick the other path.