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.005Pierwsza 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ę!
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.
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)
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.
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)
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)Na przyszłość: polecam używać tagu <pre> dla lepszego formatowania kodu.
lepsze
formatowanie
kodu
Postaram się zapamiętać, bo niestety przy polu edycyjnym brak podpowiedzi z czego można korzystać.
No niestety, użyłem go wyżej, w ostrych nawiasach (jak w HTML) i został wycięty. W sumie tego się spodziewałem.
Tu więcej https://davidwalsh.name/wordpress-comment-tags
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. 🙂
No i co? Wycięło mi <pre> i </pre> (pre otwierające i zamykające od “alfa” do “pamiętam”)! Dlaczego?
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
Wygląda na to, że wszystko działa jak powinno. Tak wygląda “surowy” komentarz:
https://i.imgur.com/MC6WBf1.png
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.
ok, spróbujmy z nowej przeglądarki
pre poniżej
jakiś
kod
tutaj
i tutaj
też
pre powyżej
Faktycznie, nie zadziałało. Pomyślę jak to poprawić w wolnej chwili.
Sprawdźmy teraz:
def testujemy(): a=1 b=2 for n in range(10): a,b=b,a+b print(a) testujemy()OK, od tej chwili można dodawać kod w komentarzach, używając następującej magii: https://i.imgur.com/yWcgWmU.png
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.
Słuszna uwaga, wrzuciłem na stałe etykietkę pod formularzem komentarza, ze szczegółami. Teraz nikt nie zapomni 🙂
Z ciekawości sprawdzam:
tutaj wstaw swój kod swój wstaw tutajKoniec sprawdzania.
To jeszcze raz dla pewności 🙂
tutaj wstaw swój kod swój wstaw tutajKoniec drugiego sprawdzenia.
Yyy, nie działa? Nóż urwał nać, w dziuplę jeża. Znaczy się muszę jeszcze powalczyć…
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] …
Start
tutaj wstaw swój kodMeta.