horse racing

[David Ash]

This problem is a variant on a problem that has been making the rounds on the Web lately on places like Quora:

One has 25 racehorses and a racetrack. Each horse will always complete the race in exactly the same time. One can race five horses at a time, but the only information one gets is the ranking of the five horses. One wants to determine the top 3 horses out of all 25 horses. There are then three subproblems:

1. Prove that, in general, this can be done in at most seven races (this is the version currently making the rounds).

2. Prove that, in general, seven races are also necessary in that just six races are not sufficient (this subproblem I'm proposing and can solve).

3. Prove that no matter what strategy one uses, the expected number of races to find the top 3 horses must be at least seven. For example, there is no strategy guaranteed to work in seven races but that will also provide a solution in six races some of the time. (This subproblem I'm proposing but haven't solved yet).

[t...@bellefleurbooks.com]

Dear David:

I have not looked on the Web, but the first two proofs are rather
obvious. The apparent horse racing scheme is basically a triple
elimination tournament but with five competing each round instead of
two. By triple elimination I mean being outrun, directly or indirectly,
by three different horses.

The third proof is slightly more complex. Here is a quick overview.
You can make this outline below into a lot of precise cases, if you
want, but it just turns the whole thing into a tedious proof.

In the apparent scheme in the first two proofs, five different horses
win the first five races, without any of them losing to any of the
others, and all 25 horses compete in the first five races. If you race
the five winners in the sixth race, as you do in the apparent scheme in
the first two proofs, you do not know who is second or third, so you
need the seventh race. If you don't race the five winners in the sixth
race, then you need the seventh race, just to find out who is first (and
you won't be able to determine who is second or third in all possible
permutations of the horses).

Suppose five different horses win the first five races without any of
them losing to any of the others, as mentioned, but suppose at least one
horse races at least twice in the first five races, so there is at least
one horse left over that did not race. Now you have at least six
potential winners, and the sixth race will not be enough to determine
the winner. You will have at least seven horses that you have to race
in the seventh race, so the scheme won't work in all permutations.

Suppose at most four different horses win the first four races, without
any of them losing to any of the others, in every possible permutation
of the horses. This means that at most twenty horses race in the first
five races, leaving at least five horses left over. Again, you have at
least six potential winners, and the sixth race will not be enough to
determine the winner. You will have at least nine horses that you have
to race in the seventh race, so the scheme won't work in all
permutations.

The upshot is that you have to race 25 horses the obvious way in the
first five races. This necessitates seven races for the triple
elimination tournament. The sixth race has to be the winners of the
first five. The seventh race has to be the horse that finished third in
the sixth race, the two horses that placed in the race that the horse
that finished second in the sixth race won, and the two horses that
showed, but did not win, in the race that the horse that won the sixth
race earlier won. There is no other way to make this all work out in no
more than seven races.

Sincerely,

Tom

On 2021-09-06 17:58, 'David Ash' via Competition Corner Participant

> --
> You received this message because you are subscribed to the Google
> Groups "Competition Corner Participant Discussion" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to
> competition-corner-partici...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/competition-corner-participant-discussion/6c192d7d-f0da-4c6a-b262-611100c566a3n%40googlegroups.com
> [1].
>
>
> Links:
> ------
> [1]
> https://groups.google.com/d/msgid/competition-corner-participant-discussion/6c192d7d-f0da-4c6a-b262-611100c566a3n%40googlegroups.com?utm_medium=email&utm_source=footer

[David Ash]

Hmmm...it is definitely possible if we are very lucky to do it in six races. For example:

H1,H2,H3,H4,H5

H3,H6,H7,H8,H9

H3,H10,H11,H12,H13

H3,H14,H15,H16,H17

H3,H18,H19,H20,H21

H3,H22,H23,H24,H25

In this case we only have TWO distinct winners of the first five races, but one of them does lose to another (H3 loses to H1 in race #1). Is this scenario covered in your proof in any way?

The difficulty seems to be that if we arrange the first 5 or so races in such a way that we have a chance of getting lucky and finishing in six races (as the above example shows), it seems that the EXPECTED number of overall races would then be greater than 7. But I haven't been able to prove it. I'm not sure if you have a proof yet either though :)

Anyways on this just as on the question of funding I do think we need Gabi and István to put together a bit of a formal structure, although I definitely appreciate their getting the ball rolling by sending out the request for problems.

[t...@bellefleurbooks.com]

Dear David:

Please look carefully at what I said in my earlier e-mail message. What
you suspect is true and have not proved is what I have given you an
outline of how to prove. What you suspect is true is actually true and
provable. Not only are exactly seven races required, as you expect, but
there is only one way to arrange the tournament--with 25 horses in the
first five races, the winners of the first five in the sixth, etc.

Should you carry the horse that came in third in the first race to the
second race, as you do in your example, there is no guarantee that the
horse will win the second race. Another horse may win the second race.
A third horse may win the third race. A fourth horse may win the fourth
race. A fifth horse may win the fifth race. As long as you have at
least 21 horses in the first five races, as you do in the example below,
you have no way to prevent five different horses from winning the first
five races. With 21 horses, you also have four left over. Any of these
nine can be a winner. You do not have enough races left, in this case,
to determine both the winner and the next two horses. (Or, as you put
it, you need more than seven races to do this.)

You ask if the example is the scenario in my outline. No, it is not.
One scenario in the outline is five different winners in the first five
races but fewer than 25 horses competing in them. The other scenario is
arranging the first five races so that they can never ever have five
different winners, but this means not introducing a new horse in at
least one race. If you introduce a new horse in every race, it might
win, so you might have five winners by the end of the fifth race. If
you don't introduce a new horse in one of the first five races, then you
cannot have raced more than twenty horses, so there are at least five
horses left over that have not raced yet by the end of the fifth race.

You mention hoping to get lucky somehow. You won't get lucky at this
horse track. You had better stick to the bars.

Sincerely,

Tom

On 2021-09-11 22:09, 'David Ash' via Competition Corner Participant

> https://groups.google.com/d/msgid/competition-corner-participant-discussion/8e669e8a-1256-4c72-8e0d-915009c60fe7n%40googlegroups.com

> [1].
>
>
> Links:
> ------
> [1]

> https://groups.google.com/d/msgid/competition-corner-participant-discussion/8e669e8a-1256-4c72-8e0d-915009c60fe7n%40googlegroups.com?utm_medium=email&utm_source=footer

[John Sullivan]

I'm not sure I've followed all the details yet, but, Tom, I think you've proved that there's essentially only one strategy that is guaranteed to work with only seven races. But David's last question was about the possible existence of a strategy where the expected number of races needed is less than 7. I took his example as indicating the start of a strategy which has a small chance of needing only 6 races. (That is, let the 3rd horse from the 1st race compete against the remaining horses in the next five races. This works in 6 races if and only if the top 3 horses were all in the first race, which I guess is a 1 in 114 chance.) He didn't tell us what he'd do if things don't work out so nicely, so we can't compute the expected number of races. But surely whatever the detailed strategy is, there is more than a 1 in 114 chance that it won't even work in 7 races. I don't see that you've proved this, however.

Best,

John

[David Ash]

Thanks for the replies John and Tom!

Yes, John has correctly illuminated the question I'm trying to get at w/my third subproblem. I've shown that if we arrange the horses just right for the first 5 or 6 races, there is a small probability (1 in 114 could be about right although I didn't compute it) that we can finish in 6 races. If we do so, however, we also create a much higher probability (so it would seem) of requiring 8 or more races to finish, so the expected number of races is higher than 7.00. That's what it looks like and that is what I'm asking if people can prove (I don't claim to have a proof yet).

It is known and proven that there is a guaranteed strategy to finish in seven races and no guaranteed strategy to finish in six races. The third subproblem deals more with the expected number of races.

[juggling.jim.roche]

Just in case people don't have enough to do... I've thought a bit about strategies when we generalize to H horses in all, with R horses per race, if we want to discover (in ranked order) the top T horses. We can consider both the worst-case number of races needed to guarantee success and the expected number of races. (The answers might be significantly different for some (H, R, T).) I would primarily be interested in good asymptotic estimates for large values of H, with R and T maybe having different growth rates than H.

If R = 2, then we probably have relatively standard sorting problems (especially if T = H), but suppose that H = 1000, R = 10, T = 50, for example. (This is an example where I think that the expected number of races might be quite a bit less than the worst-case number of races for optimal strategies.)

Best regards,

 Jim Roche

[David Ash]

Thanks Jim and great to hear from you again after all these years--you and I were at the MOP in 1980 in Annapolis together!

Just to be clear as to my reasons for being on this discussion board--I'm here to discuss the proposed journal. I'm not here to solve specific math problems unless solving them moves the process of establishing the journal forward.

So thanks Jim for proposing this more general version of the problem! My question would be--are more general, open ended problems like this appropriate for the journal? That is, will the journal feature unsolved problems where we aren't expecting a complete solution but are interested in how much progress the students might be able to make in a limited time period.

Right now--in the early days for this journal--these meta-questions are very important to me. Is the generalized horses problem that Jim proposes something that we might use in the journal even if none of us can solve it completely at the time it appears in the journal? I'm guessing that this is a problem that isn't completely solved--of course if someone provides a complete solution I will be proven wrong :)

[David Ash]

Also to put my original problem into the framework that Jim proposes: for my original problem H=25, R=5, T=3. The first subproblem asks us to prove that the worst case number of races is <= 7. The second subproblem asks us to prove that the worst case number of races is == 7. The third subproblem asks us to prove a value for the expected number of races, which I conjecture but cannot prove is == 7.

Again though--my focus right now isn't really on solving these problems but discussing the journal, although I understand that gathering a set of problems is one component to establishing the journal.

On Saturday, September 18, 2021 at 12:39:13 PM UTC-7 juggling.jim.roche wrote:

[t...@bellefleurbooks.com]

Dear David and John:

The outline of a proof I gave is not rigorous. There are cases it
leaves out.

Just the same, it looks like you can say something more specific than
that you always need seven races, which is what you (David) are trying
to show. You are trying to show that if you can get away with six races
in at least one permutation of the horses, then you need at least eight
races in some other permutation.

What you can say that is more specific is that to be able to complete
the tournament in seven races for every permutation, then you need to
race all 25 horses in the first five races, then race the winners in the
sixth race to determine the tournament winner. Then for the seventh
race you start with the horse that came in second in the sixth race.
You identify the horse that finished second in the earlier race that
this horse won, and you have to race it in the seventh race against the
four horses that showed in the two races that the tournament winner won.
Do anything different from this, and for some permutation of the
horses, seven races won't suffice. This arrangement seems to be the
only way that you can construct the tournament, without needing eight
races for some permutation of the horses. This is a more specific
assertion than what you are saying, David. Once you prove it, however,
it is trivial then to conclude you need at least seven races.

To prove this specific assertion, you can tediously go through cases, as
I suggested in the outline in the earlier message. Here is another
approach. Why not prove that by the end of the fifth race, no matter
what you do, you always run the risk of having at least one permutation
of the horses for which you have at least five horses that could be
tournament winners, and at least ten horses that could finish first or
second in the tournament, and at least fifteen horses that could finish
first, second or third in the tournament? If, at the end of the fifth
race, you have six or more possible winners for some permutation, then
seven races will not suffice, so you have to arrange matters so that
there are no more than five possible tournament winners by the end of
the fifth race. If you do, then you need to race them in the sixth
race, or else seven races won't suffice. Once you race the five winners
in the sixth race, unless you set up the tournament as described, then
seven races won't suffice for some permutation. This outline may be
less tedious than going through cases.

In any event, if this is a question for a competition among students,
the first two proofs you mention, David, are good assignments. This
third one may be asking a lot. Yet, if you can get a proof, you may be
able to break it down into pieces that are each good assignments and
that in the end complete the third proof.

Sincerely,

Tom

> https://groups.google.com/d/msgid/competition-corner-participant-discussion/c1506eff-9b29-41e3-a6ad-9ae64e632b21n%40googlegroups.com

> [1].
>
>
> Links:
> ------
> [1]

> https://groups.google.com/d/msgid/competition-corner-participant-discussion/c1506eff-9b29-41e3-a6ad-9ae64e632b21n%40googlegroups.com?utm_medium=email&utm_source=footer

[David Ash]

This may be an outline of what you are trying to prove--which is similar but not identical to what I am trying to prove. Since solving these problems isn't my primary focus on here, at least for now, I'm not going to invest the time to expand your outline into a full rigorous proof, but maybe someone else will.

Just to clarify though--what I am trying to prove (as the third of my original three subproblems) is still slightly different from what you want to prove. You want to prove that if we run the horses in such a way that six races are sufficient at least some of the time, we will pay the price of also requiring at least eight races some of the time. Proving that would be great progress towards what I want to prove, but I want to prove the slightly stronger result that the expected number of races is always at least seven regardless of strategy. My result (if I could prove it) would imply your result, but the converse doesn't follow automatically.

[t...@bellefleurbooks.com]

Dear David:

"Fifteen" in my last message should have been "eleven."

Sorry, I did not understand that you were equally weighting all the
permutations and looking at the expected number of races you would need
to determine the winner.

If you construct the tournament the straightforward way, by the end of
the sixth race, you know the winner over all, and you have exactly five
other horses to race. It is not obvious that there is anything better
than this. If instead you pull the winner of each race forward to the
next, at the end of six races, you know the winner over all, and on
average you have roughly eight other horses to race, which is an
expectation greater than seven races. If instead you pull the second
place horse of each race forward to the next, at the end of six races,
on average you have roughly four horses to race in the seventh race, but
you could have six, which is an expectation greater than seven races.
If instead you pull the third place horse of each race forward to the
next, then it is even worse. You can try pulling the first horse some
of the time and the second horse some of the time, but nothing seems to
work better.

Usually it is easier to find a counterexample than to prove something.
Finding a tournament where the expected number of races is less than
seven is something of a counterexample. It is not at all obvious that a
counterexample exists. This suggests that you are correct, the
expectation is seven races. I still contend that there is only one way
to construct the tournament and get the expectation down to seven. If
you are correct--and you probably are--there will be a proof, and it
will be tedious.

Sincerely,

Tom

On 2021-09-18 20:10, 'David Ash' via Competition Corner Participant

> https://groups.google.com/d/msgid/competition-corner-participant-discussion/beb1ea4c-c395-45f7-affe-27365791e558n%40googlegroups.com

> [1].
>
>
> Links:
> ------
> [1]

> https://groups.google.com/d/msgid/competition-corner-participant-discussion/beb1ea4c-c395-45f7-affe-27365791e558n%40googlegroups.com?utm_medium=email&utm_source=footer