Puzzle Nekst 1 ’14-’15
For those of you who seek a challenge outside their regular courses, we offer you a new puzzle. As the summer has ultimately vanished, for this puzzle we will focus on the wonderful word this autumn will bring us.
An ant is situated on a corner of a cube and diagonally across it is a spider. While the spider remains seated, the ant moves randomly over the edges. As the ant moves rather slow, every edge takes him five minutes to cross. When the ant reaches the vertex of the spider, nature has its way and the ant will get eaten. The question remains: how long will it take for the ant to die?
Please send your solution to Nekst@Asset-Econometrics.nl before the 21st of November. A crate of beer or a delicious pie, whichever the winner prefers, will be waiting for whoever has the best (partial) solution. Please note that as before, every recipient of this magazine is eligible to send in their solution, so members of the department are invited to participate as well. Good luck!
Tim Laurensse is the winner of the previous puzzle. As a reward, he can come and pick up a crate of beer or a pie at room E1.10. As already mentioned in Nekst 1, the solution to the puzzle in Nekst 4 2013-2014 is 1/3. If T denotes tails and H denotes heads, the four optimal triplets of coin flips for player 1 are HTH, HTT, THH and THT. The optimal strategies of player 2 to these strategies are HHT, HHT, TTH and TTH, respectively. One might wonder how these optimal strategies for player 2 can be found. Player 2 simply takes the opposite of player 1’s second call first and afterwards adds the first two calls of player 1 as his second and third. This might seem kind of random, but the following explanation will show why this works. Suppose player 1 chooses the strategy HHH and the first three flips do not compose this exact triplet. Since we are looking for the first occurrence of this sequence the position in front of the sequence will be tails by definition. Suppose, for example, that HHH has its first occurrence in position 6, 7 and 8. Then position 5 has to be tails, since otherwise the first occurrence of HHH would be 5, 6 and 7. Using this argument, one finds that player 2 should always reverse the second call of player 1 in order to build an optimal strategy. The only reason that this strategy does not guarantee a win for player 2 is that player 1’s sequence could occur on the positions 1, 2 and 3.
For explaining the calculation of the odds, player 1’s strategy HTH will be used. The other calculations are very similar to this. Recall that player 2’s optimal response to HTH is HHT. The probability that player 2 wins can be divided into four scenarios, in other words, the four different pairs one can make, HH, HT, TH and TT. The probability that player 2 wins is the sum over the four scenarios of the product of the probability that player two wins given a scenario and the probability of that scenario. Mathematically:
The probabilities of the individual scenarios are easy to find, they are all equal to ¼. The conditional probabilities are slightly harder. The probability that player 2 wins given HH can once again be split into two scenarios: the probability that player 2 wins given HHH times the probability of H and the probability that player 2 wins given HHT times the probability of T. The probability of H and T is obviously ½ and the probability that player 2 wins given HHT is obviously 1. The probability that player 2 wins given HHH is equal to the probability that player 2 wins given HH, since the coin has no memory. This expansion can be done for every one of the four scenarios which yields four equations with four unknowns. In the end, the result is that player 2 has a probability of 2/3 to win the game when these strategies are played. Therefore, player 1 has a probability of 1/3 to win.
