1
$\begingroup$

Assume you have 8 horses and you can race any 5 of them at time. After every race you get the 3rd and 4th fastest among them. How will you find the fastest among them? What would be the general approach if this was n horses?

More than the solution I wanted to know your intuition or approach for this type of problems.

$\endgroup$

marked as duplicate by Bass, A J, rhsquared, JMP, ManyPinkHats Dec 15 '18 at 10:19

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3
$\begingroup$

The task is impossible.

One approach:

As you've set the problem, it's not possible to identify the fastest horse. It will always be impossible to distinguish between the fastest and the second-fastest horse, regardless of what races you run.
In any race with both, they will come first and second respectively. As you are only told which horses come third and fourth, you will never see these horses in the race results. Whether they come first-and-second or second-and-first, the race results are identical; since they can be swapped without changing visible results, they are indistinguishable.
In any race with only one, they will come first. As you are only told which horses come third and fourth, you will never see these horses in the race results. Again, whether they come first-and-not-entered or not-entered-and-first, the race results are identical; since they can be swapped without changing visible results, they are indistinguishable.
In your limited results view, for every single race, it is impossible to distinguish between the two of them.

Another approach:

Previously, I mentioned that because the slowest horse will never be in the results, it is also indistinguishable. This is incorrect, as Deusovi proves in the linked duplicate.
While it is true the slowest horse will never be in the results, it is possible to use the information to still identify it. For more details, see Deusovi's answer here.

$\endgroup$
  • $\begingroup$ That was my first impression too, but it's actually possible to distinguish the slowest if you have at least six! (See my answer in the linked duplicate.) $\endgroup$ – Deusovi Dec 15 '18 at 14:05
  • $\begingroup$ @Deusovi but in no way can we distinguish the first 2 right.If is was given that the 6 horses are either in increasing order or decreasing then what is the minimum number of steps to find that out. $\endgroup$ – Srin Chow Dec 15 '18 at 19:19
2
$\begingroup$

After each race we get two horses that for sure aren't the fastest. So we can take them out and race another set of 5 and so forth. However, I don't know how we can make a difference between the top 2 horses (who are never 3rd/4th) and the slowest one (who's also never 3rd/4th).

$\endgroup$
  • 1
    $\begingroup$ I was thinking something like that as well. Maybe just keep qualifying the worst ones, and the ones that don't make the list as worst, we keep? $\endgroup$ – Crille123 Dec 15 '18 at 9:00

Not the answer you're looking for? Browse other questions tagged or ask your own question.