Internet Math Challenge

Solution to the puzzle for 7 March 2003

The probability that card 5 will end up in position 1 is 512/3125 (or 16.384%.

The easiest way to get this answer is to realize that there are 5⁵ = 3125 possible outcomes for the 5 successive random number draws, and then to count how many of those outcomes put card 5 on top at the end. There are two ways that card 5 can end up on top:

It can get placed on top on the first random number draw (by switching places with card 1) and then stay there for the other four draws. For this to happen the first random number must be a 5 and then the other four draws can be any of the other four numbers (but cannot be 5). This happens in 1*4*4*4*4 = 256 outcomes.
Card 5 could be left alone for the first four draws, and then get switched with card 1 on the last draw. There are also 4*4*4*4*1 = 256 outcomes that do this.

No other combination of draws will place card 5 on top at the end, so our total is 256 + 256 = 512 -- thus 512 out of the 3125 outcomes put card 5 on top.

There is another (longer, but perhaps more instructive) way of solving this puzzle. We can simply compute the various probabilities for the location of card 5 after each draw. on the first draw, each of the numbers 1 through 5 are equally likely. But if the number comes up 1-4, card 5 will just remain where it is. If 5 is drawn then card 5 will move to position 1. So, after the first draw:

There is a 1/5 probability it will be in position 1.
There is a 4/5 probability it will be in position 5.

Now after the second draw:

There is a (1/5)*(4/5) = 4/25 probability card 5 will be in position 1 -- for one-fifth of the time it will be there after the first draw, and four-fifths of those times it will be left there in the second draw.
There is a (1/5)*(1/5) + (4/5)*(1/5) = 5/25 = 1/5 probability it will be in position 2 -- for one-fifth of the time it will be in position 1 after the first draw, and one-fifth of those times the second draw will move it to position 2, but also four-fifths of the time it is in position 5 after the first draw, and again one-fifth of those times the second draw will move it to position 2.
There is a (4/5)*(4/5) = 16/25 probability it will be in position 5 after the second draw.

Note that the three probabilities after the second draw add up to 1, as they should: 4/25 + 1/5 + 16/25 = 1.

Continuing this slightly tedious process for three more draws yields the following:

There is a 2*(1/5)*(4/5)⁴ probability that card 5 will be in position 1 after the last draw.
There is a (1/5)*(4/5)³ + (1/5)*(4/5)⁴ probability that card 5 will be in position 2 after the last draw.
There is a (1/5)*(4/5)² + (1/5)*(4/5)⁴ probability that card 5 will be in position 3 after the last draw.
There is a (1/5)*(4/5) + (1/5)*(4/5)⁴ probability that card 5 will be in position 4 after the last draw.
There is a 1/5 probability that card 5 will be in position 5 after the last draw.

It's interesting to note that the most likely location for card 5 to end in is position 4 -- strange!

Thanks to these sponsors for their generous support of the IMC!