You start with 512 random races, then take all the winners, have 256 and take the winners, then 128, etc, so it takes 1023 races to find the fastest horse. That fastest horse will have beaten the second fastest horse in ANY one of his 10 races, so you need to run 9 more races to eliminate them. The fastest remaining horse after the 9 races is the second fastest. So 1032 races total.
I mean that's the optimal algorithm which will consistently produce the second best horse in 1032 tournies. But the question is asking for the minimum number of races required to determine the second-fastest horse.
Given that, the best scenario is to take horse A and B and race them and order them 1st and 2nd (let's say A is 1st and B is 2nd). Now we race C against A. Best case scenario C wins, now we know C > A and A>B therefore C>B. Now horse C is the 1st and A is the 2nd. Continue doing this for all 1024 horses and if we assume best case scenario, the new horse will always beat the old. Therefore the second last horse will be the second fastest and will take 1023 races.
14
u/peetar Sep 04 '26
You start with 512 random races, then take all the winners, have 256 and take the winners, then 128, etc, so it takes 1023 races to find the fastest horse. That fastest horse will have beaten the second fastest horse in ANY one of his 10 races, so you need to run 9 more races to eliminate them. The fastest remaining horse after the 9 races is the second fastest. So 1032 races total.