4 ms·
If anyone is interested in a proof, I think this works: The slowest car will with probability 1 be the first car in its own clump. The second slowest car will
by kmm 7y ago
If anyone is interested in a proof, I think this works:
The slowest car will with probability 1 be the first car in its own clump. The second slowest car will be the first car in a clump if it is in front of the slowest car. This happens with a probability of 1/2. The third slowest car will form a clump without the second and first slowest cars if it is in front of both of them, which will happen with probability 1/3. The fastest car will only form its own clump if it's the first car, which will happen with probability 1/n.
So the total number of clumps will be 1 + 1/2 + 1/3 + ... + 1/n
- drsopp 7y agoBeautiful.
- leni536 7y agoIt's a very nice proof. Note that this implicitly relies on a great trick used in probability theory, namely that E(X_1 + X_2 + ... + X_n) = E(X_1) + E(X_2) + ... + E(X_n), even if the random variables are not independent. In this specific case X_i = "the number of clumps where the ith slowest car is in front of" which is either 0 or 1.