OK, I watched the video and they used the same solution. I was hoping to also see a proof that this solution is indeed minimal - but there wasn't.
Can we prove this? I've given it some thought and I think I can prove that this is impossible with 6 or less races.
We will deal with different arrangements of the first 5 races:
The simplest case is where 19 or less horses participated in these first 5 races. This means we have only one more race and 6 or more horses, so at least one horse will not participate in any race - which is obviously a wrong solution.
The case where 20 horses participated in the first 5 races is also simple - if the final race will have these 5 horses, we will not be able to compare them to the 20 horses from the first 5 races, so this arrangement is also wrong.
The case where all 25 horses participated in the first 5 races. This means these 5 races were disjoint. Here we need to split the sixth race:
If we pick the first horse of each group, we won't know how the second and third places of that final race are compared to the second and third places of the original group of the winning horse - so this solution is wrong.
If we pick a different horse from at least one group, and that horse does not reach first place - we won't be able to tell how the leading horse of that group compares to the winner of the last race, so this solution is also wrong.
The case where between 21 and 24 horses participated in the first 5 races. Let N be the number of horses who did not participate. For each such horse, there is a link between two groups of 5 horses (one horse that participated in both). At best this link turns these two groups into a single group where we know the order (same horse finished last in one group and first in the other). This means that the horses from the first 5 races can be grouped to 5-N groups. Each of the horses that did not participate is a group of a single horse - so in total we have N+(5-N)=5 groups. Note that:
We need to pick a horse from each such group - or else we won't be able to compare the group that wasn't chosen with the other groups.
We must pick the fastest horse of each group - because if we pick another horse and it isn't the first we won't be able to determine which horse is the fastest.
At least one group has more than one horse.
Now - since we can compare the second horse of the group with more than one horse with the second horse of the final race - we can't determine the total second place, and this case is also a wrong solution.
We have shown that with 6 races, not only is it impossible to determine the top 3 horses - it is also impossible to determine the top 2! I suspect the number 3 was chosen because you can't find more than that with only 7 races - but the proof for that is left as an exercise to the reader.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
OK, I watched the video and they used the same solution. I was hoping to also see a proof that this solution is indeed minimal - but there wasn't.
Can we prove this? I've given it some thought and I think I can prove that this is impossible with 6 or less races.
We will deal with different arrangements of the first 5 races:
The simplest case is where 19 or less horses participated in these first 5 races. This means we have only one more race and 6 or more horses, so at least one horse will not participate in any race - which is obviously a wrong solution.
The case where 20 horses participated in the first 5 races is also simple - if the final race will have these 5 horses, we will not be able to compare them to the 20 horses from the first 5 races, so this arrangement is also wrong.
The case where all 25 horses participated in the first 5 races. This means these 5 races were disjoint. Here we need to split the sixth race:
The case where between 21 and 24 horses participated in the first 5 races. Let N be the number of horses who did not participate. For each such horse, there is a link between two groups of 5 horses (one horse that participated in both). At best this link turns these two groups into a single group where we know the order (same horse finished last in one group and first in the other). This means that the horses from the first 5 races can be grouped to 5-N groups. Each of the horses that did not participate is a group of a single horse - so in total we have N+(5-N)=5 groups. Note that:
We have shown that with 6 races, not only is it impossible to determine the top 3 horses - it is also impossible to determine the top 2! I suspect the number 3 was chosen because you can't find more than that with only 7 races - but the proof for that is left as an exercise to the reader.