4 ms·
I know another problem with the same solution. Imagine a ferry with n cars that drive on land onto a narrow road that prevents passing, and each car has a uniqu
by drsopp 7y ago
I know another problem with the same solution. Imagine a ferry with n cars that drive on land onto a narrow road that prevents passing, and each car has a unique random preferred speed > 0. The cars start driving and starts clumping together in groups. The expected number of groups is the harmonic series up to n.
- kmm 7y agoIf 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.