Browse · MathNet
PrintJapan Mathematical Olympiad
Japan counting and probability
Problem
8 coins are placed on a line from left to right. In the sequel, we keep on repeating the following action: Choose at random a coin showing a head and satisfying the following condition: Condition: Either there is no coin on its right showing a tail, or there is no coin on its left showing a tail. Suppose we keep on repeating this action until there remains no coin showing a head and satisfying the condition stated above. Determine the expectation of the number of coins showing a head when the actions end.
Solution
It is clear that the conclusion would be the same if we follow the following procedure instead of the procedure specified in the statement of the problem: First we assign one of the numbers to the coins already lined up in a random way (so that each of ways of assigning the numbers has the same probability.) Then we start with the coin with number assigned to check whether it satisfies the condition of the problem. If it does, turn the coin to show the tails; if not, then leave the coin as it is. Then we do the same with the coin with number assigned, and keep on doing the same with all the coins in the increasing order of the numbers assigned. Now, consider the probability that the coin placed on the -th spot from the right will be turned to show tails. The desired expectation will be the sum over of the corresponding probabilities.
When the time comes for the coin placed on the -th spot from the right to be examined, the event that there is no coin to the right of it which shows the tails corresponds precisely to the event that the number assigned to it is less than each of the numbers assigned to the coins placed on its right. The probability of the latter event is the same as the probability that the number assigned to a coin chosen at random from randomly chosen coins to be the smallest of the numbers assigned to the initially chosen coins, and this probability is obviously .
Since the coin placed at the -th spot from the right is placed at the -th spot from the left, a similar argument as above shows that the probability that there is no coin showing tails placed to the left of this coin is .
Finally, the event that there is no coin either to the left or to the right of this coin showing tails is the same as the event that the number assigned to this coin is the smallest number , and hence this probability is .
Thus the probability that this coin will be turned to show the tails is , and the desired value of the expectation is
When the time comes for the coin placed on the -th spot from the right to be examined, the event that there is no coin to the right of it which shows the tails corresponds precisely to the event that the number assigned to it is less than each of the numbers assigned to the coins placed on its right. The probability of the latter event is the same as the probability that the number assigned to a coin chosen at random from randomly chosen coins to be the smallest of the numbers assigned to the initially chosen coins, and this probability is obviously .
Since the coin placed at the -th spot from the right is placed at the -th spot from the left, a similar argument as above shows that the probability that there is no coin showing tails placed to the left of this coin is .
Finally, the event that there is no coin either to the left or to the right of this coin showing tails is the same as the event that the number assigned to this coin is the smallest number , and hence this probability is .
Thus the probability that this coin will be turned to show the tails is , and the desired value of the expectation is
Final answer
621/140
Techniques
Expected valuesInclusion-exclusion