Minimum hány versenyt kell szervezni ahhoz, hogy megtudjuk melyik a 3 leggyorsabb ló? (Bővebben lent)

Ötösével futtatjuk a lovakat, és mindegyik verseny első három helyezettje bekerül a következő fordulóba. Tehát 5 verseny lement, és maradt 15 ló.

A következő fordulóban összesorsoljuk az öt első, az öt második és az öt harmadik helyen befutott lovat, és őket versenyeztetjük. Itt is az első három helyezett jut tovább, így 8 verseny után 9 ló marad.

Mindegyik lóról tudjuk, hogy melyik versenyen hányadik lett; eszerint kiválasztjuk az 5 legjobb lovat, és őket futtatjuk, és itt is az utolsó kettő kiesik. Az ez utáni versenyben az előbbiben nyert ló szintén elindul a másik 4 lóval, és ott is kettő kiesik. Így 10 verseny után maradt 5 ló, közülük mindenképp kiderülnek a leggyorsabb lovak.

Tehát eszerint 11 versenyt kell rendezni. Ennél jobbat nem találtam, és szerintem nincs is.

A lényeg az, hogy minden verseny végén 2 ló fog kiesni; ha 3 ló esne ki, tehát csak az első kettő jutna tovább, akkor megeshetne, hogy az egyébként harmadik leggyorsabb ló is kiesne (ez akkor fordulhatna elő, hogyha valamelyik versenyben a ténylegesen 1-2-3 helyezett lovak futnának, és ennek mindig megvan az esélye), így máshogyan nem is lehet számolni.

Először is biztos vagyok benne, hogy a feladat angolul, de talán még magyarul is fenn van a neten.

Érdemes keresgélni.

Én most nem kerestem, inkább próbáltam magam megoldani.

"Tehát eszerint 11 versenyt kell rendezni. Ennél jobbat nem találtam, és szerintem nincs is. "

Itt egy 7 futamos megoldás:

Csinálunk először 5 futamot, úgy, hogy minden ló pontosan egy futamban induljon.

Ekkor kialakul egy ilyen sorrend:

a1-a2-a3-a4-a5

b1-b2-b3-b4-b5

stb.

Most versenyeztessük az 5. győztest, ez a 6. futam.

Tegyük fel, hogy a1>b1>c1 sorrend alakult ki.

Ez azt jelenti, hogy

d1-et és e1-et megelőzte 3 ló kapásból, a d2, e2 stb. lovakat megelőzte az a1,b1,c1 és a d1 vagy e1 is.

Tehát ezt a 10 lovat eliminálhatjuk.

Ugyanígy az összes 4. és 5. helyezett kiesett a versenyből.

Ami maradt tehát:

a1,a2,a3

b1,b2,b3

c1,c2,c3

a1 biztos, hoigy a leggyorsabb, mint gyorsabb, mint a2 és gyorsabb, mint b1

b3 illetve c2,c3 biztos, hoigy nem fér be az első 3-ba. Vagyis ami maradt:

a1 - biztosan első

a2,a3,b1,b2,c1 lovak vannak versenyben a 2. és 3. helyért.

Ez pont 5 ló, rendezünk köztük még egy futamot és az első 2 lesz a 2. és 3.

Most kéne bizonyítani, hogy jobb megoldás nincs. De itt még nem tartok :)

7 verseny is elég:

Az első ötben ötösével mind a 25 ló versenyez egyet. Ezután minden futam 4. és 5. helyezettje kizárható.

A 6. körben az első öt futam 5 győztesét versenyeztetjük.

Az itteni győztes a leggyorsabb az összes közül (jelöljük őt A-val).

A 7. körben döntjük el, hogy melyik a 2. és a 3. leggyorsabb. Ha meggondoljuk, erre még pont öt lónak van esélye: annak a kettőnek, akik a 6. körben 2. (ő legyen B) és 3. lett; annak a kettőnek, akik az elején A-val voltak egy futamban és 2. illetve 3. helyen végeztek; valamint aki az elején B mögött volt második. Így ezt az öt lovat a 7. körben versenyeztetve megtudjuk melyik a 2. illetve 3. leggyorsabb.

"d1-et és e1-et megelőzte 3 ló kapásból, a d2, e2 stb. lovakat megelőzte az a1,b1,c1 és a d1 vagy e1 is.

Tehát ezt a 10 lovat eliminálhatjuk."

Ezt nem egészen értem, hogyan jött ki. Kifejted bővebben?

Nem olvastam végig a megoldásokat, de leírom szerintem hogyan kellene:

* Először megversenyeztetném mind a 25 lovat, ez 5 futamot jelent.

* Az előbbi 5 futam győzteseit összeszedném, lesz 5 lovam, amit meg kell versenyeztetnem.

* Megversenyeztetem az 5 győztes lovat és az első három helyezettből ki is derül, hogy melyik a 3 leggyorsabb ló. A 4. és 5. helyezettel nyilván már nem kell törődnöm, azokat elküldhetem melegebb éghajlatra legelni.

Ez összesen 6 futam volt, ha jól számolom.

"Ezt nem egészen értem, hogyan jött ki. Kifejted bővebben?"

Utánam már leírták ugyanezt más szavakkal, de megpróbálom.

Van a 25 lovad, amik 1-től 25-ig sorba rendezhetőek.

5 futam után ilyen rendezésed lesz:

a1>a2>a3>a4>a5

stb.

A reláció azt jelenti, hogy a nagyobb a gyorsabb.

Jön a 6. futam, és kijön, hogy

a1>b1>c1>d1>e1

Vonjuk le a következtetést.

e futamot nézzük meg:

a1>b1>c1>d1>e1>e2>e3>e4>e5

Illetve d futamot:

a1>b1>c1>d1>d2>d3>d4>d5

Tehát e és d futam minden résztvevője kiesett.

c2-c5 szintén nincs már versenyben, mert

a1>b1>c1>c2>c3>c4>c5

Ugyanígy b3-b5 sincs:

a1>b1>b2>b3>b4>b5

6 ló maradt:

a1,a2,a3

b1,b2

c1

a1 nyert két futamot közvetve vagy közvetlenül mindenkivel versenyzett ő a leggyorsabb.

a2,a3 mégcsak 1x futott ők lehet, hogy gyorsabbak b1-nél lehet, hogy lassabbak nem tudjuk még.

b2 szintén versenyben van még, vagy gyorsabb, mint c1 vagy lassabb nem tudjuk.

Tehát mindenképp kell még egy 7. futom a2,a3,b1,b2,c1 lovakkal.