Вероятен тетраедър

[Sup3rlum]

Продължение на предишната -

Този път имаме отсечка която чупим на 5 случайни места, какъв е шанса от получените парчета да можем да сглобим какъвто и да е тетраедър?

[peyo]

Добре, още няма точен отговор, затова направих симулация да видим колко може да е отговора.
Изследвах 2 начина да получим случайните отсечки.

Метод 1 make_6_random_pieces1 просто взима 6 случайни числа от 0 до 1.

Метод 2 make_6_random_pieces2 е по-сложен. Взима отсечка с дължина 1. Избира 5 случайни места на които да я счупи и получава 6 случайно отсечки със обща сума 1. както ще видим има голяма разлика в резултатите от двата метода.

Код: Избери целия код

from __future__ import division
import random
import itertools

def make_6_random_pieces1():
    return [random.random() for _ in range(6)]

def make_6_random_pieces2():
    sx = [random.random() for _ in range(5)]
    sx.sort()
    sx = sx[0], sx[1] - sx[0], sx[2] - sx[1], sx[3] - sx[2], sx[4] - sx[3], 1 - sx[4]
    return sx
   
def is_triangle( a,b,c ):
    return a+b > c and a+c > b and b+c > a
   
def prob_tetrahedron():
    bust = 0
    N = 1000000
    for i in range(N):
        sx = make_6_random_pieces2()
        for a,b,c,d,e,f in itertools.permutations(sx):
            if is_triangle( a,b,c ) and \
                    is_triangle( a,d,f ) and \
                    is_triangle( b,d,e ) and \
                    is_triangle( c,e,f ):
                break
        else:
            bust += 1
           
    print (1 - (bust /N) )

if __name__ == '__main__':
    prob_tetrahedron()



Резултатите метод 1. Пускам 10 симулации 1М проби всяка. Вероятността средно е 0.3733074:

Код: Избери целия код

   prob      
1   0.373983   -0.0006756   4.56435360000073E-07
2   0.372488   0.0008194   6.71416359999951E-07
3   0.373179   0.0001284   1.64865599999931E-08
4   0.373963   -0.0006556   4.29811360000045E-07
5   0.373454   -0.0001466   2.14915600000153E-08
6   0.373147   0.0001604   2.57281599999838E-08
7   0.372779   0.0005284   2.79206559999984E-07
8   0.373911   -0.0006036   3.64332960000045E-07
9   0.373048   0.0002594   6.7288359999982E-08
10   0.373122   0.0001854   3.43731599999802E-08
avg   0.3733074      2.36657040000005E-06
      stdev   0.000512788715424
      stderr   0.000162158029917
95% confidence         
from   0.372302334117768      
to   0.374312465882232      



Резултатите метод 2, който е по-близо до условието на задачата. Пускам 10 симулации 1М проби всяка. Вероятността средно е 0.0741265:

Код: Избери целия код

   prob      
1   0.074177   -5.05000000000089E-05   2.5502500000009E-09
2   0.073605   0.0005215   2.71962249999994E-07
3   0.074698   -0.0005715   3.26612250000019E-07
4   0.073497   0.0006295   3.96270249999989E-07
5   0.073958   0.0001685   2.8392249999996E-08
6   0.074522   -0.0003955   1.56420250000006E-07
7   0.074143   -1.65000000000165E-05   2.72250000000545E-10
8   0.074179   -5.25000000000109E-05   2.75625000000114E-09
9   0.074293   -0.0001665   2.77222500000046E-08
10   0.074193   -6.6500000000011E-05   4.42225000000146E-09
avg   0.0741265      1.21738050000001E-06
      stdev   0.000367783224196
      stderr   0.000116303267366
95% confidence         
from   0.073405644880576      
to   0.074847355119424      



Направих горните статистики да разбера колко знака е точността и изглежда да е 3 знака след десетичната точка.

Сега някой ако може да пусне и точно решение, че ми е любопитно колко съм близо до отговорите.

[drago]

Пейо, точно решение едва ли ще има. Много тежки са сметките. Симулациите, които си написал, също не са коректни. Като гледам, това което правиш е да избереш $6$ парчета $a,b,c,d,e,f$ за ребра на тетраедъра (няма значение по кой начин). След това проверяваш дали всеки три от тези $6$ величнни са страни на триъгълник. Точно тук е проблема! Представи си, че имаш един тетраедър, в който две срещуположни ребра са много малки, но са отдалечени доста едно от друго. Т.е. другите $4$ ребра са големи. Тогава, тези двете малките и едно от големите не образуват страни на триъгълник, но въпреки това това си е легитимен тетраедър.
Това, което искам да кажа е, че твоите условия са прекалено рестриктивни. Вероятността да се получи тетраедър е по-голяма и при двата метода.

P.S. Ами и това не е ясно, дали са по-рестриктивни. Например ако всеки три от $6$ отсечки образуват тръгълник, това не означава, че тези $6$ отсечки могат да се ребра на тетраедър. Помисли.

[peyo]

... Като гледам, това което правиш е да избереш $6$ парчета $a,b,c,d,e,f$ за ребра на тетраедъра (няма значение по кой начин). След това проверяваш дали всеки три от тези $6$ величнни са страни на триъгълник. Точно тук е проблема! Представи си, че имаш един тетраедър, в който две срещуположни ребра са много малки, но са отдалечени доста едно от друго. Т.е. другите $4$ ребра са големи. Тогава, тези двете малките и едно от големите не образуват страни на триъгълник, но въпреки това това си е легитимен тетраедър.
..

Аха, разбрах какво имаш предвид. Но не, аз не проверявам дали всяка 3-ка от 6-те образуват триъгълник. Аз проверявам дали само 4 конкретни тройки образуват триъгълник:
is_triangle( a,b,c ) and is_triangle( a,d,f ) and is_triangle( b,d,e ) and is_triangle( c,e,f )

Или по-точно от всички пермутации на 6-те проверявам за 4 триъгълника, което мисля, че точно отговаря на условието "от получените парчета да можем да сглобим какъвто и да е тетраедър".

Всички пермутации са 720. Не знам дали тук не може да се оптимизира нещо, но няма значение за крайния резултат.

Мислих си и за още 2 метода на образуване на отсечките:

Метод 3: Чупим пръчката на случайно място. Избираме случайно едно от новите парчета, чупим го на случайно място и повтаряме докато се образуват 6 парчета.

Метод 4: Чупим пръчката на случайно място. Избираме най-голямото парче, чупим го на случайно място и повтаряме докато се образуват 6 парчета.

[drago]

...Но не, аз не проверявам дали всяка 3-ка от 6-те образуват триъгълник. Аз проверявам дали само 4 конкретни тройки образуват триъгълник:
is_triangle( a,b,c ) and is_triangle( a,d,f ) and is_triangle( b,d,e ) and is_triangle( c,e,f )

Ок, съжалявам, не съм разгледал кода внимателно. Цикълът върви по всички пермутации и излизаш от него, при първото мапване на 6-те отсечки към $a,b,c,d,e,f$ , при което и четирите "триъгълника" са наистина триъгълници.
Но, ккто написахпо-горе, условието че всичките тройки $(a,b,c), (a,d,f ),( b,d,e ),( c,e,f )$ са страни на триъгълник не означава, че тези 6 отсечки са страни на тетраедър. Например $a=b=c=d=f=1, e=1.9$.

[peyo]

...
Но, както написах по-горе, условието че всичките тройки $(a,b,c), (a,d,f ),( b,d,e ),( c,e,f )$ са страни на триъгълник не означава, че тези 6 отсечки са страни на тетраедър. Например $a=b=c=d=f=1, e=1.9$.

Не съм сигурен, че разбирам какво имаш предвид. Да видим в конкретния случай:

Код: Избери целия код


def test_tetr_1():
    a=b=c=d=f=1 ; e=1.9
    print (is_triangle( a,b,c ) and \
                    is_triangle( a,d,f ) and \
                    is_triangle( b,d,e ) and \
                    is_triangle( c,e,f ))


Резултата е: True. И мисля, че няма проблем да е тетраедър. Означенията ми са нещо такова:

3-Figure2-1.png (5.08 KiB) Прегледано 764 пъти

[aifC]

[tex]\frac{11}{16}[/tex] ми звучи някак по - правдоподобно.

[Genie_Almo]

Прикачвам малко инфо, което намерих из нета относно критериите за образуване на тетраедър от шест отсечки.

[peyo]

Прикачвам малко инфо, което намерих из нета относно критериите за образуване на тетраедър от шест отсечки.

Сега разбрах за какво говори drago. Трябва да променя проверката с доста по-сложна според EM-2009-064-004-04.pdf.

[drago]

... Трябва да променя проверката с доста по-сложна според EM-2009-064-004-04.pdf.

А има ли смисъл? Интересно ли ти е?

[peyo]

... Трябва да променя проверката с доста по-сложна според EM-2009-064-004-04.pdf.

А има ли смисъл? Интересно ли ти е?

Мисля, че поне за пълнота можем да добавим и тази проверка.

Код: Избери целия код

...
# new import
import numpy as np

#new function
def Cayley_Menger_determinant(x,y,z,x_,y_,z_):
    x2 = x*x; y2=y*y; z2=z*z; x_2 = x_*x_; y_2=y_*y_; z_2=z_*z_;
    A = np.array([
        [0,  x2,  y2,  z2,  1 ],
        [x2, 0,   z_2, y_2, 1 ],
        [y2, z_2, 0,   x_2, 1 ],
        [z2, y_2, x_2, 0,   1 ],
        [1,  1,   1,   1,   0 ]])
    return np.linalg.det(A)

# the check condition in prob_tetrahedron() now is :

            if is_triangle( a,b,c ) and \
                    is_triangle( a,d,f ) and \
                    is_triangle( b,d,e ) and \
                    is_triangle( c,e,f ) and \
                    Cayley_Menger_determinant(a,b,c,d,e,f) > 0 :

...


Резултати с 1М симулации:

Код: Избери целия код

метод    преди        сега        преди/сега
1        0.3733074    0.179031    2.085
2        0.0741265    0.023913    3.099


По някаква причина вероятостта е паднала 2 и 3 пъти. Струва ми се повече отколкото предполагах, защото мислех, че пропускам само някакви гранични редки случаи, но не намирам грешка. Освен това не е паднала еднакво в двата случая, което е също интересно защо.

[drago]

В remark 2 на цитираната статия има връзка м/у детерминантата на Кейли-Менгер и обема $V$ на тетраедъра.
$$V=\frac{1}{12\sqrt{2}}\sqrt{D(S)}.$$
Нещо подобно на Хероновата формула за лице на триъгълник. Което и обяснява защо $D(S)>0$. Това ми напомни на една задача от състезанието Миклош Швайцер, 2018. Там тази формула е дадена в по-компактен запис.