Math Puzzles (Read the Rules!)

[chiggins]

With only your wits, and a racetrack that can run heats of four horses maximum at once, figure out the four fastest horses.

Question: are we figuring out which four horses are the fastest, and the order of those four, or are we simply finding which four are the fastest without regard to how those four finish?

[ChUcK]

The four fastest, as well as how they rank. Bukowski needs this info more than he needs his next Red Stripe.

VeganRay, you are incorrect. Charles has already hired a bum.

[Timko]

I'll bet you $100 that if you give me $200, I will give you $300 in return.

Would you bet with me? Why?

Ray, read the rules. You can't post another problem until your answer has been confirmed by the asker.

[veganray]

Sorry, missed that.

After deeper perusal, I have a better solution for 16 horses (A thru P).
• Have 4 random heats. Assume the finishing order for the heats is as follows:
1) A B C D
2) E F G H
3) I J K L
4) M N O P
• Have a fifth heat featuring the winners of the 1st four. Assume finishing order:
5) A E I M
• We now know A is fastest & that either B or E is second-fastest. Have a match race B vs. E. (Heat #6)
• If B wins, the candidates for third-fastest are C & E.
• If E wins, the candidates for third-fastest are B, F, & I.
• Either way, have a race between the possible contenders to decide third-fastest. (Heat #7)
• If B wins, candidates for fourth-fastest are C & E.
• If C wins, candidates for fourth-fastest are D & E.
• If E wins, candidates for fourth-fastest are B, F, & I.
• If I wins, candidates for fourth-fastest are J & M.
• Either way, have a race between the possible contenders to decide fourth-fastest. (Heat #8)

8 heats

I've been trying to formulate a general solution for any values of numbers of horses, max. number of horses per heat, and number (y-fastest) you are trying to determine. Keep running into divide by zero issues. Does anyone know a general solution?

[Parks]

Sorry, missed that.

After deeper perusal, I have a better solution for 16 horses (A thru P).
• Have 4 random heats. Assume the finishing order for the heats is as follows:
1) A B C D
2) E F G H
3) I J K L
4) M N O P
• Have a fifth heat featuring the winners of the 1st four. Assume finishing order:
5) A E I M
• We now know A is fastest & that either B or E is second-fastest. Have a match race B vs. E. (Heat #6)
• If B wins, the candidates for third-fastest are C & E.
• If E wins, the candidates for third-fastest are B, F, & I.
• Either way, have a race between the possible contenders to decide third-fastest. (Heat #7)
• If B wins, candidates for fourth-fastest are C & E.
• If C wins, candidates for fourth-fastest are D & E.
• If E wins, candidates for fourth-fastest are B, F, & I.
• If I wins, candidates for fourth-fastest are J & M.
• Either way, have a race between the possible contenders to decide fourth-fastest. (Heat #8)

8 heats

I've been trying to formulate a general solution for any values of numbers of horses, max. number of horses per heat, and number (y-fastest) you are trying to determine. Keep running into divide by zero issues. Does anyone know a general solution?

Why are you only racing two horses in a heat?

[Parks]

I'll bet you $100 that if you give me $200, I will give you $300 in return.

Would you bet with me? Why?

Of course not, because if you win the bet I break even, and if you lose the bet you get $100 :D

I'm not posting another problem because this was a rogue submission.

[veganray]

Why are you only racing two horses in a heat?

I didn't see a prohibition of races containing <4 horses in the problem, and 2 (or 3) is enough to solve the problem using my "tree" algorithm.

[chiggins]

• We now know A is fastest & that either B or E is second-fastest. Have a match race B vs. E. (Heat #6)

I'm not sure that's right, for example:

Code: Select all

16 15 14 13
 9 10 11 12
 8  7  6  5
 4  3  2  1


becomes:

Code: Select all

13 14 15 16
 9 10 11 12
 5  6  7  8
 1  2  3  4


becomes:

Code: Select all

 1 14 15 16
 5 10 11 12
 9  6  7  8
13 2  3  4


So after your first five heats, you cannot say that B or E are the second fastest, right?

[veganray]

After heat #1, we know A is faster than B, C, & D
After heat #5, we know that A is faster than E, I, & M
E is faster than everybody else in heat #2 (he won)
I is faster than everybody else in heat #3 (he won)
M is faster than everybody else in heat #4 (he won)
From the results of heat #5, we know that E is faster than I or M
Therefore we know that E is faster than everybody in heats 2, 3, & 4
From the results of heat #1, we know that B is faster than C or D
Therefore, A is fastest, & either B or E must be second-fastest

BTW - if the results of heat #5 were different, we would just rename the first four heats such that heat #5's winner's heat is deemed "heat #1", heat #5's runner-up's heat is deemed "heat #2", heat #5's 3rd place horse's heat is deemed "heat #3", and heat #5's loser's heat is deemed "heat #4".

[chiggins]

(To be clear, my matrices are just one possible result, working backwards from knowing the 1st to 16th fastest horse.)

After heat #1, we know A is faster than B, C, & D

That's reflected as the 13th fastest horse beating 14, 15, and 16th fastest. Okay.

E is faster than everybody else in heat #2 (he won)

That's reflected as the 9th fastest horse beating 10, 11, and 12th fastest. Okay.

I is faster than everybody else in heat #3 (he won)

That's reflected as the 5th fastest horse beating 6, 7, and 8th fastest. Okay.

M is faster than everybody else in heat #4 (he won)

That's reflected as the 1st fastest horse beating 2, 3, and 4th fastest. Okay.

After heat #5, we know that A is faster than E, I, & M

I moved this down into chronological position, and it's reflected as a race between the 1st, 5th, 9th, and 13th fastest horses, with the first horse coming in 1st.

From the results of heat #5, we know that E is faster than I or M

As far as I can tell, this only means that the 5th fastest horse is faster than the 9th or 13th fastest horse.

Therefore we know that E is faster than everybody in heats 2, 3, & 4

That's the trouble spot, it may be that I'm dim and not seeing it, but looking at my example all I can say for sure is that you can be %100 sure that the fastest horse on the track won heat #5. The second, third, and fourth horses were beaten in heat #4 by the fastest horse, but I don't see how they've been accounted for in heat #5?

BTW - if the results of heat #5 were different, we would just rename the first four heats such that heat #5's winner's heat is deemed "heat #1", heat #5's runner-up's heat is deemed "heat #2", heat #5's 3rd place horse's heat is deemed "heat #3", and heat #5's loser's heat is deemed "heat #4".

Heh. I do not understand "we would just rename the first four heats such that heat #5's winner's heat is deemed "heat #1"", apologies for my obtuseness.

[ChUcK]

Veganray's solution is correct. He presented it in a way I have never seen before, but the logic works.

edit: Here's my solution, which is the same as veganray's but it keeps four horses in each heat:

race 4 heats of all different horses. here are theoretical results (in order of placing)
heat 1: ABCD
heat 2: EFGH
heat 3: IJKL
heat 4: MNOP

Then race the winners from each heat with the theoretical results
heat 5: AEIM

That makes A the fastest and it eliminates horses H,L,P

heat 6: BEIM and the winner is the second fastest (assume B wins) and this eliminates horses G,K,O.

heat 7: EIM and the winner is the 3rd fastest (assume C wins) and this eliminates horses F,J,N

heat 8: DEIM and the winner is the 4th fastest. Assume D wins, which gives A>B>C>D>all other horses.

8 races is the minimum.

My solution makes some horses run unnecessarily. Certainly heat 6 only needs to be between B and E, as they are the only possible candidates for 2nd fastest.

[Parks]

Well, Bukoswki might've just hired the bum instead of you, because using a different method it only requires a 7th heat a fair percentage of the time :D

Unrelated side note: keep in mind that HKLNOP were all eliminated after the 5th heat as well, not just HLP.

[chiggins]

BTW - if the results of heat #5 were different, we would just rename the first four heats such that heat #5's winner's heat is deemed "heat #1", heat #5's runner-up's heat is deemed "heat #2", heat #5's 3rd place horse's heat is deemed "heat #3", and heat #5's loser's heat is deemed "heat #4".

Now I got it. I was working columns without bringing the other finishers with them. Once I turned them into chains with greater-thans between the horses, and moved the whole chain up or down the stack, it made perfect sense. (Was like a hand came down and POW I got illuminated.) Helluva puzzle and nice work, doctor.

[ChUcK]

Unrelated side note: keep in mind that HKLNOP were all eliminated after the 5th heat as well, not just HLP.

Whoops, I think you're right. I think that after the 5th race HKLNOP are all at least 4 "greater than"s from A, therefore eliminated from competition.

[veganray]

Does that mean I'm supposed to post the next brainteaser?