Wyścigi konne

[smiechowiec]

Mamy 25 koni, które zawsze biegają w jednakowym tempie, ale każdy z inną prędkością.
Jaka jest minimalna liczba biegów wystarczająca do wyznaczenia 3 najszybszych koni ?
W każdej gonitwie może wziąć udział najwyżej 5 koni.
Możemy wnioskować jedynie na podstawie wyników gonitwy, nie znamy czasów poszczególnych koni.

[kornel-1]

6 gonitw minimalnie.
12 gonitw uniwersalnie.

Inaczej mówiąc w sprzyjających warunkach 6 gonitw wystarczy aby wyłonić trójkę najszybszych koni. Organizując 12 gonitw zawsze można wyłonić najlepszą trójkę.

Kornel

[smiechowiec]

Znana mi odpowiedź zawiera więcej niż 6 i mniej niż 12 gonitw.
Czy mógłbyś podać szczegóły Twojego rozwiązania?

[kornel-1]

smiechowiec napisał:

> Znana mi odpowiedź zawiera więcej niż 6 i mniej niż 12 gonitw.
> Czy mógłbyś podać szczegóły Twojego rozwiązania?

Zacznę od 12. Prymitywne rozwiązanie zapewniające zawsze wyłonienie najlepszej trójki.
Gonitwa nr 1: 1 2 3 | 4 5
Gonitwa nr 2: 6 7 8 | 9 10
Gonitwa nr 3: 11 12 13 | 14 15
Gonitwa nr 4: 16 17 18 | 19 20
Gonitwa nr 5: 21 22 23 | 24 25

Odrzucamy 10 najsłabszych koni i znów gonitwy:

Gonitwa nr 6: 1 2 3 | 6 7
Gonitwa nr 7: 8 11 12 | 13 16
Gonitwa nr 8: 17 18 21 | 22 23

Odrzucamy 6 najsłabszych koni i znów gonitwy:

Gonitwa nr 9: 1 2 3 | 8 11
Gonitwa nr 10: 12 17 18 | 21

Odrzucamy 3 najsłabsze konie i znów gonitwy:

Gonitwa nr 11: 1 2 3 | 12 17
Gonitwa nr 12: 3 | 18

Odrzucamy 3 najsłabsze konie, zostaje najszybsza trójka

--------------------
Rozwiązanie dla 6 gonitw dotyczy skrajnie korzystnego układu
Gonitwa nr 1: 1 2 3 4 5
Gonitwa nr 2: 5 6 7 8 9
Gonitwa nr 3: 9 10 11 12 13
Gonitwa nr 4: 13 14 15 16 17
Gonitwa nr 5: 17 18 19 20 21
Gonitwa nr 6: 21 22 23 24 25

W kolejnych gonitwach 2-6 żaden z koni nie był szybszy niż 4 i 5. Czyli najszybsza była trójka wybrana (szczęśliwie!) do pierwszej gonitwy.

Zdaję sobie sprawę z tego, że to rozwiązanie może Ci się nie podobać. Ale Twoje sformułowanie "minimalna liczba biegów wystarczająca do wyznaczenia 3 najszybszych koni" tak odczytałem.


Kornel

[smiechowiec]

Masz rację, 6 gonitw wystarczy jeśli zaczniemy od najszybszej piątki.
Rozwiązanie ogólne można jeszcze ulepszyć zmniejszając liczbę gonitw.

[kornel-1]

25 koni A....Z, 5 gonitw, których wylaniamy trojki:
A B C / D E
F G H / I J
K L M / N O
P Q R / S T
U V X / Y Z
10 koni odrzucamy.
Szósta gonitwa z liderów:
A F K P U
A nr 1
F nr 2 lub 3 lub poza podium,
K - nr 3 lub poza, resztę odrzucamy.

Siódma gonitwa z wiceliderów:
B G / L Q V
B - nr 2 lub 3 lub poza
G - nr 3 lub poza
resztę odrzucamy.
Ósma gonitwa trojek:
C / H M R X
C -nr 3 lub poza, resztę odrzucamy.
Dziewiąta gonitwa:
F K /B G C
F - nr 2
K - nr 3
Medale, impreza.
Kornel

[smiechowiec]

Jestem pod wrażeniem Twojego rozwiązania, przemyślałeś to starannie.
Istnieje rozwiązanie z jeszcze mniejszą ilością gonitw.
Kornelu, czy też odnosisz takie wrażenie, że ostatnio niewiele osób zagląda na to forum?
Pozdrawiam

[kornel-1]

smiechowiec napisał:

> Kornelu, czy też odnosisz takie wrażenie, że ostatnio niewiele osób zagląda na
> to forum?

Lokomotywy forum odjechały w nieznane...

Pomyślę o rozwiązaniu z mniejszą liczbą gonitw.

Kornel

[kornel-1]

Jeszcze raz:
5 gonitw:
A B C / D E
F G H / I J
K L M / N O
P Q R / S T
U V X / Y Z
10 koni odrzucamy.
Szósta gonitwa z liderów:
A F K / P U
A nr 1
F nr 2 lub 3 lub poza podium,
K - nr 3 lub poza, resztę odrzucamy.

Ale!
Q (tym bardziej R) jest wolniejszy od P, którego odrzuciliśmy, więc Q i R skreślamy
V (tym bardziej X) jest wolniejszy od U, którego odrzuciliśmy, więc V i X skreślamy
L (tym bardziej M) jest wolniejszy od K, który jest co najwyżej trzeci więc L i M skreślamy
H jest wolniejszy niż G, który jest co najwyżej trzeci, więc H skreślamy
Zostaje:
A B C
F G
K

A - nr 1, już zwyciężył więc urządzamy siódmą gonitwę dla:

B C / F G K i wyłaniamy drugie i trzecie miejsc
B - nr 2
C - nr 3


k

[smiechowiec]

Wielkie brawa !
O to chodziło.

[xeficod859]

nie wiem