A quick up date, I am looking at the horse one but I had an idea with this.PeroK said:That's the idea. You can reduce the number by (approx) a factor of 3 each time.
It's then a question of what criteria you use to assess your strategy. The maximum number of measurements can be calculated using powers of three (or the inverse process: log to the base ##3##).
If, instead, we look at the expected (average) number of measurements, then it gets suprisingly tricky. The example I gave above is that for ##18## items, you can do better than measuring ##6## against ##6##. That's because you can find one light item from ##7## statistically faster than one light item from ##6##. To be honest, I didn't spot that until I wrote a Python script to check all the possibilities!
Yup. Is there a horse in the WOW race that could be second fastest? If so, which horses do you already know are slower than it?pinball1970 said:Problem I see is if I brute force it that way, I will end up with a lot of races where horses have already raced each other.
@Ibix solved it in post #2. The observation is that the WOW race ranking eliminates additional horses from the the initial races of the horses that did not win the WOW race. You are left with 5 horses for the final 2 slots in the 7th race.pinball1970 said:I would not know that till I put that horse in with WOW runners up.
Vanadium 50 said:Let's label it a little differently. In the Race of Winners, label the fastest horse A1, the next fastest B1, and so on. Now look at the prelininaries: label the second fastest horse in the race with A in it A2, the third fastest A3, and so on. Label the second fastest horse in the race with B in it B2, the third fastest B3, and so on.
There is nothing magical about this labeling; it's just convenient.
Can A1 be the 2nd fastest? No...it's the fastest. Can E5?
Ibix said:Yup. Is there a horse in the WOW race that could be second fastest? If so, which horses do you already know are slower than it?
Damn it!Vanadium 50 said:OK, you;re almost there. You have five lanes, and how many horses after identifying A1 as the fastest?
Do you mean once I have ran the heats and winners of those to get the fastest?Vanadium 50 said:For extra credit, repeat this many times. Is E5 on average slower than A5? If so, how is it possible that the speed of two other horses in the race can possibly influence the speed of these two horses?
For extra extra credit, is B4 on average faster than A5?
If I understand the question, you can model this by considering the numbers 1-25 put at random into five groups of five. The numbers in each group are then sorted in ascending sequence. We then choose group A as the group with the number 1 in it. A1 is the number 1 and A5 is the highest number in that group. Group B is the group with the next lowest first number. E.g., if the number 2 is not in group A, then group B will be the group with the number 2 in it. Group E is the group with the highest first number.Vanadium 50 said:I mean you run this with 25 million horses. A1 is always fastest, by construction. If you compare the average speed of the million horses that end up in E5 with the million in A5 which is faster?
If one is faster, how is this possible?
i.e. a slower horse.PeroK said:It's clear than the distribution for E5 has a higher mean than the distribution for A5.
Note that the 16th fastest horse, for example, could equally be in any group; but, it's more likely to be the slowest horse in group A than the slowest horse in group E. It might even be the fastest horse in group E.Vanadium 50 said:i.e. a slower horse.
I agree it is true, but why is it clear?
You can't label them A-E at this point, because that labelling is only available after the sixth race. At that point, though A5 can be faster than all of B1-E1, but E5 must be slower than all of them. So the expectation speed of A5 seems likely to be higher than that of E5.Frabjous said:After the first five races, there is equal probability (1/5) that that slowest horse is A5,B5,C5, D5 or E5.
Got it. Thanks.Ibix said:You can't label them A-E at this point, because that labelling is only available after the sixth race. At that point, though A5 can be faster than all of B1-E1, but E5 must be slower than all of them. So the expectation speed of A5 seems likely to be higher than that of E5.
Agreed. My answer is wrong.Vanadium 50 said:I think you have to be verty careful about "equal probability". Certain cases have been sliminated.
For example, E5 cannot be 9 if E4 is 10.
Similarly, B1 is likely to be faster than A2. To be B1 you need to beat 19 horses. To be A2 you only need to beat 3.
One way to look at this is to place the fastest horse in a group at random, then place the slowest horse in a group at random. There is, therefore, a probability of ##\frac 4 {24} = \frac 1 6## that the fastest and slowest horses are in the same group. This is less than the naive ##\frac 1 5##. That means that the probability that A5 is the slowest horse is ##\frac 1 6##.Frabjous said:I’ll be the idiot.
After the first five races, there is equal probability (1/5) that that slowest horse is A5,B5,C5, D5 or E5.
The sixth and seventh race only involve horses with zero probability of being the slowest. Given that we have learned nothing new about the slowest, the probabilities do not change.
What am I doing wrong?
The idea is that the original draw into five groups is uniformly random. We can then calculate various probabilities, such as the probability that the fastest and slowest horses are in the same race etc.Vanadium 50 said:@PeroK I don't follow your reasoning, but we might be saying the same thing.
I know there are four horses faster than A5: A1, A2, A3 and A4.
I know that there are eight horses faster than E5: A1, B1, C1, D1, E1, E2, E3 and E4.
So on average, A5 is faster than E5.
Ready for the extra extra credit?
Running a similation on a computer may be harder than it appears. There are a lot of ways to place 25 horses in 25 slots (liike 25!) so you need to worry about uniformity of sampling.
import random
#
# Choose the number of times to run the simulation
num_sim = 10_000_000
#
# Count the number of times A5 beats E5
a5_win = 0
#
# g_list keeps a tally of relative rank of horses A1-A5, B1-B5 etc.
g_list=[[0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0],[0,0,0,0,0]]
#
for k in range(0, num_sim):
horses = list(range(1,26))
random.shuffle(horses)
#
# Split the random selection into the five groups (first races)
#
g_0 = [horses[0],horses[1],horses[2],horses[3],horses[4]]
g_1 = [horses[5],horses[6],horses[7],horses[8],horses[9]]
g_2 = [horses[10],horses[11],horses[12],horses[13],horses[14]]
g_3 = [horses[15],horses[16],horses[17],horses[18],horses[19]]
g_4 = [horses[20],horses[21],horses[22],horses[23],horses[24]]
#
# sorting each group equates to running the first set of races
#
g_0.sort()
g_1.sort()
g_2.sort()
g_3.sort()
g_4.sort()
#
# sorting the list of lists equates to running the WOW race (by default Python sorts by the first nunber in each list)
g_temp = [g_0,g_1, g_2, g_3, g_4]
#
g_temp.sort()
#
# Check whether A5 is faster than E5)
#
if g_temp[0][4] < g_temp[4][4]:
a5_win += 1
#
# Add the rankings for this race to the overall tally:
for i in range(0, 5):
for j in range(0, 5):
g_list[i][j] += g_temp[i][j]
#
# Calculate the average rank for each horse:
for i in range(0, 5):
for j in range(0, 5):
g_list[i][j] = round(g_list[i][j]/num_sim,2)
#
print("A5 is faster than E5 {:.2f}".format(a5_win/num_sim))
print("Average rank for group A", g_list[0])
print("Average rank for group B", g_list[1])
print("Average rank for group C", g_list[2])
print("Average rank for group D", g_list[3])
print("Average rank for group E", g_list[4])Dunno. I'll have to check with the sheik.Vanadium 50 said:Been playing with a much more subtle problem: identify the median-speed horse.
One reason this is subtle is the condition "fewest races" - is this on average? Or the smallest maximum guranteed to find the answer? Or something else?
Though I no longer play the game of bridge, I frequent a group of bridge players. They are confronted with such situations all the time. The also have the constraint of solving the problem without any aids and doing so in a timely manner. The problem is quite similar as the number of cards in a hand is fixed and a higher rank in one hand means lower ranks in the other hands.PeroK said:If I understand the question, you can model this by considering the numbers 1-25 put at random into five groups of five. The numbers in each group are then sorted in ascending sequence. We then choose group A as the group with the number 1 in it. A1 is the number 1 and A5 is the highest number in that group. Group B is the group with the next lowest first number. E.g., if the number 2 is not in group A, then group B will be the group with the number 2 in it. Group E is the group with the highest first number.
It's clear than the distribution for E5 has a higher mean than the distribution for A5.
This could be simulated using a Python (or C++) script, or possibly calculated - if it wasn't so late in the day.
PS the lower the number, the faster the horse it represents.
Sheik al-Abdullah said, "What may I ask is this "average" of which you are speaking?" When I tried to explain he replied, "I hear your words only as they rattle about in the deep well of time. The horses win or not win by the will of Allah, peace be upon him. So it is written." I elected not to pursue the matter further.Hornbein said:Dunno. I'll have to check with the sheik.