25 februára 2011

Ťažisko rezu

Metóda "alias" používaná na simulačné generovanie diskrétnych náhodných premenných sa opiera o vetu, ktorej špeciálny prípad je možné pekne geometricky interpretovať:

Akýkoľvek bod C vo vnútri štvorstena je ťažiskom nejakého trojuholníka, ktorého vrcholy ležia na hranách tohto štvorstena.

Vedeli by ste túto vetu dokázať? Napadajú Vás nejaké zovšeobecnenia tejto vety?

(Ospravedlňujem sa všetkým riešiteľom, ktorí sa trápili s pôvodnou nesprávnou formuláciou vety.)

7 komentárov:

Brano povedal(a)...

myslim, ze ta veta neplati. podme sa na to pozriet rovno v n rozmeroch.
nas "stvorsten" je konvexny obal rcholov A0,A1,..., An a vnutorny bod B=S(pi*Ai) kde S() je suma, i ide od 0 po n a S(pi)=1. oznacme vk=Ak-A0 (k ide od 1 po n) potom B=A0+S(pk*vk) ak chceme aby B bolo tazisko konvexneho obalu Bk, pricom Bk lezia na polpriamkach (hranach) vychadzajucich z A0 tak B=S(Bk)/n=S(A0+n*pk*vk)/n ak vsak maju byt Bk na hranici nasho "stvorstena", potom musi platit n*pk<=1
ak n=1 mame podmienku p1<=1 co plati,
ak n=2 mame podmienku p1,p2<=1/2 co mozme dosiahnut tym ze vyberieme A0 tak aby p0 bolo maximalne,
ale ak n=3 potom podmienka p1,p2,p3<=1/3 nemusi byt splnena mozme napriklad zvolit p0=p1=0.4 a p2=p3=0.1

tak neviem ci som urobil niekde chybu, alebo zle pochopil zadanie ale podla mna je kontraprikladom
A0=(0,0,0) A1=(10,0,0) A2=(0,10,0) A3=(0,0,10) B=(4,1,1)

goober povedal(a)...

Hehe, Braňo... takto múdry som bol aj ja :-)

Problém v Tvojej úvahe je ten, že ten rez nemusí sekať iba hrany vychádzajúce z jedného vrchola. V troch rozmeroch to napríklad nemusí byť trojuholník -- pri pravidelnom štvorstene ABCD stačí vziať stredy hrán AC, AD, BC, BD a máš netrojuholníkový rez.

Osobne ale tiež pochybujem o platnosti tej vety -- napriklad zatiaľ neviem vybabrať so štvorstenom (0,0,0), (48, 0, 0), (0, 48, 0), (0, 0, 48) a bodom vnútri (25, 17, 5, 1).

Radoslav Harman povedal(a)...

Fú, chalani, sorry. Ste dobrí, chybu som urobil ja :(. Tá geometrická interpretácia by mala správne znieť takto: Každý bod C vnútri štvorstena je v ťažisku nejakého trojuholníka, ktorého vrcholy ležia na hranách štvorstena. To samozrejme nemusí byť ťažisko rezu, pokiaľ ten rez nie je trojuholník...

goober povedal(a)...

Akosi sa nikomu nechce nič napísať... tak napíšem aspoň ja stručnú myšlienku môjho dôkazu.

Majme štyri vrcholy štvorstena, volajúce sa A, B, C, D. Zavedieme si homogénne súradnice -- t.j. každý bod vyjadríme ako lineárnu kombináciu (a.A + b.B + c.C + d.D), pričom požadujeme, aby a+b+c+d = 1. Štvorstenu potom zodpovedajú nezáporné hodnoty všetkých štyroch súradníc. Jeho hrany vyzerajú tak, že dve zo súradníc dávajú v súčte jednotku a zvyšné (dve) sú nulové.

Ťažisko trojuholníka sa dá vyjadriť ako jedna tretina zo "súčtu" jeho vrcholov. Ak teda (a,b,c,d) sú očakávané súradnice ťažiska, chceme vektor (3a, 3b, 3c, 3d) rozložiť na súčet troch vektorov, v ktorých vždy dve zložky dávajú súčet 1 a zvyšné sú nulové.

Toto sa dá urobiť aj všeobecnejšie -- akýkoľvek vektor s (N+1) kladnými súradnicami (a0, ..., aN), ktorých súčet je N, sa dá rozložiť na súčet N vektorov, ktoré majú po dve súradnice so súčtom 1 a ostatné nulové. Stačí totiž vziať minimálnu a maximálnu súradnicu (bez ujmy na všeobecnosti sú to aN a a0) a uvedomiť si, že a0 + aN >= 1. Keby to tak nebolo, platí ai + aN < 1 pre i=0..(N-1) (keďže a0 je maximálna súradnica). Potom ale a0 + a1 + ... + N*aN < N, čo je v spore s predpokladom, že a0 + a1 + ... + aN = N. No a teraz stačí vziať vektor (1-aN, 0, ..., 0, aN) a odrátať ho od toho pôvodného. Ich rozdiel má poslednú súradnicu nulovú a súčet ostatných je (N-1) -- takže môžeme isť indukciou ďalej.

Napríklad v Braňovom príklade sú tie homogénne súradnice toho "plánovaného ťažiska" (0.4, 0.4, 0.1, 0.1); po vynásobení trojkou je to (1.2, 1.2, 0.3, 0.3). Aplikovaním tohoto postupu dostaneme rozklad (0.7, 0, 0, 0.3) + (0, 0.7, 0.3, 0) + (0.5, 0.5, 0, 0). V klasických súradniciach to zodpovedá bodom (0,0,3), (7,3,0), (5,0,0).

Radoslav Harman povedal(a)...

goober, opäť super. V podstate si dokázal hlavnú vetu k alias metóde, ktorá tvrdí, že akákoľvek diskrétna náhodná premenná s konečným nosičom sa dá napísať ako "equiprobable mixture" náhodných premenných, z ktorých každá má nanajvýš dvojprvkový nosič. Tvoj dôkaz je inak technicky veľmi podobný "kanonickému" dôkazu.

goober povedal(a)...

Tak, ľahký problém sme vyriešili... teraz už len vyriešiť Radovu pôvodnú úlohu :-)

Jej mierne upravené znenie je: Máme štvorsten. Existuje v jeho vnútri bod, ktorý nie je ťažiskom žiadneho jeho rezu?

Rovnako to môžeme potiahnuť do N rozmerov -- namiesto štvorstena vezmime nejaký N-rozmerný konvexný útvar.

Napríklad pre 2 rozmery by odpoveď mala byť "nie". Veďme cez ten náš bod hocijakú priamku. Tato pretne hranicu útvaru v dvoch bodoch, čím vyrobí dve úsečky -- od nášho bodu na jednu a druhú stranu. Vezmime si rozdiel ich dĺžok. Keď budeme priamku spojite otáčať, tento rozdiel sa bude spojite meniť. Po otočení o 180 stupňov bude rovnaký ako na začiatku, ale s opačným znamienkom. No a to nám už stačí na to, aby sme vedeli, že niekde medzitým musel byť rovný aj nule -- a teda náš bod bol "ťažiskom" (= stredom) príslušného "rezu".

V troch rozmeroch zase napríklad taká guľa predstavuje jednoduchý prípad, kde je tiež odpoveď "nie". Štvorsten ale zatiaľ dôkazu úspešne odoláva :-)

Radoslav Harman povedal(a)...

goober: Samozrejme moja pôvodná úloha je úplne zmysluplná (ak ju opatrne formulujeme v zmysle zistiť, či platí, a nie dokázať, že platí), pomerne zaujímavá a netriviálna. Je možné, že som "omylom" natrafil na pekný problém. Ešte nad ním viac porozmýšľam aj ja a prípadne ho formulujem ako samostatný príspevok.