33rd CanMO 2001 Problem 2 The numbers -10, -9, -8, ... , 9, 10 are arranged in a line. A player places a token on the 0 and throws a fair coin 10 times. For each head the token is moved one place to the left and for each tail it is moved one place to the left. If we color one or more numbers black and the remainder white, we find that the chance of the token ending up on a black number is m/n with m + n = 2001. What is the largest possible total for the black numbers?
The token must end on an even number, so clearly we color 1, 3, 5, 7, 9 black and -1, -3, -5, -7, -9 white. Let p(n) be the probability of the token ending up on n. Then p(10) = p(-10) = 1/1024, p(8) = p(-8) = 10/1024, p(6) = p(-6) = 45/1024, p(4) = p(-4) = 120/1024, p(2) = p(-2) = 210/1024, p(0) = 252/1024. 2001 = 3.23.29, so if m+n = 2001, then m = ka, n = kb, where a < b are coprime and k = 1, 3, 23, 29, 69, 78, 667 or 2001. b must be a power of 2, so the possibilities are: a/b = 0/1, 1/2, 7/16, 13/16, 5/64, 23/64, 155/512, 977/1024. Hence the probability must be h/1024 where h = 0, 512, 448, 832, 80, 368, 310 or 977. We find that the only possibilities are 0, 512 = 252 + 120 + 120 + 10 + 10, 512 = 210 + 210 + 45 + 45 + 1 + 1, 310 = 210 + 45 + 45 + 10 = 977 = 252 + 210 + 210 + 120 + 120 + 45 + 10 + 10. These give sums (for the even numbers) of 0, 0, 0, 10, 6. So the best is 10, obtained by coloring black the even numbers 2, 6, -6, 8. Thus we color -6, 1, 2, 3, 5, 6, 7, 8, 9 black and the rest white for a total of 45, giving a probability of 310/1024 = 155/512 = 465/1536, where 465 + 1536 = 2001. 33rd CanMO 2001 © John Scholes jscholes@kalva.demon.co.uk 10 June 2002