wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Sprinting event
        
(Message started by: Altamira_64 on May 12th, 2012, 2:45am)
Title: Sprinting event
Post by Altamira_64 on May 12th, 2012, 2:45am
The 400 metre dash sprinting event will be held at a field track with 5 lanes. 25 athletes will be participating in total, of which, obviously, only 5 can be running together at a time. Define the minimum number of dashes required to determine the 3 fastest athlets of all, so that they are awarded the gold, silver and bronze medal. Which athletes will be running in each dash?
We assume that each athlete performs exactly the same in each dash. The results of the event will be determined by the relative classification of the athletes and not by their exact times. We only need to determine the 3 fastest athletes and not to follow the exact procedure which usually is followed at such events. (Obviously we cannot use a stopwatch).
Title: Re: Sprinting event
Post by rmsgrey on May 12th, 2012, 6:00am

on 05/12/12 at 02:45:47, Altamira_64 wrote:
The 400 metre dash sprinting event will be held at a field track with 5 lanes. 25 athletes will be participating in total, of which, obviously, only 5 can be running together at a time. Define the minimum number of dashes required to determine the 3 fastest athlets of all, so that they are awarded the gold, silver and bronze medal. Which athletes will be running in each dash?
We assume that each athlete performs exactly the same in each dash. The results of the event will be determined by the relative classification of the athletes and not by their exact times. We only need to determine the 3 fastest athletes and not to follow the exact procedure which usually is followed at such events. (Obviously we cannot use a stopwatch).


In other words, there are 25 entities, with a hidden total order. Each race tells you the (relative) order of 5 of the entities.

Under those conditions, [hide]7[/hide] races would be sufficient. It's harder to prove necessity - [hide]6[/hide] is obviously necessary ([hide]with only 5 races, either you have at least one entity who has never raced, or you have 5 disjoint sets of 5 runners, and no comparisons between runners in different races.[/hide])

As to the ordering of the races:

[hideb]
5 heats in which each runner races once and once only.
1 final in which the five runners who won the heats race, establishing the overall winner.
1 runoff between the runner who placed third in the final, the runner who placed second in the final, the runner who placed second in their heat to the runner who placed second in the final, and the two runners who placed second and third in the heat that produced the overall winner.

If, after the final, you label the heats A, B, C, D and E, in the order their winners placed in the final (so the overall winner ran in heat A, and so on) and then label the runners in each heat 1, 2, 3, 4, 5 in the order they placed in that heat - so A1 is the overall winner, E5 placed last in the heat whose winner, E1, lost the final, and so on. If you label the runners A1-E5 in this way, then the runoff is between C1, B1, B2, A2 and A3.

First and second place in the runoff will go to the second and third fastest overall - A2 or B1 winning the runoff, and any of the five potentially coming second in the runoff.[/hideb]
Title: Re: Sprinting event
Post by Altamira_64 on May 17th, 2012, 3:30am
WoW! Great solution RmsGrey! You are a genius!


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board