Końskie rozważania

horseCiekawa zagadka, której niestety nie udało mi się poprawnie rozwiązać bez używania Google. Może komuś się uda – naprawdę, polecam najpierw spróbować samemu, chociażby dla własnej satysfakcji.

A zagadka brzmi tak:

Jest 25 koni oraz jeden tor, na którym może się ścigać nie więcej niż pięć koni na raz. Jaka jest najmniejsza liczba wyścigów, które pozwolą wyłonić 3 najszybsze konie spośród tych 25?

Dla uproszczenia zakładamy, że 1) konie się nie męczą (a więc prędkość żadnego konia nie zależy od tego ile gonitw już przebiegł), 2) żadne dwa konie nie biegają z identyczną prędkością. Czyli, zapisując bardziej formalnie, dla każdej pary koni x,y zachodzi nierówność V(x) ≠ V(y), gdzie V(k) jest prędkością konia k.

Tak naprawdę powinienem napisać T(x) ≠ T(y) ponieważ prędkość konia jest zmienna, a o zwycięstwie decyduje czas pokonania toru a nie chwilowa prędkość, ale nie komplikujmy niepotrzebnie.

Mi się udało problem zredukować do dziesięciu wyścigów – podpowiem jednak, że to nie jest poprawne rozwiązanie (a więc da się wyłonić trzy najszybsze konie w mniejszej liczbie gonitw).

Aha, dla “spryciarzy”, nie mamy stopera, nie mamy taśmy mierniczej. Jedyne co możemy “mierzyć” to kolejność przybywania koni na metę wyścigu.

Jakieś pomysły?


Zapisz się
Powiadom o
guest
23 komentarzy
Inline Feedbacks
View all comments
butter
butter
2012/04/10 16:34

masz 8 kul, 7 ma jednakową wagę 1 jest lżejsza. Masz wagę szalkową – jak w 2 ważeniach wyznaczyć tą lżejszą?

butter
butter
Reply to  xpil
2012/04/10 23:04

biorę
2^0 kostek z pierwszej [2^0] maszyny oraz
2^1 kostki z 2^1 maszyny oraz
2^2 kostek z 2^2 maszyny oraz
….
2^9 kostek z 2^9 maszyny i ważę wszystko hurtem…

xpil
xpil
Reply to  butter
2012/04/10 23:54

Dokładnie tak (skoryguj tylko numerację maszyn). Najczęstszy błąd przy rozwiązywaniu tego zadania to następujące rozumowanie: "Hmmm, mam dziesięć kostek masła, w tym jedna o 10% cięższa… Jak do cholery wykumać która to jest, za pomocą jednego ważenia? No nie da się…"

butter
butter
Reply to  xpil
2012/04/10 23:27

mogę zejść do 11:
na początek 5 wyścigów po 5 i biorę najszybsze 3 z każdego -> pegazów.
a potem puszczam 5kę i odrzucam 2 najsłabsze [do wyczerpania zapasów]
suma:11
ten sam wynik wychodzi, jak najpierw puszczę 5, odrzucę 2 i będę powtarzał aż do koń-ca konuf.

admin
admin
Reply to  butter
2012/04/10 23:51

Mi się udało zejść do 10 gonitw (jak już nadmieniałem dwakroć), o tak:
1. Puszczamy 5×5
2. Przesuwamy cyklicznie k-tego konia z n-tej grupy do grupy n+k-1 (zapętlając), czyli pierwsze zostawiamy tam gdzie były, drugie przesuwamy do grup n+1, trzecie do n+2 i tak dalej (kolejność koni w każdej grupie ustalamy wg pozycji, na których doszły one do mety)
3. Puszczamy jeszcze raz 5×5
4. Dla każdego konia, sumujemy numery pozycji, na których skończył obydwa wyścigi.

Zawsze jeden koń będzie miał sumę 2 (pierwsza pozycja w obu wyścigach) a dokładnie dwa konie będą miały sumę po 3 (jedno zwycięstwo i jedno drugie miejsce). Tylko że to jest aż dziesięć gonitw, a da się w mniej niż dziesięciu.

Jak już powiedziałem, znalazłem rozwiązanie na Google – i szczerze mówiąc raczej bym na nie nie wpadł samodzielnie, chociaż jest oczywiste.

Dużo trudniejsze jest to samo zadanie, ale ze znalezieniem PIĘCIU najszybszych koni zamiast trzech. I do tej wersji nie znalazłem rozwiązania 🙂

Roman
Roman
Reply to  butter
2019/04/22 14:52

A co jeśli 3 najlepsze konie są w pierwszym biegu…

butter
butter
2012/04/10 16:41

a. 5×5 koni – bierzemy z każdej gonitwy po 3 najszybsze = 15
b. 3×5 koni – bierzemy z każdej gonitwy po 3 najszybsze = 9
c. 2 gonitwy [4i5] z każdej gonitwy po 3 najszybsze = 6
d. 1 gonitwa [5] – bierzemy pierwszą 4kę
e. finałowa gonitwa – zwycięzcy d. + sierotka z c.
Odp: 5+3+2+1+1 = 12

lackI
lackI
2012/04/10 19:59

Mi wyszło 8:
Runda 1: 5×5 daje nam 5 stad posortowanych koni.
Runda 2: 3 wyścigi, w pierwszym biorą udział pierwsze miejsca, w drugim drugie w trzecim trzecie. W ten sposób pierwsze miejsca wyłaniają 3 najszybsze konie z 25.
Nie wiem czy to dobry sposób bo nie googlowałem.

lackI
lackI
Reply to  lackI
2012/04/10 20:30

niestety, kretynie, to nie jest dobry sposób

Maciek
Maciek
2012/04/11 13:46

Mi wyszlo 7:
1. 5×5 na poczatek jak wszyscy juz pisali.
2. 6 wyscig pomiedzy zwyciezcami pieciu poprzednich wylania najszybszego.
3. Do ostatniego bierzemy juz tylko:
– 2 i 3 miejsce z poprzedniego wyscigu (bo wiemy, ze najszybszego juz z zadnym nie trzeba porownywac)
– 2 i 3 miejsce z wyscigu z pierwszej serii, w ktorym wygral ten najszybszy kon (z 6 wyscigu), na wypadek gdyby zdarzylo sie, ze w tym wlasnie wyscigu pobiegly trzy najszybsze konie
– na koniec jeszcze konia, ktory zajal 2 miejsce w biegu, w ktorym w pierwszej serii zwyciezyl kon, ktory w szostym biegu byl drugi, zeby sprawdzic czy bedzie on szybszy od konia, ktory byl trzeci w szostym wyscigu
– pierwsze i drugie miejsce wyloni drugiego i trzeciego najszybszego konia, bo pozostalych nie ma sensu brac pod uwage.

Maciek
Maciek
Reply to  xpil
2012/04/11 17:06

Dziekuje. Nawet nie probowalem guglowac(?) 🙂

Co do pieciu najszybszych koni sposob jest analogiczny, czyli pierwsze 7 wyscigow takie same. Dalej odrzucamy pierwsza trojke, ktora juz wylonilismy, jak rowniez 10 koni, ktore wiemy, ze nie zalapia sie do pierwszej piatki, a mianowicie:
– ostatniego konia z wyscigu, ktory w pierszej serii (5 wyscigow) wygral kon, ktory byl 2-gi w wyscigu nr 6.
– dwa ostatnie konie z wyscigu, ktory w pierwszej serii wygral kon, ktory byl 3-ci w wyscigu nr 6.
– trzy ostatnie konie z wyscigu, ktory w pierwszej serii wygral kon, ktory byl 4-ty w wyscigu nr 6.
– i jeszcze cztery ostatnie konie z wyscigu, ktory w pierwszej serii wygral kon, ktory byl 5-ty w wyscigu nr 6.

Pozostaje nam zatem 12 koni do porownania.

W wyscigu nr 7, kon ktory przybiegl ostatni na pewno nie zalapie sie do pierwszej piatki, bo oprocz najszybszego konia (ktory nie musial brac udzialu w tym wyscigu) byly jeszcze 4 szybsze od niego. Poniewaz kon ten byl w najgorszym wypadku 3-ci w swoim biegu z pierwszej serii, to istnieja co najmniej dwa konie (wsrod tych 12, ktore zostaly nam do porownania), ktore sa od niego wolniejsze i mozemy je odrzucic razem z nim.

Zostaje wiec 9 koni do sprawdzenia, a na to wystarcza 2 kolejne wyscigi (nr 8 i 9). W osmym wyscigu pobiegnie kon, ktory bedzie bronil 4 miejsca zajetego w siodmym wyscigu, a przeciwko niemu stana cztery konie, z ktorych zaden jeszcze z nim nie rywalizowal, ani ze soba. Takze kazdy z tych pieciu koni biegl w roznych z pieciu biegow pierwszej serii i sa oni jedynymi kandydatami na miejsce 4, bo kazdy inny kon, ktory biegl z nimi w biegu a zostal do spawdzenia, jest od nich wolniejszy. Kon, ktory wygra osmy bieg jest czwartym najszybszym. Natomiast kon, ktory zajmie drugie miejsce w tym biegu, bedzie bronil miejsca nr 5 przeciwko czterem pozostalym z 9 koni, w biegu nr 9.

Mam nadzieje, ze jakos w miare da sie zrozumiec to wytlumaczenie. 🙂

Maciek
Maciek
Reply to  xpil
2012/04/11 17:37

Ja wlasnie posilkowalem sie troche Excelem przy szukaniu rozwiazania. 🙂
Cos w tym jest, bo ostatnio Google poprosilo o moje cv, ale nie dlatego, ze rozwiazalem ta zagadke. Jesli szukasz bardziej zlozonych lamiglowek, zwiazanych ze sztuczna inteligencja, to moze zainteresuje Cie stronka aichallenge.org.

Gargi
Gargi
2012/04/11 14:30

25 koni czyli:
5 wyścigów po 5 koni, wyłaniamy po jednym zwycięzcy każdego wyścigu, który przechodzi do kolejnego etapu. Mamy zatem 5 zwycięzców którzy biegną razem w szóstym już wyścigu. Pierwsze 3 konie, które dobiegną na metę są najszybszymi ze wszystkich 25 koni.
Zatem wystarczy 6 wyścigów.

Gargi
Gargi
2012/04/11 14:41

Etap 1: Mamy 25 koni czyli 5 wyścigów po 5 koni każdy. Wyłaniamy 5 zwycięzców – po jednym z każdego wyścigu.
Etap 2: 5 zwycięzców z 1go etapu bierze udział w 6tym wyścigu. Pierwsze 3 konie, które dobiegną na metę, są najszybszymi końmi ze wszystkich 25.

Zatem wystarczy 6 wyścigów.Chyba najprostszy sposób, bez wzorów, liczenia i zbędnego kombinowania.

O ile oczywiście jest on prawidłowy…

admin
admin
Reply to  Gargi
2012/04/11 14:46

Prawda. Z tym, że gówno prawda 🙂 A co jeżeli dwa najszybsze konie będą się ścigać ze sobą w pierwszym wyścigu? Automatycznie eliminujesz niewłaściwego konia z dalszych rozważań.

Gargi
Gargi
Reply to  admin
2012/04/11 15:51

Muszę przyznać, że zabiłeś mi ćwieka tą zagadką ale chyba w końcu ją rozwiązałem 😉 pod warunkiem, że prawidłowa liczba wyścigów to 9 😛
I prosiłbym o informację chociaż na maila czy mam rację, bo będzie dużo pisania, a nie chcę się rozpisywać bez potrzeby 😉

siwy
siwy
2013/06/18 12:25

Gościu …. to że jesteś niekumaty to nie znaczy że możesz wprowadzać innych w błąd przeczytaj admina 3 posty wyżej ….

23
0
Would love your thoughts, please comment.x
()
x