02 februára 2010

Nedosiahnuteľné body

Vo vnútri kruhu máme zakreslený bod A. Na hranici tohto kruhu zvolíme bod B, spojíme ho s bodom A úsečkou a stredom úsečky AB budeme kolmo viesť tetivu t. Uvažujme množinu tých bodov kruhu, ktorými tetiva t určite nemôže prechádzať, nech by sme B zvolili kdekoľvek na hranici kruhu. Čo všetko vieme o tejto množine bodov povedať? 

Poznámka 3.2.: Úlohu už prakticky vyčerpávajúco vyriešil Peťo a to dokonca vo všeobecnej, mnohorozmernej verzii; viď jeho blog.

12 komentárov:

Charon ME povedal(a)...

Z obrazkov len tipujem ze by to mohlo byt nieco blizke vnutru elipsy s osami R a sqrt(R^2-x^2) kde X je vzdialenost bodu A od stredu a R je polomer kruhu, ale na viac sa nezmozem. Aj tak mam podozrenie ze az take lahke to nebude :)

goober povedal(a)...

Jedna pani rovnoľahlosť povedala: Dnes je streda, takže to bude otvorený, stredne veľký kruh so stredom v strede medzi stredom pôvodného kruhu a bodom A.

Peter Richtárik povedal(a)...

Ulohu riesme vseobecne v n-rozmernom priestore (kruh = n rozmerna gula, tetiva = nadrovina kolma na A-B prechadzajuca stredom usecky; nebudeme sa teda obmedzovat na jej prienik s gulou). Pytajme sa teda, ktore body R^n (a nie len gule) nelezia na ziadnej z nadrovin.

Predpokladajme ze A je vo vnutri gule a ze gula ma stred 0 a polomer 1.

Hladana mnozina je tato:

S = { X z R^n take ze ||X|| - (A,B) < (1 - ||A||^2)/2 },

kde ||X|| je Euklidovska norma (dlzka) vektora X a (A,B) je skalarny sucin A a X.

Navyse sa da dokazat, ze mnozina S lezi cela vnutri gule; teda vsetky body leziace mimo gule a na jej povrchu lezia na niektorej z nadrovin.

Poznamka: Vsimnime si, ze ak A = 0, potom S je prazdna, a tak to ma byt.

Pripad, ked A nelezi vnutri gule, sa da riesit podobne; napisem ked budem mat viac casu...

Takisto samotne riesenie napisem neskor...

Radoslav Harman povedal(a)...

Peťo: Hmmm. A je to teda v 2D pripade elipsa, ako tipoval Charon, alebo dokonca kruh, ako si mysli goober? :-)

Peter Richtárik povedal(a)...

Mam tam typograficku chybicku: miesto (A,B) ma byt samozrejme (A,X)!

Peter Richtárik povedal(a)...

Hej, je to ellipsoid tvaru

{x : (x-v)^T*H(x-v) <= r^2},

kde v = a/2 je jeho stred, H = I - a*a^T je kladne semidefinitna matica urcujuca jeho tvar, a polomer ma r = 0.5*(1-t)*sqrt(1 + t/(1-t)), kde t = ||a||^2.

Peter Richtárik povedal(a)...

Samozrejme tam ma byt ostra nerovnost...

Peter Richtárik povedal(a)...

Úloha sa mi veľmi páčila, dík Rado! Tu je sľúbené riešenie:

http://predbara.com/2010/02/03/riesenie-radovej-ulohy-nedosiahnutelne-body/

Radoslav Harman povedal(a)...

Peťo, super!

Inak hneď ako si uviedol svoje riešenie v komentári som začal kresliť nejaké obrázky, ale ako vidím, Ty si ma predbehol, takže už nemá zmysel, aby som to viac komentoval...

Peter Richtárik povedal(a)...

Doplnková úloha: Dokážte, že Radovu množinu S (ktorá sa ukázala byť otvorenou elipsou) možno (pre každé A vo vnútri kruhu K) vpísať do kruhu C polovičného polomeru ako má K, pričom:

a) C sa celý nachádza v K
b) C je kruh najmenšieho polomeru s pomedzi všetkých, ktoré obsahujú S

goober povedal(a)...

Ááááá... to mám z toho, že si veci poriadne nenakreslím. Som si len predstavil tie stredy úsečiek AB, ktoré ležia na kružnici, ktorej polomer je polovica polomeru K a stred je v strede medzi A a stredom K. No a nejako som potom akosi usúdil, že všetko vnútri tohoto tvorí Radovu množinu... Na druhej strane, tuším je to práve ten kruh C z doplnkovej úlohy :-)

Najmenšosť by mohla vyplývať z takejto úvahy: Vezmime si priamku, ktorá prechádza bodom A a stredom kruhu K. Tá nám pretne kružnicu K v dvoch bodoch, B_1 a B_2. No a keď vezmeme stredy úsečiek AB_1 a AB_2, tak tieto patria do mnoźiny S a pritom sú od seba vzdialené o polovicu priemeru K.

Ale možno zle vidím aj teraz :-)

Peter Richtárik povedal(a)...

Goober: Tvoja úvaha/stratégia sa mi zdá byť košér.

Samozrejme by bolo treba ísť na to rigorózne a každý krok dokázať. Napríklad tie stredy úsečiek AB_1 a AB_2 nepatria do S, ale malo by sa dať ukázať, že patria do uzáveru S (teda, že existujú body z S ľubovoľne blízko týmto bodom). Súhlasím s tým, že to takto vyzerá, bolo by to však potrebné dokázať.

Tu som ten kruh nakreslil:

http://predbara.com/2010/02/03/najmensi-kruh-obsahujuci-radovu-mnozinu/

Okrem vyššie spomenutej doplnkovej úlohy je tu ďalšia:

http://predbara.com/2010/02/04/najmensi-sustredny-kruh-obsahujuci-radovu-mnoznu/