Brucewayne
New member
- Joined
- Sep 14, 2020
- Messages
- 1
Task
Let some battle take place on a map that has several convenient positions for firing (for simplicity, we will assume that all these positions are set in one line from left to right).
Each of these positions are protected on the right — this means that the shooter can only be hit if someone shoots at him from the position to the left of the given shooter.
The commander decided to take 10 such positions and put one shooter of each level there (there are 10 shooter levels totally — from the first to the tenth). Let's assume that any shooter cannot shoot any other shooter on a higher level. After placing the shooters, the commander noticed that some shooters could hit others. He decided to randomly choose two shooters with equal probability and, if one of them could hit the other, swap these shooters. Obviously, after such a rearrangement, these shooters will no longer be able to hit each other. The commander continued to carry out this operation (randomly choose two shooters and, if necessary, swap them) X times until peace comes — none of the shooters can shoot anyone. Since the couples of shooters are chosen randomly, X is a random variable. It is required to find its mathematical expectation.
Example:
Input data:
[1,2,3,4,5,6,7,8,10,9]
Output:
45.0
Problem:
I understand that only a level 10 shooter can hit a level 9 shooter. Therefore, in order to swap them, on average commander needs to select 45 random pairs of shooters (C102 = 45). But what about other options for the location of the shooters? For example [1,2,3,4,5,6,7,10,8,9] or [1,2,3,10,9,8,4,5,6,7] etc. Any ideas?
Let some battle take place on a map that has several convenient positions for firing (for simplicity, we will assume that all these positions are set in one line from left to right).
Each of these positions are protected on the right — this means that the shooter can only be hit if someone shoots at him from the position to the left of the given shooter.
The commander decided to take 10 such positions and put one shooter of each level there (there are 10 shooter levels totally — from the first to the tenth). Let's assume that any shooter cannot shoot any other shooter on a higher level. After placing the shooters, the commander noticed that some shooters could hit others. He decided to randomly choose two shooters with equal probability and, if one of them could hit the other, swap these shooters. Obviously, after such a rearrangement, these shooters will no longer be able to hit each other. The commander continued to carry out this operation (randomly choose two shooters and, if necessary, swap them) X times until peace comes — none of the shooters can shoot anyone. Since the couples of shooters are chosen randomly, X is a random variable. It is required to find its mathematical expectation.
Example:
Input data:
[1,2,3,4,5,6,7,8,10,9]
Output:
45.0
Problem:
I understand that only a level 10 shooter can hit a level 9 shooter. Therefore, in order to swap them, on average commander needs to select 45 random pairs of shooters (C102 = 45). But what about other options for the location of the shooters? For example [1,2,3,4,5,6,7,10,8,9] or [1,2,3,10,9,8,4,5,6,7] etc. Any ideas?