7. príklad - Vzorové riešenie

Každý policajt musí bežať aspoň v jednom preteku. Ak by existoval policajt, ktorý nebežal ani v jednom preteku, nemáme žiadnu informáciu o jeho rýchlosti, takže by mohol byť v najlepšej trojici a my by sme o ňom nevedeli.

Máme 25 policajtov, keďže v jednom preteku je najviac 5 súťažiacich policajtov, to znamená, že uskutočníme aspoň 25/5=5 pretekov aby sme odskúšali každého pretekára. Rozdelíme ich ako v nasledovnej tabuľke (prvé číslo znamená na akom mieste sa umiestnil v danom preteku, druhé číslo znamená poradie preteku, napr. 32 znamená policajt sa umiestnil na treťom mieste v druhom preteku):

Keď sa do najlepšej trojky prebojuje policajt z preteku, tak v najlepšej trojke budú tiež tí z jeho preteku, ktorí skončili vyššie (napr. ak sa 31 prebojuje tak automaticky tam musia byť aj 21 a 11), lebo ho porazili v priamom súboji.

Všetci policajti, ktorí sa umiestnili na 4. (4_) a 5. (5_) mieste už nemajú žiadnu šancu byť v najlepšej trojke, lebo ani v ich preteku nie sú. Teraz potrebujeme zistiť, ktorým policajtom budeme merať čas.

Merať časy chceme tak, aby sme merali v každej skupiny tomu istému miestu (napríklad prvému). Ak by sme ich pomiešali, merali napríklad 22, 35, 41, 15, 23, nedozvieme sa vzájomné poradie daného miesta a nevieme systematicky vyradiť policajtov bez šance na umiestnenie v najlepšej trojke. Takže budeme merať časy tým, ktorí skončili v ich preteku na rovnakých miestach (napr. 31, 32, 33, 34, 35).

Keby sme chceli merať čas všetkým tretím, jedine by sme zistili, že najlepší tretí (napr. 31) má šancu nachádzať sa v najlepšej trojke ešte so všetkými druhými (2_) aj prvými (1_). Ostatní tretí (napr. 32) nemôžu byť, lebo by aj prvý (12) a druhý (22) z ich preteku museli byť v najlepšej trojke, čo už je 6 policajtov (31, 21, 11 a z druhého preteku 32, 22, 12, lebo 31 je rýchlejší ako 32). Nemáme žiadne informácie o prvých a druhých policajtoch takže, by sme týchto 10 policajtov museli znovu odmerať. To vieme spraviť na 2 preteky, spolu to je 5+2=7 pretekov.

Keby chceme merať čas všetkým druhým, tak iba ten najrýchlejší (napr. 21) z nich sa môže nachádzať v najlepšej trojke, lebo ak by sa dvaja najlepší z druhých nachádzali tak by sa museli aj tí prví z ich skupiny, čo by urobilo už štvrtého najrýchlejšieho. Takže by mali šancu všetci prví, najlepší druhý (21) a ešte stále aj tretí (31) v skupine toho druhého najlepšieho. Zostane nám 7 policajtov na 3 neznáme miesta:

O žiadnom policajtovi nevieme s určitosťou povedať, na ktorom mieste skončil. Prvý celkovo môže byť hocijaký z prvých v skupine. Druhý, hocikto z prvých alebo aj ten najrýchlejší druhý (21) (pri ňom by musel byť 11 tiež lebo sú spolu v skupine). Tretí môže byť hocikto zo zelených, ak by bol 21 alebo 31 tak aj tí z jeho skupiny vyššie musia byť tiež. Nič to nemení na tom, že do preteku ešte potrebujeme poslať zvyšných 6 (okrem 21) policajtov. To vieme spraviť na 2 preteky, takže zase potrebujeme 5+2=7 pretekov.

Keby meriame čas všetkým prvým tak vieme, že celkovo prvý bude ten najlepší z prvých, lebo porazil z každej skupiny toho najlepšieho. (najlepší z prvých je 11 a postupne najhorší 15)

Tiež vieme povedať, že skupiny s najpomalšími dvomi policajtmi z prvých (14 a 15) sa nemôžu umiestniť, lebo ich najrýchlejší (14 a 15) bol pomalší ako traja najrýchlejší z ostatných skupín.

32 sa tiež nevie umiestniť, lebo môže byť najlepšie štvrtý (11, 12 aj 22 sú určite pred ním). 23 a 33 sa tiež nevedia, lebo by 11, 12 aj 13 sú určite pred nimi.

Ostalo nám 5 policajtov, ktorí majú šancu na umiestnenie, takže urobíme šiesty pretek medzi nimi a prví dvaja sa umiestnia celkovo na druhom a treťom mieste. 

5 pretekov nám nebude stačiť, lebo sme si prešli možnosti, z ktorých sme sa ani pri jednej nedostali k riešeniu pomocou iba 5 pretekov. Pokiaľ by sme si na meranie nevybrali policajtov na rovnakom mieste v ich preteku tak by sme nemali informácie ani o celkovo 1. mieste a nevedeli ich medzi sebou poriadne porovnávať a vyhadzovať tých bez šance na umiestnenie.

Dokopy sme urobili 5 pretekov aby sa zapojili všetci. V nich sme odmerali časy najrýchlejších. Potom sme usporiadali posledný šiesty pretek pre 5 policajtov, ktorí nám ostali so šancou na umiestnenie. 

Na určenie prvých troch pozícií potrebujeme \bold{5+1=6} pretekov.