- #1
daniel_i_l
Gold Member
- 868
- 0
Consider the following riddle:
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.
Now, one way to solve the problem is to play around with different methods until you find one that seems minimalistic. But that way you can't prove that your answer is right. In an effort for a way to prove (or disprove) that the answer i got (7 by the way) was right I had the following idea: Let's call the information that one horse is faster than the other one bit of information. Then, in order to find the 3 fastest you need not only a certain amount of information, but also the right density (by that I mean that you need a lot of information about only 3 horses). Now maybe there's some way to find out the maximum amount of information and density that can be gotten by a given number of races.
Does anyone have any ideas about this? Are there existing theories that I can use?
Thanks.
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.
Now, one way to solve the problem is to play around with different methods until you find one that seems minimalistic. But that way you can't prove that your answer is right. In an effort for a way to prove (or disprove) that the answer i got (7 by the way) was right I had the following idea: Let's call the information that one horse is faster than the other one bit of information. Then, in order to find the 3 fastest you need not only a certain amount of information, but also the right density (by that I mean that you need a lot of information about only 3 horses). Now maybe there's some way to find out the maximum amount of information and density that can be gotten by a given number of races.
Does anyone have any ideas about this? Are there existing theories that I can use?
Thanks.