The idea is that you have 25 horses, a 5 lane track, no timer, and want to find the fastest 5 horses. How many races can you do it in?
The idea is that you have 25 horses, a 5 lane track, no timer, and want to find the fastest 5 horses. How many races can you do it in?
NOTE THAT THE ORIGINAL PROBLEM WANTED ALL 5 IN ORDER, AND THIS WAY JUST GIVES THE FASTEST 5 POSSIBLY OUT OF ORDER AND NEEDS A 9TH RACE TO ORDER THEM PROPERLY.
I stayed up all night once to come up with an 8, and thought i did, but in the morning realized that I had made a mistake. BruteForce found a description of a solution for 8. It was on the same track as me, but he didn't make the mistake I did. I take no credit.
Anyhow, here's the write-up so it's a little more visual and easier to parse than the text answer he found.
You start by running 6 races. 5 races let every horse run, and the 6th is the winner's race. You're left with:
Note that "1" is clearly the fastest horse, since he was never beaten, and we have some information about every horse relative to at least one other horse. We can also remove some as hopeless, since they're too far back along the known relative speed graph to possibly be in the top 5.
Let's remove those.
Now what? Well, if we want the top 3 in order we'd race 1.2, 1.3, 2, 2.2, and 3. That's 5 horses and the answer to the "top 3 in 7" problem. That's not what we want, though.
We're going to instead race 1.3, 2.2, 3, 3.2, and 4. Why? We know that at least one of 1.2 and 2 are in the top 5, and can figure that out based on the result of our race 7. Here's our race 7.
Let's take the easiest result case first. 3 and 4 are the top 2. 3 had to have beaten 4, since we knew it was already faster. 2 is therefore in the top 4 in second position, and the final horse is one of 1.2, 2.2, 3.2, 4.2, 5. That's 5 horses and we can just race them. Brown indicates horses to be in race 8.
Now let's look at a complicated result. 1.3 and 2.2 are the top 2, in that order. What do we know?
The key piece of information is that since 2.2 beat 3, 3 cannot be in the top 5. Why? For 3 to be in, 2 would have to be in, as well as 2.2. Both beat 3. But that also means, since 1.3 beat 2.2 that 1.2 is in there too. We ran out of places. The same logic rules out 2.3. Depending on the result of race 7, you might have to flip the graph but can then apply the same reasoning as it ends up being symmetrical.
So in this case, which is an example of the most complicated situations from race 7, ends up looking like this:
1.3 and 2.2 run again, and 1.2 doesn't need to run because it has to be in the finals anyhow. The top 3 from this race are in the top 5 with 1 and 1.2.
This was a much better problem than the "top 3" version.
ses-5-race-tracks-How-many-races-you-have-to-run-to-select-top-5-horses-QTN_136645.htm
Read full article from With My Eyes: 25 Horses, 5 lanes, no clock, top 5 (not 3)
The idea is that you have 25 horses, a 5 lane track, no timer, and want to find the fastest 5 horses. How many races can you do it in?
NOTE THAT THE ORIGINAL PROBLEM WANTED ALL 5 IN ORDER, AND THIS WAY JUST GIVES THE FASTEST 5 POSSIBLY OUT OF ORDER AND NEEDS A 9TH RACE TO ORDER THEM PROPERLY.
I stayed up all night once to come up with an 8, and thought i did, but in the morning realized that I had made a mistake. BruteForce found a description of a solution for 8. It was on the same track as me, but he didn't make the mistake I did. I take no credit.
Anyhow, here's the write-up so it's a little more visual and easier to parse than the text answer he found.
You start by running 6 races. 5 races let every horse run, and the 6th is the winner's race. You're left with:
Note that "1" is clearly the fastest horse, since he was never beaten, and we have some information about every horse relative to at least one other horse. We can also remove some as hopeless, since they're too far back along the known relative speed graph to possibly be in the top 5.
Let's remove those.
Now what? Well, if we want the top 3 in order we'd race 1.2, 1.3, 2, 2.2, and 3. That's 5 horses and the answer to the "top 3 in 7" problem. That's not what we want, though.
We're going to instead race 1.3, 2.2, 3, 3.2, and 4. Why? We know that at least one of 1.2 and 2 are in the top 5, and can figure that out based on the result of our race 7. Here's our race 7.
Let's take the easiest result case first. 3 and 4 are the top 2. 3 had to have beaten 4, since we knew it was already faster. 2 is therefore in the top 4 in second position, and the final horse is one of 1.2, 2.2, 3.2, 4.2, 5. That's 5 horses and we can just race them. Brown indicates horses to be in race 8.
Now let's look at a complicated result. 1.3 and 2.2 are the top 2, in that order. What do we know?
The key piece of information is that since 2.2 beat 3, 3 cannot be in the top 5. Why? For 3 to be in, 2 would have to be in, as well as 2.2. Both beat 3. But that also means, since 1.3 beat 2.2 that 1.2 is in there too. We ran out of places. The same logic rules out 2.3. Depending on the result of race 7, you might have to flip the graph but can then apply the same reasoning as it ends up being symmetrical.
So in this case, which is an example of the most complicated situations from race 7, ends up looking like this:
1.3 and 2.2 run again, and 1.2 doesn't need to run because it has to be in the finals anyhow. The top 3 from this race are in the top 5 with 1 and 1.2.
This was a much better problem than the "top 3" version.
ses-5-race-tracks-How-many-races-you-have-to-run-to-select-top-5-horses-QTN_136645.htm
Read full article from With My Eyes: 25 Horses, 5 lanes, no clock, top 5 (not 3)
