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ę!