Łamanie Patyka (zadane z rozmowy o pracę w Google)

[lolek09]

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.

[Zordon]

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.

[xiikzodz]

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.

[xiikzodz]

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ź.