Końskie rozważania – odpowiedź, rozwiązanie i przemyślenia dla K>3

https://xpil.eu/QuLvI

Najmniejszą liczbą wyścigów potrzebnych do wyznaczenia zwycięzcy jest siedem.

W ogólnym przypadku, dla N koni per wyścig (N>4) oraz N^2 wszystkich koni, minimalna liczba wyścigów potrzebnych do wyłonienia najszybszej trójki wynosi N+2.

Rozwiązanie:

1. Dzielimy 25 koni na grupy po pięć.

2. Puszczamy je w pięciu gonitwach.

3. Zwycięzców każdej z tych pięciu gonitw puszczamy w szóstej gonitwie.

4. Dołączamy zwycięzców szóstej gonitwy do ich oryginalnych pięciu początkowych grup.

5. Numerujemy te grupy według kolejności wygranych w gonitwie 6 (a więc zwycięski koń jest w grupie #1, przegrany w grupie #5 i tak dalej)

6. Eliminujemy grupy #4 i #5 (ponieważ dla każdego konia z tych grup istnieją co najmniej trzy konie od niego szybsze, a więc nie ma on szans na załapanie się do pierwszej trójki)

7. Analogicznie, z grupy #3 eliminujemy wszystkie konie oprócz zwycięzcy (wszystkie cztery były od niego wolniejsze), z grupy #2 eliminujemy trzy ostatnie konie (ten co dobiegł drugi ciągle ma szansę na załapanie się do pierwszej trójki - być może jest szybszy od zwycięzcy grupy #3), a z grupy #1 dwa ostatnie (zarówno drugi jak i trzeci mogą okazać się szybsze od zwycięzców grup #2 lub #3 - pozostałe dwa, nawet jeżeli są szybsze od zwycięzców z #2 lub #3, nadal przegrywają z top 3 z pierwszej grupy a więc odpadają).

8. Z pozostałych sześciu koni (jeden koń z grupy #3, dwa konie z grupy #2 oraz trzy konie z grupy #1) usuwamy zwycięzcę szóstej gonitwy (wiemy na pewno, że jest on najszybszym koniem ze wszystkich dwudziestu pięciu). Pozostałych pięć koni puszczamy w ostatniej, siódmej gonitwie. Dwa pierwsze konie z tej siódmej gonitwy oraz zwycięzca szóstej są najszybszą trójką.

Trochę luźnych rozważań...

W ogólnym przypadku (dla dowolnego N > 4), zawsze na końcu zostaje N koni do sprawdzenia.

Zadanie zaczyna się porządnie komplikować jeżeli szukamy czterech lub więcej najszybszych koni. Przypuszczam, że nie ma jakiegoś uniwersalnego algorytmu dla dowolnego top-K koni. Może jednak jest - pachnie mi to trochę trójkątem Paskala...

Weźmy K=4 (a więc szukamy najszybszej czwórki). Wówczas, stosując analogiczne rozumowanie, zostajemy na końcu z dziewiątką koni, z których musimy wyłonić trzy najszybsze. Przy N=5 to trzy dodatkowe gonitwy. Przy N=6, 7, lub 8 potrzeba dwóch gonitw. Przy N>=9 - tylko jednej. Hmm...

Dla K=5 zostaje nam 14 koni do wyłonienia zwycięskiej piątki (a tak naprawdę czwórki, bo najszybszego znamy). Przy N=5 to więcej niż połowa wszystkich koni, a więc algorytm może się okazać nieoptymalny. Przy N=6 potrzeba co najmniej czterech gonitw (a może pięciu? nie wiem) żeby wyłonić cztery najszybsze.

W ogólności, dla top-K pozostaje zawsze \(K \frac{1+K}{2}-1\) koni, spośród których trzeba ustalić (K-1) najszybszych. Aha, N powinno być (chyba?) większe od K żeby algorytm miał sens.

Koń by się uśmiał...

https://xpil.eu/QuLvI