3
$\begingroup$

Given 8 horses and you can race any 5 of them and after every race you get the 2nd and 3rd fastest horse how would you find the fastest horse in minimum number of steps. Well the minimum number of step here is important.Eariler i asked something similar and found that it was not possible so i am now asking a possbile variation of that question

link to previous question : Intuition or Approach for this problem

original question Link :Out of six numbers in some order, we know third and fourth ranked numbers in every five out of the six numbers. Find the first

$\endgroup$
  • 1
    $\begingroup$ Do you get the 2nd and 3rd fastest horses in order? $\endgroup$ – obl Dec 17 '18 at 16:41
  • 1
    $\begingroup$ Hey, I edited my answer (the second one I posted) and found a better solution. Check it out, please. $\endgroup$ – Victor Stafusa Dec 18 '18 at 14:06
  • $\begingroup$ Can we assume the horses run the race at the same speed each time they run? Seems pretty unrealistic, but pretty impossible to figure out if not ;) $\endgroup$ – TCooper Dec 19 '18 at 2:29
1
$\begingroup$

Start with:

A race with any five horses. Discard the 2nd and 3rd. 6 horses remaining.

Now:

Run a race with any five of the remaining horses. Discard the 2nd and 3rd. 4 horses remaining.

Now the trick:

You have 4 horses remaining. So, you get a horse dummy (or perhaps even a dead horse) that does not move to fill the 5th place.

Then:

Run a race with the 4 remaining horses and the dummy to fill the 5th position. Discard the 2nd and 3rd. 2 horses remaining.

And now:

Get two more dummies.

Finally:

Run a race with the 2 remaining horses and 3 dummies. Discard the 2nd place.

Then the solution has:

4 races. This is the minimum because in each race you discard 2 horses. Since there are 8 horses, you'll need at least 4 races to discard 7 of then.

$\endgroup$
  • 1
    $\begingroup$ I assumed you had to run five of the horses at once, and couldn't use a dummy or something similar. If you can, then this works. $\endgroup$ – Excited Raichu Dec 17 '18 at 12:30
  • $\begingroup$ no i cant use a dummy $\endgroup$ – Srin Chow Dec 17 '18 at 13:38
1
$\begingroup$

EDITED: FOUND A BETTER SOLUTION!

TLDR:

5 races.

Step A:

Separate two group of horses: The M group and the E group. The E (for extreme) group are the fastest, the slowest and the second-slowest horses. The M (for middle) group are the remaining 5 horses.

What can be used to separate them?

M horses might show up as 2nd or 3rd places of some race. E horses never do that.

Step B:

Find out who in the E group is the fastest horse.

How to perform step A?

Take a race which gives you two horses as 2nd and 3rd (part of the M group). Take a second one without those two and you'll get other two horses as 2nd and 3rd (also in the M group). Now you'll need to find the 5th horse in the M group.

How?

Take a third race with the four remaining horses and add up the 2nd one from the first race. The 2nd and 3rd horses also belong to the M group. It is impossible that the 2nd from the first race is not between them. Since there was only one horse known to be in the M group, this will give you the 5th member of the group. The other three horses are the E group (let's arbitrarily call them A, B and C).

How to perform step B?

Race any four members of the M group with the horse A from the E group (fourth race). Call J the 2nd place and K the 3rd.

Then:

Race the same four members of the M group with the horse B from the E group (fifth and last race).

Now what?

If in the fifth race, K ends up in 2nd and J doesn't show up (hence he was 1st in the race), this means that taking out A helped the M horses. This implies that A won the forth race and is the fastest horse.

If in the fifth race, J ends up in 3rd and K doesn't show up (should be 4th), this means that adding up B worsened the situation for the M horses. This implies that B won the fifth race. Hence, B is the fastest horse.

If in the fifth race, the 2nd and 3rd places are also J and K just as the forth race, this means that neither A nor B can be the fastest horse, since swapping them didn't change anything to the M horses. So, in this case, only C can be the fastest horse.

Is it possible to determine the positions of every horse?

Yes, but you would need a few additional races. Basically what you would need is to order the M horses.

However, there is no way to tell the 7th and 8th apart (both in the E group). They are effectivelly indistinguishible. Even if/when you know exactly the order of all the other 6 horses, there is no way to produce a race that give any information about their ordering.

Is that the minimum number of races?

I strongly conjecture that yes. There should be no way to do less than 5 races.

Notice that 4 is a lower bound, because we can get answers only about two horses per race. With 3 races, we can get information of no more than 6 horses, and then there would be at least two undistinguishable horses that could be equally probably be in the 1st place. This means that a 4th race is required.

However, instead of 6, I think that this 3 races actually only gives information of 5 horses, since at least one of them would repeat (but I'm unsure, since this all is based in getting indirect information from the results). This possibly means that a 4th race will give information of only 7 horses and then a fifth race would be required.

$\endgroup$
  • $\begingroup$ Thanks alot helped to understand the concept $\endgroup$ – Srin Chow Dec 17 '18 at 17:52
  • $\begingroup$ @SrinChow If you're satisfied, with this answer, please accept it. Otherwise, tell me what should I improve. $\endgroup$ – Victor Stafusa Dec 17 '18 at 18:32
  • $\begingroup$ pretty much i also came up with another idea ill update it in my answer its also based on pattern of the races $\endgroup$ – Srin Chow Dec 25 '18 at 5:22
0
$\begingroup$

Similarly, this is impossible

because

you would not be able to differentiate between the fastest horse and the slowest horse, as the fastest will always come 1st and not be told to you, and the slowest will always come 5th, and also not be told to you.

$\endgroup$
  • $\begingroup$ Yeah but in this case i know the 2nd and 3rd fastest so the 4th and 5th fastest i cant find but i guess the first is find able.One of the answers in my link states that as well i wanted to know the fastest way to do that. $\endgroup$ – Srin Chow Dec 17 '18 at 11:52
  • $\begingroup$ @SrinChow you can’t find the fastest horse is what I’m trying to say. Not even in infinity steps. $\endgroup$ – Excited Raichu Dec 17 '18 at 11:53
  • 2
    $\begingroup$ I'm not sure this is completely true. Say for example, you have picked the five fastest horses and you are told the information about 2nd and 3rd. Then, if you were to remove the fastest horse and replace them, the horse previously in third would move to 2nd in the next race which tells you you've removed the fastest. $\endgroup$ – hexomino Dec 17 '18 at 13:14
  • 3
    $\begingroup$ This definitely isn't true - I show how to find the last horse in a similar variant in my answer to this question. $\endgroup$ – Deusovi Dec 17 '18 at 13:39
0
$\begingroup$

I would argue that the best case scenario would require

3 races

And the worst case scenario would require

5 races at most as @Victor Stufasa explained

Best case scenario

I found a few cases that would only require 3 races, here is one example:
Given 8 horses: A, B, C, D, E, F, G, H with A being the fastest and H the slowest

Let's say you ran these races:
Race#1 (A, B, C, D, E) => (B, C)
Race#2 (C, D, E, F, G) => (D, E)

Now you know that B/C are faster than D/E because only one horse in Race#1 is faster than B/C, so in Race#2, C must be faster than D/E. This means that A is faster than B/C/D/E/F/G. But we don't know how fast H is (the order could be H, A, B, C, D, E, F, G), so we have to run one more race with H, A, B, and 2 other horses.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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