Witam, mam następujący problem:
Jakie jest prawdopodobieństwo, że łamiąc patyk w dwóch miejscach otrzymamy elementy z których można złożyć trójkąt.
Jedyny sposób w jaki udało mi się rozwiązać zadanie to metodami numerycznymi.
Według moich obliczeń prawdopodobieństwo wynosi około 0.23.
Źródło programu i program do liczenia tego prawdopodobieństwa:
Wydaje mi się, że nie da się go rozwiązać metodami klasycznymi, w grę wchodziłoby ewentualnie prawdopodobieństwo geometryczne. Proszę o pomoc, ewentualnie o jakieś naprowadzenie.
Łamanie Patyka (zadane z rozmowy o pracę w Google)
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
Łamanie Patyka (zadane z rozmowy o pracę w Google)
jesli mamy odcinek \(\displaystyle{ [0,1]}\), to oznaczmy miejsca złamania przez \(\displaystyle{ x,y}\)
no i teraz mamy, ze boki trojkata to: \(\displaystyle{ a=x,b=y-x,c=1-y}\)
Wystarczy teraz sprawdzic, czy jest spełniona nierówność trójkąta, rysując w układzie XY odpowiednie zbiory i licząc pole ich części wspólnej. Typowe zadanie z pr. geometrycznego.
no i teraz mamy, ze boki trojkata to: \(\displaystyle{ a=x,b=y-x,c=1-y}\)
Wystarczy teraz sprawdzic, czy jest spełniona nierówność trójkąta, rysując w układzie XY odpowiednie zbiory i licząc pole ich części wspólnej. Typowe zadanie z pr. geometrycznego.
-
- Użytkownik
- Posty: 1874
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
Łamanie Patyka (zadane z rozmowy o pracę w Google)
Można nieco cwaniej. Patyk zamieniamy w sznurek, sklejamy mu końce tak, żeby powstał okrąg. Pamiętamy miejsce sklejenia. Rozcinamy okrąg w dwóch miejscach otrzymując w sumie trzy punkty: dwa rozcięcia i jeden sklejenia.
Trójkąt da się zmontować wtedy i tylko wtedy, gdy te 3 punkty nie leżą na jednym półokręgu. Prawdopodobieństwo tego zdarzenia z kolei można łatwo wyznaczyć. Te trzy punkty nie leżą na jednym półokręgu, jeśli półokręgi w których biegunach leżą te punkty mają puste przecięcie.
Rozważmy zdarzenie przeciwne, czyli, że mają niepuste przecięcie.
Końce półokręgów wyznaczonych przez nasze 3 punkty dzielą okrąg na 6 części. Zamiast losować punkty, możemy losować najpierw średnice wyznaczonych przez te punkty półokręgów (punkty leżą w ich biegunach) następnie za każdym razem zdecydować się na jeden z dwóch możliwych biegunów. Robimy to 3 razy, więc jest \(\displaystyle{ 2^3=8}\) możliwości. Przecięcie będzie niepuste, jeśli wstrzelimy się w jedną z 6-ciu możliwości na przecięcie, czyli prawdopodobieństwo wynosi 3/4, zatem to pierwotnie do policzenia wynosi 1/4.
Ta nieco cwańsza metoda jest tak naprawdę dużo cwańsza. Pozwala ona na przykład w pamięci wyznaczyć prawdopodobieństwo, że 100 punktów wylosowanych na sferze leży na jednej półsferze. Prawdopodobieństwo geometryczne w tej sytuacji oznaczałoby 99-krotną całkę iterowaną po wielokątach sferycznych.
Trójkąt da się zmontować wtedy i tylko wtedy, gdy te 3 punkty nie leżą na jednym półokręgu. Prawdopodobieństwo tego zdarzenia z kolei można łatwo wyznaczyć. Te trzy punkty nie leżą na jednym półokręgu, jeśli półokręgi w których biegunach leżą te punkty mają puste przecięcie.
Rozważmy zdarzenie przeciwne, czyli, że mają niepuste przecięcie.
Końce półokręgów wyznaczonych przez nasze 3 punkty dzielą okrąg na 6 części. Zamiast losować punkty, możemy losować najpierw średnice wyznaczonych przez te punkty półokręgów (punkty leżą w ich biegunach) następnie za każdym razem zdecydować się na jeden z dwóch możliwych biegunów. Robimy to 3 razy, więc jest \(\displaystyle{ 2^3=8}\) możliwości. Przecięcie będzie niepuste, jeśli wstrzelimy się w jedną z 6-ciu możliwości na przecięcie, czyli prawdopodobieństwo wynosi 3/4, zatem to pierwotnie do policzenia wynosi 1/4.
Ta nieco cwańsza metoda jest tak naprawdę dużo cwańsza. Pozwala ona na przykład w pamięci wyznaczyć prawdopodobieństwo, że 100 punktów wylosowanych na sferze leży na jednej półsferze. Prawdopodobieństwo geometryczne w tej sytuacji oznaczałoby 99-krotną całkę iterowaną po wielokątach sferycznych.
-
- Użytkownik
- Posty: 1874
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
Łamanie Patyka (zadane z rozmowy o pracę w Google)
Przy okazji innych rozważań przyszło mi do głowy inne rozwiązanie.
Niech \(\displaystyle{ a_i}\) \(\displaystyle{ i=1,2,3}\) będą długościami odcinków powstałych po złamaniu patyka, który ma długoć 1.
Pytamy o prawdopodobieństwo, z którym spełnione są poniższe nierówności:
(*) \(\displaystyle{ a_i+a_j \ge a_k}\)
dla parami różnych \(\displaystyle{ i,j,k}\).
Zachodzi jednak
(**) \(\displaystyle{ \sum a_i=1}\)
oraz liczby \(\displaystyle{ a_i}\) są nieujemne, więc po odjęciu (**) od (*) otrzymujemy:
(**) \(\displaystyle{ a_i\le 1/2}\)
dla \(\displaystyle{ i=1,2,3}\) i na odwrót, (***) implikuje (*).
Rozważmy teraz pewien (niezdegenerowany) trójkąt \(\displaystyle{ A_1,A_2,A_3}\) na płaszczyźnie.
Trójka \(\displaystyle{ (a_1,a_2,a_3)}\) wyznacza pewien punkt tego trójkąta we współrzędnych barycentryczych względem jego wierzchołków. Nierówności (***) są spełnione wtedy i tylko wtedy, gdy ten punkt leży we wnętrzu trójkąta o wierzchołkach będących środkami boków wyjściowego trójkąta. Z kolei pole tego trójkąta to 1/4 czwarta pola wyjściowego, więc to jest odpowiedź.
Niech \(\displaystyle{ a_i}\) \(\displaystyle{ i=1,2,3}\) będą długościami odcinków powstałych po złamaniu patyka, który ma długoć 1.
Pytamy o prawdopodobieństwo, z którym spełnione są poniższe nierówności:
(*) \(\displaystyle{ a_i+a_j \ge a_k}\)
dla parami różnych \(\displaystyle{ i,j,k}\).
Zachodzi jednak
(**) \(\displaystyle{ \sum a_i=1}\)
oraz liczby \(\displaystyle{ a_i}\) są nieujemne, więc po odjęciu (**) od (*) otrzymujemy:
(**) \(\displaystyle{ a_i\le 1/2}\)
dla \(\displaystyle{ i=1,2,3}\) i na odwrót, (***) implikuje (*).
Rozważmy teraz pewien (niezdegenerowany) trójkąt \(\displaystyle{ A_1,A_2,A_3}\) na płaszczyźnie.
Trójka \(\displaystyle{ (a_1,a_2,a_3)}\) wyznacza pewien punkt tego trójkąta we współrzędnych barycentryczych względem jego wierzchołków. Nierówności (***) są spełnione wtedy i tylko wtedy, gdy ten punkt leży we wnętrzu trójkąta o wierzchołkach będących środkami boków wyjściowego trójkąta. Z kolei pole tego trójkąta to 1/4 czwarta pola wyjściowego, więc to jest odpowiedź.