Oh no! There are eight colonies of zombies, two that consist of just two zombies, and the other six consisting of 4, 8, 16, 32, 64, and 128 zombies, respectively. At random, pairs of zombie colonies merge, and when they do, the merged colony will have a number of zombies equal to half the product of the numbers of zombies in the two merging colonies. These mergers keep occurring until there is just one huge colony.
What is the largest number of zombies that final colony might contain?
Revenge on the Zombies
Hurray! The zombies have nearly been defeated. They are down to exactly 19 groups, each of which consists of either four or five zombies. The total number of zombies remaining is a multiple of 17.
How many groups of five zombies are there?
|Spread the word:||Tweet|
Solutions to week 101
Heads Up. Note that the game is symmetric between Hadley and Taylor, so Hadley’s chance of winning is exactly half of the probability that the game is not a tie. A tie can certainly occur if both Hadley and Taylor flip one of the sequences T, HT, HHT, HHHT, etc. But as the very helpful reader Ian Sutherland pointed out, correcting an earlier error in this solution, a tie can also occur if one of Taylor or Hadley flips HT and the other flips TH, or if one of Taylor or Hadley flips HHT and the other flips HTH or THH, and so on.
In general, let the event Tn be that the game ends in a tie after n flips by both Taylor and Hadley. These events are all disjoint (there is no way that more than one of them can happen) so the overall probability of a tie is the sum of the probabilities of the Tn for all n.
Focusing on a specific n, if the game ends after n turns, there have been 2n flips, so there are 4n possible outcomes for those flips. Out of those, the only ones that result in a tie consist of: both Hadley and Taylor flipping n-1 Hs followed by a T (1 possibility), Hadley flipping that and Taylor flipping n-1 Hs with a single T in some position other than the last (n-1 possibilities), and vice versa (n-1 possibilities), for a total of 2n-1 possibilities. Hence the probability of Tn is (2n-1)/4n.
So to get the overall probability of a tie, we need to sum this quantity over all n. We will assume that the sum of this series exists (which is a technicality not difficult to check using standard techniques) and let S = 1/4 + 3/16 + 5/64 + 7/256 + … be the sum. Then 4S = 1 + 3/4 + 5/16 + 7/64 + 9/256 + …, so that 3S = 4S – S = 1 + 2/4 + 2/16 + 2/64 + 2/256 + … But 2/4 + 2/16 + 2/64 + 2/256 + … is an ordinary geometric series, so its sum is (1/2)/(1 – 1/4) = 2/3 by the standard formula for the sum of a geometric series.
Therefore, 3S = 1 + 2/3, so S = 5/9. That means there is a 5/9 probability that the game ends in a tie, and a 4/9 probability it does not end it a tie, so a 2/9 probability that Hadley wins.
Balanced Flip. How likely is a balanced flip with 2n coins? Well, there are 22n outcomes of the flip, and for the flip to be balanced, exactly (but any) n must come up heads, so there are 2n choose n balanced flip outcomes. Thus, the probability of a balanced flip is [(2n)!/n!n!] / 22n = (2n)! / 22nn!n!. To figure out for what n this probability will be highest, we look at the ratio of this probability for 2n coins and for 2(n+1) coins, namely (2n)!22n+2(n+1)!(n+1)! / (2n+2)!22nn!n! = 4(n+1)(n+1) / (2n+2)(2n+1) = (2n+2)/(2n+1). You can see that this ratio is greater than one for all positive n, and so we conclude that the greatest probability of a balanced flip corresponds to the smallest positive value of n, namely two coins.
Links to all of the puzzles and solutions are on the Complete Varsity Math page.
Come back next week for answers and more puzzles.