Ślamazary na drodze – rozwiązanie zagadki

https://xpil.eu/mri

Postawiona niedawno zagadka o samochodach na nieskończenie bardzo długiej drodze może na pierwszy rzut oka wyglądać dość zawile, ale jak się przyjmie właściwy tok rozumowania, okazuje się względnie prosta.

Wiemy z treści zagadki, że na dzień dobry każde auto ma inną prędkość i położenie. Przeprowadzimy teraz eksperyment myślowy, który uprości nam uzyskanie odpowiedzi bez wpływu na logikę zadania: układamy wszystkie samochody od najwolniejszego do najszybszego i zaczynamy je po kolei ustawiać na drodze, w losowych miejscach. Pamiętajmy, każde kolejne dostawione na drogę auto jest szybsze od wszystkich dotychczas dostawionych.

Pierwsze auto. N=1, X=1.

Drugie auto, N=2. I teraz tak: albo będzie ono z przodu pierwszego i ucieknie (wtedy X=2), albo nie (wtedy pozostaje X =1). Prawdopodobieństwo jest pół na pół, więc dla N=2 mamy \(X=1+\frac{1}{2}=1.5\).

Dokładamy trzecie auto, szybsze od dwóch już jadących. Jeżeli trafi ono na sam przód (szansa: 1/3), liczba grup wzrośnie o 1. Jeżeli nie - liczba grup nie zmieni się. A skoro oczekiwana liczba grup dla N=2 wynosiła \(X=1+\frac{1}{2}\), to oczekiwana liczba grup dla N=3 będzie \(X=1+\frac{1}{2}+\frac{1}{3}\).

Widać już?

Nie widać?

No to dokładamy czwarte auto, szybsze od każdego z trzech już jadących. Jeżeli trafi ono na pierwszą pozycję (szansa: 1/4), "ucieknie" pozostałym. Jeżeli nie - "przyklei się" do którejś z już istniejących grup. A więc dla N=4 mamy \(X=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\).

W ogólności, dla dowolnego N mamy: \(X=\sum_{n=1}^{N} \frac{1}{n}\)

Jeżeli ktoś nie ufa powyższym rozważaniom i woli sprawdzić rzecz doświadczalnie, proszę bardzo. Oto prościutki skrypt w Pythonie symulujący naszą nieskończoną długą drogę i samochody:

from random import random

minLiczbaAut, maxLiczbaAut, liczbaPrób = 2, 20, 100000
wyniki = {x: 0 for x in range(minLiczbaAut, maxLiczbaAut+1)}
wynikiTeoretyczne = {x: sum([1/n for n in range(1, x+1)])
                     for x in range(minLiczbaAut, maxLiczbaAut+1)}

for liczbaAut in range(minLiczbaAut, maxLiczbaAut + 1):
    for próba in range(liczbaPrób):
        droga = [random() for auto in range(liczbaAut)]
        liczbaGrup = 1
        for i in range(liczbaAut-1):
            if(droga[i] > droga[i+1]):
                liczbaGrup += 1
            else:
                droga[i+1] = droga[i]
        wyniki[liczbaAut] += (liczbaGrup/liczbaPrób)

for i in range(minLiczbaAut, maxLiczbaAut+1):
    print(i, round(wyniki[i], 5), round(wynikiTeoretyczne[i], 5),
          round(abs(wyniki[i] - wynikiTeoretyczne[i]), 5))

Gwoli wyjaśnienia co dzieje się w liniach 12-16: w linii 12 zaczynamy przeglądać auta od frontu. W linii 13 sprawdzamy czy aktualnie sprawdzane auto jest szybsze od tego za nim; jeżeli tak - zwiększamy liczbę grup; jeżeli nie, nakazujemy autu za nim zwolnić do tej samej prędkości.

Z kolei dzielenie w linii 17 normalizuje wyniki.

Na wyjściu dostałem:

2 1.49932 1.5 0.00068
3 1.83301 1.83333 0.00032
4 2.08185 2.08333 0.00148
5 2.28672 2.28333 0.00339
6 2.45032 2.45 0.00032
7 2.59162 2.59286 0.00124
8 2.71483 2.71786 0.00303
9 2.82762 2.82897 0.00135
10 2.93145 2.92897 0.00248
11 3.02296 3.01988 0.00308
12 3.10611 3.10321 0.0029
13 3.17859 3.18013 0.00154
14 3.25625 3.25156 0.00469
15 3.31315 3.31823 0.00508
16 3.3755 3.38073 0.00523
17 3.43854 3.43955 0.00101
18 3.49263 3.49511 0.00248
19 3.54707 3.54774 0.00067
20 3.60274 3.59774 0.005

Pierwsza kolumna to liczba aut, druga - średnia liczba grup w stu tysiącach prób, trzecia - teoretyczna liczba aut wyliczona jako suma odwrotności, wreszcie ostatnia, czwarta kolumna to różnica między drugą a trzecią (bez znaku). Widać zgodność do trzech miejsc po przecinku. Zwiększanie liczby prób (trzecia linia kodu) poprawia dokładność wyników, rzecz jasna kosztem czasu symulacji.

Wszystko się zgadza.

A jak Wam poszło?

Na dzień dobry nie za ciekawie.

1Najpierw odezwał się Cichy, który nie zrozumiał zagadki i udzielił odpowiedzi - w dodatku nieprawidłowej - na nieco inne (choć spokrewnione) pytanie, czyli ile wynosi oczekiwana liczba aut w pojedynczej grupie.

2Potem o zagadkę potknął się Rozie, któremu wyszło (i to nawet z symulacją w Pythonie), że średnio będzie zawsze (N+1)/2:

3Dwa dni później odezwał się zbolały po Covidzie Waldek i niestety również poległ:

Waldkowi życzę szybkiego powrotu kondycji.

4SpeX podesłał swoje rozwiązanie nazajutrz - ale najwyraźniej przeoczył komentarz o sferycznej krowie w próżni i zaczął kombinować z teorią powstawania korków. Rzecz jasna nie zaliczam.

5Po kilku dniach Waldkowi przeszła pomroczność pokowidowa i zaatakował zagadkę raz jeszcze, tym razem w sposób charakterystyczny dla Waldka: nie dość, że dotarł do poprawnego wyniku (i to nieco inną trasą niż ja), to jeszcze dołożył swoje trzy grosze żeby było ciekawiej. Gratuluję!

https://xpil.eu/mri

23 komentarze

  1. Zastanawiam się, czy na pewno dobrze liczysz. Rozwinięcie oczekiwanej liczby grup z 2 pojazdów na 3 przez rozważenie przypadku z dołożeniem najszybszego na początek z prawdopodobieństwem 1/3 jest zgrabne, ale czy poprawne? Wydaje mi się, że nie uwzględniasz w ten sposób wpływu większej ilości pojazdów na prawdopodobieństwa powstania jednej grupy.

    Weźmy samochody o prędkości 1, 2, 3. Możemy je ustawić 6 sposobów, otrzymując następującą ilość grup:
    (1, 2, 3) – 3
    (1, 3, 2) – 2
    (2, 1, 3) – 2
    (2, 3, 1) – 2
    (3, 1, 2) – 2
    (3, 2, 1) – 1

    Oczekiwana wartość ilości grup dla 3 aut to zatem:
    1/6*1 + 4/6*2 + 1/6*3 = 12/6 = 2

    Jeśli w powyższym rozumowaniu jest jakiś błąd, uprzejmie proszę o wskazanie, jak krowie na rowie.

    1. Masz błąd dla (2,3,1)

      (1, 2, 3) – 3
      (1, 3, 2) – 2
      (2, 1, 3) – 2
      (2, 3, 1) – 1
      (3, 1, 2) – 2
      (3, 2, 1) – 1

      11/6=1.8(3)

      1. Ahm, dobra, widzę, dzięki. Nie wystarczy par sprawdzać przy liczeniu grup. Co prawda 2 nie dogoniłby 3, ale 3 zostanie spowolniony do 1 po dogonieniu 1.

        1. W ramach samokrytyki, nauki itd. właściwy kod do symulacji:

          import random

          m = 10
          count = 10000

          for n in range(2, m + 1):
          b = list(range(n))
          sum_groups = 0
          group_counts = {}
          for i in range(count):
          a = b.copy()
          random.shuffle(a)
          groups = 1
          for j in range(len(a) – 1, 0, -1):
          if a[j] > a[j – 1]:
          groups += 1
          else:
          a[j – 1] = a[j]
          sum_groups += groups
          result = sum_groups / count
          print(n, result)

          1. import random
            
            m = 10
            count = 10000
            
            for n in range(2, m + 1):
                b = list(range(n))
                sum_groups = 0
                group_counts = {}
                for i in range(count):
                    a = b.copy()
                    random.shuffle(a)
                    groups = 1
                    for j in range(len(a) - 1, 0, -1):
                        if a[j] > a[j - 1]:
                            groups += 1
                        else:
                            a[j - 1] = a[j]
                    sum_groups += groups
                result = sum_groups / count
                print(n, result)
            
            1. lepsze
              formatowanie
              kodu

              Postaram się zapamiętać, bo niestety przy polu edycyjnym brak podpowiedzi z czego można korzystać.

  2. Czy to nie powinno dać się zrobić w jednym komentarzu?

    alfa
    beta
    gamma
    delta
    dalej
    nie
    pamiętam

    Elegancko i profesjo…

    Nie czepiam się, tylko perspektywicznie sprawdzam rzeczywiste właściwości tego pola edycyjnego. 🙂

  3. No i co? Wycięło mi <pre> i </pre> (pre otwierające i zamykające od “alfa” do “pamiętam”)! Dlaczego?

    1. Nie wiem. Spróbujmy:

      poniżej wstawiam pre w trójkątnych nawiasach

      teraz
        trochę
          kodu
        i
      już
      

      powyżej linia z /pre w trójkątnych nawiasach

        1. Dokładnie coś takiego miałem w komentarzu z “lepsze formatowanie kodu” i jak widać wycięło. Prawdopodobnie Tobie nie wycina, bo jesteś właścicielem/zalogowany.

          Więcej o komentarzach w WP w moim komentarzu powyżej.

                  1. Ci, którzy teraz to przeczytali, będą pamiętali, że jest dziwnie. Ale za rok zapomną lub nie odnajdą tej instrukcji (bo jak? – nie dajesz dostępu do archiwum), a i nowi, nie znający problemu, też nie będą wiedzieli jak tutaj wcinać tekst.
                    Myślę sobie, że skoro tobie (czyli właścicielowi) działa pre, to może działać każdemu – mechanizm przecież jest – trzeba go tylko aktywować dla pospólstwa.

                    1. Słuszna uwaga, wrzuciłem na stałe etykietkę pod formularzem komentarza, ze szczegółami. Teraz nikt nie zapomni 🙂

  4. Z ciekawości sprawdzam:

      tutaj
        wstaw  
          swój 
            kod
          swój 
        wstaw  
      tutaj
    

    Koniec sprawdzania.

    To jeszcze raz dla pewności 🙂

      tutaj
        wstaw  
          swój 
            kod
          swój 
        wstaw  
      tutaj
    

    Koniec drugiego sprawdzenia.

    1. OK, potestowałem trochę i widzę, że dla niezalogowanych użytkowników system zamienia pojedyncze cudzysłowy na podwójne, w efekcie zamiast lang="język" dostajemy lang=""język"" i się system sypie. Póki co można po prostu używać [code] … [/code] …

Skomentuj Waldek Anuluj pisanie odpowiedzi

Komentarze mile widziane.

Jeżeli chcesz do komentarza wstawić kod, użyj składni:
[code]
tutaj wstaw swój kod
[/code]

Jeżeli zrobisz literówkę lub zmienisz zdanie, możesz edytować komentarz po jego zatwierdzeniu.