Horse racing
The task is well-known (you can google the solution), but, it seems to me, quite interesting.
We have 25 horses, we have to choose the best 3 of them. For this we can arrange several races. In each race no more than 5 horses can participate.
All horses are different (i.e., no two run at the same speed), the speed of the horse does not change from race to race.
Required to minimize the number of races.
UPDATE: We don’t know how to measure time, after the race we only know the order of the horses participating in it.
Formal description: there is a set of 25 elements on which a linear order is given. In one request, we can find out a part of this order on the 5 elements we have chosen. It is required to find 3 minimum elements for the minimum possible number of requests.
We have 25 horses, we have to choose the best 3 of them. For this we can arrange several races. In each race no more than 5 horses can participate.
All horses are different (i.e., no two run at the same speed), the speed of the horse does not change from race to race.
Required to minimize the number of races.
UPDATE: We don’t know how to measure time, after the race we only know the order of the horses participating in it.
Formal description: there is a set of 25 elements on which a linear order is given. In one request, we can find out a part of this order on the 5 elements we have chosen. It is required to find 3 minimum elements for the minimum possible number of requests.
')
Source: https://habr.com/ru/post/126755/
All Articles