Author |
Topic: Finding the Top 3 in a Horse Race (Read 1560 times) |
|
goozer
Newbie
Posts: 1
|
 |
Finding the Top 3 in a Horse Race
« on: Feb 7th, 2005, 1:32pm » |
 Quote  Modify
|
Had an interview question like this, but couldn't get it in the time limit, but still interested in teh answer (i dunno it maybe pretty easy, but just can't get a elegant way of doing it with a few number of races), please help.
You have 25 horses and want to know which are the 3 fastest. Whenever you race horses, the order of finish accurately reflects the relative speeds of the horses but you can only race 5 at a time. What's the minimum number of races required to determine the 3 fastest, and how do
you do it?
|
|
 IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
 
Gender: 
Posts: 767
|
|
Re: Finding the Top 3 in a Horse Race
« Reply #1 on: Feb 7th, 2005, 1:56pm » |
Quote Modify
|
The easy way is to race five races, writing down the times, and sorting the list. I suppose we can only measure their relative speed, making it a few more iterations. I get 12 races, but I do believe there is a more optimal solution...
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Finding the Top 3 in a Horse Race
« Reply #2 on: Feb 7th, 2005, 2:13pm » |
Quote Modify
|
I am sure I have seen this here before.
Anyway, here is the solution: (ctrl-A to view)
::
Race all the horses in 5 races. Then, race the five winners.
Call A1 the winner of the winner's race, B1 the second and C1 the third. Call A2 and A3 the followers of A1 in his first race and B2 the second in B1's first race.
You have (X<Y means "X is faster than Y"):
A1<A2<A3, B1<B2 and A1<B1<C1
All other horses are slower than one of A3, B2 or C1, and these 3 have each at least 2 horses in front. Therefore, the top 3 are among the six horses A1, A2, A3, B1, B2, C1.
You already know who is the fastest. It is A1. To find number 2 and 3, you just need to race the remaining five.::
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print