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?

23 komentarze

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

    1. 1. Dzielę kule na grupy 3, 3, 2
      2. Porównuję grupy 3, 3 (ważenie numer 1)
      3a. Jeżeli są równe, ważę dwie pozostałe kule (lżejsza opadnie) – koniec.
      3b. Jeżeli są nierówne, eliminuję 5 kul (3 ważone – cięższe, i dwie nieważone)
      4. Porównuję dowolne dwie spośród trzech pozostałych kul (ważenie numer 2)
      5a. Jeżeli są równe, lżejsza jest kula trzecia (nieważona w ważeniu 2) – koniec
      5b. Jeżeli są nierówne, lżejsza pójdzie na dół – koniec.

      Dla dziewięciu kul też się da w dwóch ważeniach. Generalnie do wykrycia lżejszej kuli w zbiorze 3^n – elementowym wystarczy n ważeń.

      Kontrzadanie:
      Mamy dziesięć maszyn, każda z nich produkuje ćwierćkilogramowe kostki masła. Jedna z maszyn jest zepsuta i produkuje kostki masła o 10% za ciężkie. Jak za pomocą jednego ważenia ustalić, która maszyna jest zepsuta? Mamy do dyspozycji tradycyjną wagę, która podaje masę ważonego przedmiotu w gramach.

      1. 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…

        1. 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ę…"

      2. 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.

        1. 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 🙂

  2. 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

    1. Nie. Napisałem przecież, że udało mi się znaleźć rozwiązanie w dziesięciu gonitwach, i że jest ono nieprawidłowe (można w mniej niż dziesięciu).

  3. 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.

  4. 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.

    1. Poprawna odpowiedź. Gratuluję pomysłowości – albo umiejętności guglania 🙂

      A co w przypadku pięciu najszybszych? Kombinowałem trochę, ale bezskutecznie.

      1. 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. 🙂

        1. Da się, tylko musiałem to sobie "rozrysować" w Excelu.

          Całkiem fajny wywód – możesz śmiało startować na stanowisko analityka danych w Google, bowiem takie właśnie pytanie dostał jeden z kandydatów w trakcie rozmowy kwalifikacyjnej 😉

          1. 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.

  5. 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.

  6. 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…

    1. 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ń.

      1. 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 😉

        1. Mi się udało zejść do 10 wyścigów – 9 to lepszy wynik, ale można jeszcze lepiej. Tak więc kombinuj dalej. Inna sprawa, że poprawne rozwiązanie podano tu już dwukrotnie: jedno podał dwie godziny temu Maciek, a drugie ja w osobnym wpisie. Ale nie poddawaj się 🙂

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

Skomentuj butter Anuluj pisanie odpowiedzi

Twój adres e-mail nie zostanie opublikowany.