Parkowanie samochodów

[cardemon]

Po długiej przerwie witam serdecznie wszystkich łamigłówkowiczów. Oto
najnowsza zagadka:

Przy krótkiej i wąskiej uliczce mieszkał sobie pewien łamigłówkowicz.
Codziennie skoroświt (jedno słowo, akcent na drugie "o" :)) wychodził on do
pracy, kiedy uliczka była jeszcze całkiem pusta. Wracał natomiast wczesnym
popołudniem, kiedy na uliczce zaparkowane były samochody. Auta zawsze
parkowały tak, że juz żadne więcej nie mogło się tam zmieścic. Na uliczce
wolno było parkować tylko po jednej stronie i tylko równolegle do krawężnika.
Uliczka miała długość 4, a każdy samochód zawsze długość 1 (czyli 4 się na
uliczce nie mieściły). Nasz łamigłówkowicz szybko doszedł do wniosku (wiadomo
jak, prawda?), że kierowcy, którzy przyjeżdżają w ciągu dnia i parkują swoje
wozy na tej uliczce, robią to w sposób zupełnie przypadkowy i nie zważają,
czy parkują dobrze czy źle i czy zostawiają lub nie miejsce dla innych.
Szybko też policzył, jaka powinna być przy takich warunkach przeciętna liczba
parkujących samochodów.
A czy Ty też wiesz jaka to liczba?

Powodzenia,
CdM

PS. Z tym "szybko policzył" to trochę przesadziłem, trochę mu to zajęło. :)

[Gość: pafcio]

wg mnie to około 2,5345...chyba, że się gdzieś pomyliłem:)

[Gość: ref]

Wedlug moich wyliczen (na zyczenie do wgladu) wynika,
ze prawdopobienstwo zaparkowania 3 samochodow jest
wieksze niz zaparkowania 2. Dlatego nie podaje sredniej
liczby samochodow (bo nie da sie zaparkowac 2/16 samochodu)
tylko calkowita - moja odpowiedz 3.
Przyjalem, ze skoro brak jest danych na temat wymaganej potrzebnej
odleglosci pomiedzy samochodami do zaparkowania, to wystarczy
kazda odleglosc ɬ.

ref

[Gość: ref]

Wyliczenia:
Wg. mnie prawdopodobienstwo, ze zaparkuja 3 wynosi 17/32,
a ze zaparkuja 2 - 15/32.
Wiec srdnio zaparkuje (17/32*3) + (15/32*2) = 2,53125 (czy to ma sens?)


ref

[Gość: ref]

Wyliczenia:
Wg. mnie prawdopodobienstwo, ze zaparkuja 3 wynosi 17/32,
a ze zaparkuja 2 - 15/32.
Wiec srdnio zaparkuje (17/32*3) + (15/32*2) = 2,53125 (czy to ma sens?)


ref

[kopperek]

Raczej dokładnie 2,5 - stoją tam zawsze dwa albo trzy
samochody, a prawdopodobieństwo każdego z tych zdarzeń
wynosi 0.5. Chyba że coś koszmarnie pokpiłem:).

pozdrawiam Kopperek

PS Cardemon, a może zajrzałbyś jeszcze na "wojenkę"....:D

[cardemon]

kopperek napisał:

> Raczej dokładnie 2,5 - stoją tam zawsze dwa albo trzy
> samochody, a prawdopodobieństwo każdego z tych zdarzeń
> wynosi 0.5. Chyba że coś koszmarnie pokpiłem:).
>
> pozdrawiam Kopperek
>
> PS Cardemon, a może zajrzałbyś jeszcze na "wojenkę"....:D

Chodzi o średnią z duzej liczby dni, np. jaka będzie ta średnia po 1000-cu
dniach.
Na "wojenkę" właśnie zaglądam...

pzdr. CdM

[kopperek]

cardemon napisał:

> Chodzi o średnią z duzej liczby dni, np. jaka będzie ta
średnia po 1000-cu
> dniach.


Tak to wlasnie rozumiem. Ulica jest codziennie rano
pusta, wiec kolejne wartosci (w kolejnych dniach) sa
niezalezne. Szukany wynik jest takze wartoscia
oczekiwana. Zdumiewajaca zagadka, moje rozumowanie jest
bardzo proste, a jednak wciaz nie moge sie zdecydowac czy
jest poprawne. Chyba mam dolek.

pozdrawiam Kopperek

[Gość: pafcio]

no mnie wyszło, że to wcale nie jest takie proste,a prawdopodobieństwo, że
będą 3 a nie 2 wyszło (5+sqrt2)/12

pozdrufka

[andy._]

Gość portalu: pafcio napisał(a):

> no mnie wyszło, że to wcale nie jest takie proste,a prawdopodobieństwo, że
> będą 3 a nie 2 wyszło (5+sqrt2)/12
Mnie też wyszło, że to nie takie proste, ale oparłem się o całke od 0 do 1 z x/
(2-x), a nie mam pomocy pod ręką. Być może to prowadzi do Twojego wyniku.

Pozdr. A.

[Gość: pafcio]

:) szukałem pola, fakt, ale obyłem się bez całki...

[cardemon]

Bardzo wszystkich proszę, żeby podali raczej końcowe wyniki obliczeń. Wiadomo,
że będzie to liczba gdzieś między 2 a 3, a może nawet między 2.5 a 3. Potem
przedyskutujemy rozwiązania. Póki co sam przeglądam jeszcze swoje obliczenia.

Pozdrowienia dla wszystkich,
CdM

[Gość: pafcio]

poszedłwszy za radą autora zagadki, przejrzałęm swoje notatki, i znalazłem
przynajmniej jeden na razie błąd... prawdopodobieństwo, że będą 3 a nie 2
wynosi (5+sqrt2)/9 a nie przez 12. a stąd oczekiwana liczba to ok 2,71,
pozdrawiam

[cardemon]

Gość portalu: pafcio napisał(a):

> poszedłwszy za radą autora zagadki, przejrzałęm swoje notatki, i znalazłem
> przynajmniej jeden na razie błąd... prawdopodobieństwo, że będą 3 a nie 2
> wynosi (5+sqrt2)/9 a nie przez 12. a stąd oczekiwana liczba to ok 2,71,
> pozdrawiam

Ha!!! Na razie tylko tyle, jeszcze nie zdradzę posiadanych przeze mnie wyników,
a są one aż... dwa. ;)

pzdr. CdM

[Gość: ref]

Tez przejrzalem notatki - porażka.
Tak ze moje wyniki wycofuje.
W wolnej chwili sprobuje policzyc jeszcze raz.

ref

[andy._]

Z mojej całki wyliczyłem w końcu 2.7424 - nie sprawdzałem rachunków więc nie
wykluczam błedu.
Pozdr. A.

Jutro wiecej - Re: Parkowanie samochodów

[cardemon]

Nie chciałbym jeszcze robić ostatecznego podsumowania, więc powiem tylko dwa
slowa: Jestem pod wrażeniem wynikow Pafcia - 2.71 i Andy'ego - 2.7424! One duzo
mi mówią (szczególnie wynik Andy'ego)! Ale póki co, poczekajmy jeszcze na Refa
i może jeszcze kogos. Zasugerowalbym tez nieśmiało podejście do rozwiązania
tego problemu poprzez symulację komputerową. Programik nie powinien zająć
więcej niz 20 linijek (mnie laikowi zajął 22 linijki)...

Serdeczne pozdrowienia, obiecuję więcej jutro,
CdM

Jutro wiecej - Re: Parkowanie samochodów

[marchewa4]

Znalazlem wreszcie troche czasu, zeby sie tym problemem zajac. Wyszlo mi
2,74247.
Moze uda mi sie znalezc czas na mala symulacje ;-)

Pozdrawiam wszystkich
M.

Jutro wiecej - Re: Parkowanie samochodów

[cardemon]

marchewa4 napisał:

> Znalazlem wreszcie troche czasu, zeby sie tym problemem zajac. Wyszlo mi
> 2,74247.
> Moze uda mi sie znalezc czas na mala symulacje ;-)
>

Jak by tu rzec... Człowiek idzie właśnie spać, a tu nagle spada mu jak grom z
nieba liczba 2.74247, a ten człowiek nieszczęsny sam trzyma w schowku liczbę
2.74247042592007...
No i jak tu teraz spać spokojnie... ;)

pzdr. CdM :) :) :)

Jutro wiecej - Re: Parkowanie samochodów

[marchewa4]

cardemon napisał:

> Jak by tu rzec... Człowiek idzie właśnie spać, a tu nagle spada mu jak grom z
> nieba liczba 2.74247, a ten człowiek nieszczęsny sam trzyma w schowku liczbę
> 2.74247042592007...
> No i jak tu teraz spać spokojnie... ;)

Nie wiedzialem, ze o taka dokladnosc tu idzie ;-)))
To moze podam dokladnie co mi wyszlo: ( 11 - 4 ln2 ) / 3

M.

PS. Przy symulacji wychodzi mi srednio ok. 0.05 wiecej.

Jutro wiecej - Re: Parkowanie samochodów

[Gość: ref]

No to i ja podaje wynik - calki nie policze , bo nie mam tablic :(((
A z symulacji wyjszlo mi 2,742470093

ref

Jutro wiecej - Re: Parkowanie samochodów

[andy._]

Gość portalu: ref napisał(a):

> No to i ja podaje wynik - calki nie policze , bo nie mam tablic :(((
> A z symulacji wyjszlo mi 2,742470093
Bardzo ładny wynik symulacji (ile próbek?). Nie jestem jednak przekonany czy
warto symulować, kiedy znany jest wynik analityczny, no chyba żeby się
sprawdzić jako programista.

Pozdr. A.

[musztardek]

Wrócił do domu pierwszy gość. Porzucił swój samochód wzdłuż uliczki i polazł do
domu. Lecę ja tam z linijką i mierzę. Jeśli przed samochodem pozostało miejsca
ponad 1 i za samochodem takoż, to zacieram ręce, zapisuję że zmieszczą się
wszystkie 3 samochody i biorę się za jakieś konstruktywne zajęcie (obieranie
ziemniaków na przykład) zamiast ślęczenie w oknie. Ale jeśli po którejś stronie
zostało mniej miejsca niż 1, to czujnie czekam na kolejnego sąsiada, aż wróci z
pracy.... I oto nadjeżdża! Ładuje się w tę większą lukę w uliczce (bo w małą
nie zmieści się, co nie?) i do domciu tup-tup-tup. A ja hop-przez okno, żeby
mnie nie zauważył i dalej linijką moją pomiary robić. Zostawił za sobą lub
przed sobą więcej 1 miejsca? Brawo! Będzie miejsce dla trzeciego wozu. nie ma 1
ani przed nim, ani za nim? A to drań - nie zmieszczą się trzy, będą stały tu
tylko dwa autka :(

Siedzę tak sobie każdego dnia i patrzę co oni tu robią, i zapisuję liczbę aut
dzień po dniu, i liczę, ile średnio ich tu parkuje.

Powyższe to przekład mojego programu do symulacji parkowania :)) Zajmuje 29
linii, ale dlatego tak dużo, żebyy mi się wyniki ładnie przezetnowały na
ekranie i żebym nie musiał za dużo klikać :)

No więc siedzę tak już od czterech i ćwierci MILIONA dni, i widzę, że tych
samochodów to tam parkuje 2,53762979420019 ! A sąsiad z całką w dłoni (niejaki
Andy X.) mi ciągle grozi i twierdzi że widzi tych samochodów więcej.... No to
jak to w końcu jest, hę?

Wiem, symulacja jest nie za wiele warta wobec dokładnych obliczeń
matematycznych, ale skoro tak, to gdzie popełniam błąd w algorytmie opisanym
powyżej?
Pozdrawiam,
Musztardek

[andy._]

musztardek napisał:

> Wiem, symulacja jest nie za wiele warta wobec dokładnych obliczeń
> matematycznych, ale skoro tak, to gdzie popełniam błąd w algorytmie opisanym
> powyżej?
Algorytm jest piękny i błędu w nim nie widzę. Może jest błąd w programie?

Pozdr. A.

[musztardek]

andy._ napisał:

> Algorytm jest piękny i błędu w nim nie widzę. Może jest błąd w programie?

Nie dość że z całką w ręce czyha na mnie na korytarzu, to jeszcze zagląda w
kody programów które piszę ;) Ale bardzo dobrze !

Owszem, jest błąd! Taki już jestem w gorącej wodzie kąpany, że wystrzelę z
wieściami, zanim je dobrze sprawdzę. Błąd już został poprawiony, program liczy
od nowa, no i już od początku widać że wynik waha się w granicach 2,740-2,745.
A więc na dłuższą metę wyjdzie mi to samo co Wam :)

Pozdrawiam, przepraszam za zamieszanie :), idę zaparkować samochód, póki jest
miejsce ;)
Musztardek

Wyjaśnienia, objaśnienia i odpowiedzi

[cardemon]

Na początek kilka słów przeprosin dla wszystkich łamigłówkowiczów, którzy nie
potrafili poradzić sobie z tą zagadką. Przeprosiny są za perfidię zamieszczenia
tego zadania na tym forum, na którym powinny gościć zagadki niewątpliwie
również i trudne, ale na pewno nie wymagające "ciężkich dział" w postaci
rachunku rózniczkowo-całkowego. Ta zagadka wymaga niestety obliczenia całki i
muszę przyznać, ze jestem pełen uznania, iż przynajmniej dwie osoby, a
mianowicie Andy i Marchewa, doskonale sobie z tym poradziły. Moje gratulacje!
Na swoje usprawiedliwienie mam dwie rzeczy:
Po pierwsze liczyłem na to, że ktoś bez wytaczania "cięzkich dział" poradzi
sobie z rozwiązaniem. Pafcio był/jest bardzo blisko i muszę przyznać, że z
niecierpliwością czekam na jakiś sygnał od niego i przedstawienie swojego
rozwiązania. Nie wiem również, czy Ref uporał się z problemem matematycznie czy
komputerowo, ale jeśli nawet przeprowadził tylko symulacyjne obliczenia, to i
tak jego wynik jest zdumiewająco dokładny. Moje gratulacje za doskonały
algorytm!
Natomiast drugą rzecz jaką mam na swoje usprawiedliwienie, to właśnie ten
nieszczęsny programik komputerowy, bowiem moje obliczenia symulacyjne nie
pokrywały się z obliczeniami analitycznymi. Róznica wynosiła jakieś 0.08. Nie
wiedziałem więc co jest źle, czy mój programik, czy obliczenia. Teraz wiem, że
błąd tkwi gdzieś w tych 20 linijkach programu. Zabawne, że podobna sytuacja
przydarzyła sie też Musztardkowi. Na nieszczęście w przeciwieństwie do
Musztardka nadal nie potrafię znaleźć błędu w swoim programiku. :(
Mam jednak nadzieję, że w końcu dorwę drania, jak będę miał jaśniejszy umysł, a
jeśli nie, to poproszę obecnych tu forumowiczów o pomoc. :)

Tyle wyjaśnień, objaśnień i odpowiedzi na dziś.
Pozdrowienia dla wszystkich,
CdM

[Gość: pafcio]

hej, nie było mnie w sieci, więc nie mogłem od razu reagować. znalazłem 2 błą
(wydaje się ostateczny ) w obliczeniach. niestety wynik znowu nie pasuje (choć
jest blisko) - a mianowicie wychodzi mi 2,7(7) czyli 2 i 7/9.

oto szkic rozwiązania:

po lewej mamy 0 po prawej4:) najbardziej wysunięta w lewo częśc pierwszego
samochodu może znależć się na odcinkach: ɘ,1> (1,2> lub (2,3> z
prawdopodobieństwem 1/3. Jeżeli jest tośrodkowy przedział to stanie 3
samochody;

rozwiązania 1 i 3 przedziału są symetryczne, więc zajmę się tylko 1.

jeżeli ta najbliżej 0 część 1 samochodu ma współrzędną a (0<aə) to aby były 3
samochody lewa część 2 samochodu musi leżeć w następujących przedziałach:
- a+1 lub
tak aby była mniejsza od 2

dziedziną wszystkich możliwości lewych współrzędnych samochodów jest trapez o
wierzchołkach (0,1) (1,2) (3,0) i (3,1) a szukane prawdopodobieństwo to 2/3

i w sumie prawdopodobieństwo że będą 3 wynosi 7/9

nie wiem gdzie tkFi bła więc pomóżcie proszę

pozdrufka

[andy._]

Gość portalu: pafcio napisał(a):

> ... trapez o wierzchołkach (0,1) (1,2) (3,0) i (3,1) ...
Podane wierzchołki to nie trapez tylko czworokąt. Może tu coś tkwi?
Generalnie wydaje mi się, że problem jest nieliniowy aczkolwiek początkowo nie
wykluczałem jakiejś sprytnej liniowej parametryzacji na co chyba też liczył
Cardemon podając tę zagadkę. Ponieważ okazało się, że w wyniku analitycznym
występuje ln 2, to teraz linearyzacja, a nawet jakiej podejście z funkcją
kwadratową nie wydaje mi się możliwe.

Pozdr. A.

[Gość: pafcio]

sorka, oczywiście 0,3 i 1,3

[andy._]

Gość portalu: pafcio napisał(a):

> sorka, oczywiście 0,3 i 1,3

OK, ale teraz nie bardzo rozumiem jak to jest z tą dziedziną i skąd 2/3?

Pozdr. A.

[Gość: pafcio]

x - współrzędna lewej strony 1 samochodu
y - to samo z 2 samochodem

dziedziną nazwałem zbiór wszystkich, tak samo prawdopodobnych, możliwości x i
y, pod warunkiem że x należy od 0 do 1

ten zbiór to właśnie opisany trapez (y się zmienia od 1 do 3, ale z pewnymi
ograniczeniami wynikającymi z faktu, że nie powinien parkować na samochodzie
przed nim)

pole figury równe jest 3/2

a teraz przejdźmy do sukcesu czyli 3 samochodów. opisują go pola 2 trójkątów o
współrzędnych:
1. 0,1 1,2 i 0,2 pokazuje przypadki gdy 2 samochód parkując zostawia za soba
miejsce dla 3
2. 0,2 0,3 i 1,3 pokazuje przypadki gdy 2 samochod parkujac zostawia miejsce
dla 3 przed sobą

stosunek pól sukcesu do możliwości to właśnie 2/3

pozdrawiam

Paradoksy prawdopodobienstwa

[marchewa4]

> x - współrzędna lewej strony 1 samochodu
> y - to samo z 2 samochodem
>
> dziedziną nazwałem zbiór wszystkich, tak samo prawdopodobnych, możliwości x i
> y, pod warunkiem że x należy od 0 do 1
>
> ten zbiór to właśnie opisany trapez (y się zmienia od 1 do 3, ale z pewnymi
> ograniczeniami wynikającymi z faktu, że nie powinien parkować na samochodzie
> przed nim)

Przeprowadzmy maly eksperyment.

Przyjezdza pierwszy kierowca. Wie, ze ma zaparkowac tak, zeby przod stal w
przedziale [0,1]. Niech wybierze sobie losowo miejsce. Potzem przyjezdza drugi
i parkuje, gdzie moze, ale to juz nas mniej interesuje.
Zgodzimy sie chyba, ze prawdopodobienstwo, ze pierwszy kierowca stanie przodem
w przedziale [0, 1/2] wynosi 1/2?

A teraz policzmy to prawdopodobienstwo biorac pod uwage, ze sprzyjajace punkty
to trapez (0,1) (1/2, 3/2) (1/2, 3) (1,3), a wszystkie mozliwosci to trapez
opisany przez Pafcia. Co wychodzi?

Dlaczego? ;-)

M.

[andy._]

Gość portalu: pafcio napisał:

> x - współrzędna lewej strony 1 samochodu
> y - to samo z 2 samochodem
>
> dziedziną nazwałem zbiór wszystkich, tak samo prawdopodobnych, możliwości x i
> y, pod warunkiem że x należy od 0 do 1

Teraz już rozumiem cały wywód i widzę, że jest błedny, ale wyjaśnienie nie
będzie takie proste i krótkie. Chodzi o to, że możliwości x i y nie są "tak
samo prawdopodobne". Jeśli założymy, że wartości x z przedziału 0 - 1 są
równoprawdopodobne, to wtedy wartości y mają różną gęstość dla róznych x: dla
małych x (około zera) y zmienia się od 1 do 3, a dla dużych x (bliskich
jedynki) od 2 do 3.

> pole figury równe jest 3/2
Figura jest OK ale opisuje właśnie gęstość prawdopodobieństwa, a nie
prawdopodobieństwo. Gdyby podzielić ją na kwadraciki 0.01 x 0.01 to dla paska 0
< x < 0.01 prawdopodobieństwo 2 < y < 2.01 jest około 1/200, a dla paska 0.99 <
x < 1 takie pradopodobieństwo jest już tylko około 1/100. To własnie jest
ta "gęstość" (wartości y nie są tak samo pradopodobne dla różnych x).

> a teraz przejdźmy do sukcesu czyli 3 samochodów.
> ... stosunek pól sukcesu do możliwości to właśnie 2/3
Rysunek i rozumowanie są prawidłowe, ale odnoszą się do gęstości
prawdopodobieństwa, a nie do samego prawdopodobieństwa. Żeby przejść na
prawdopodobieństwo trzeba właśnie wykonać całkowanie gęstości i wtedy się
dojdzie do oczekiwanego wyniku. Całkowanie to nic strasznego tylko właśnie
sumowanie tych małych kwadracików 0.01 x 0.01 (im mniejsze tym całkowanie
dokładniejsze, a w granicy dokładne).

Przepraszam za ten przydługi i pewnie niezbyt klarowny wywód, ale może coś z
niego wyniknie:)

Pozdr. A.

[Gość: pafcio]

dzięki, b. klarowne wyjaśnienie...

[Gość: ref]

Witam ponownie,

Przyznam sie bez bicia, co zrobilem.
Napisalem 3 programiki.
Pierwszy do obliczenia prawd. ze wzoru (czyli cos w rodzaju obliczenia całki).
Wynik - 2,742470093.
Drugi - losuje polozenie dwoch samochodow (tylko dla sutuacji, kiedy pierwszy
parkuje z brzegu) - wynik: 2,538202667.
Trzeci - pierwszy samochod "ustawiam" w przedziale 0-1, a drugi samochod
losuje - wynik: 2,537918667.
Wiec mam opisany juz wyzej problem - losujac otrzymuje nizszy wynik niz
całkując.
I za cholercię nie wiem, o co chodzi. Z tego wszystkiego zacząłem przyglądać
sie wynikowi z całką....

ref

[lukkasz]

Dlaczego 4 samochody się nie mieszczą?? Rozumiem, że się mieszczą, tylko
prawdopodobieństwo takiego ich zaparkowania jest zerowe?

[cardemon]

lukkasz napisał:

> Dlaczego 4 samochody się nie mieszczą?? Rozumiem, że się mieszczą, tylko
> prawdopodobieństwo takiego ich zaparkowania jest zerowe?

W zasadzie tak. Moze nawet nie tyle zerowe, co bardzo bliskie (-ɬ). Brawa za
dociekliwość.

CdM

[lukkasz]

Dzięki za nazwanie tego dociekliwością a nie czepianiem się :)
Ale skoro już wnikamy, to prawdopodobieństwo, że zaparkują 4 samochody
parkujące w opisany sposób (czyli przypadkowo) jest dokładnie równe zero. Już
prawdopodobieństwo, że jakiś samochód zaparkuje dokładnie przy brzegu, jest
przecież równe zero (jest to prawdopodobieństwo wybrania konkretnego punktu na
odcinku). Zgadza się?

[cardemon]

lukkasz napisał:

> Dzięki za nazwanie tego dociekliwością a nie czepianiem się :)

W zagadkach na tym forum, a tym bardziej w matematyce nie ma "czepiania się". :)

> Ale skoro już wnikamy, to prawdopodobieństwo, że zaparkują 4 samochody
> parkujące w opisany sposób (czyli przypadkowo) jest dokładnie równe zero. Już
> prawdopodobieństwo, że jakiś samochód zaparkuje dokładnie przy brzegu, jest
> przecież równe zero (jest to prawdopodobieństwo wybrania konkretnego punktu >
> na odcinku). Zgadza się?

Wszystko się jak najbardziej zgadza. :)

pzdr. CdM