piatok 9. septembra 2011

Nedotýkajúce sa body

edit: Pozor, zadanie je trochu problematické, opravené znenie definície nájdete v komentároch.

V knižke Martina Gardnera som narazil na zaujímavý pojem: nontouching points. Rovinná definícia by mohla znieť takto:

Body X a Y sa nedotýkajú ak existuje r>0 také, že bod Y neleží v kruhu s polomerom r a stredom X. Množina nedotýkajúcich sa bodov je taká množina bodov, z ktorých sa žiadne dva nedotýkajú.

Úplne polopate povedané - 2 body sa nedotýkajú ak ich od seba vieme oddeliť kružnicou. S takýmito bodmi sa dajú vymýšľať rôzne hádanky. Napríklad:

1. Koľko takýchto bodov sa dá "nakresliť" do štvorca v rovine?

2. Vedeli by ste vymyslieť nejaký predpis/systém na určenie spočítateľného nekonečna nedotýkajúcich sa bodov v štvorci?

3. Dalo by sa v štvorci určiť nespočítateľné množstvo nedotýkajúcich sa bodov? Vedeli by ste určiť nejaký predpis/systém, alebo dokázať, že sa to nedá?

8 komentárov:

Lukáš Poláček povedal(a)...

Dobré, zase ma intuícia oklamala.

Radoslav Harman povedal(a)...

Zda sa mi to trochu nejasne. Predsa kazde dva rozne body X,Y v rovine maju tu vlastnost, ze existuje polomer r>0 taky, ze Y nelezi v kruhu so stredom v X a polomerom r.

rasťo povedal(a)...

Hmm, to je pravda. Skusim sa este pozriet na toho Gardnera, co tym pojmom teda myslel.

Charon ME povedal(a)...

mozno sa to povodne myslelo tak, ze ten existujuci polomer mal platit pre celu mnozinu (pre kazdu dvojicu bodov v danej mnozine)?

katka povedal(a)...

Keby sme zobrali do uvahy tu Charonovu definiciu, teda keby malo existovat nejake r>0 take, ze lub. dva vybrane body su od seba vzdialene aspon r, tak do stvorca vieme napchat len konecne vela takychto "navzajom sa nedotykajucich" bodov.

Konecne vela ich tam vieme vybrat vzdy (a dokonca mozu byt uplne lubovolne rozmiestnene), lebo za r zoberieme minimum zo vzdialenosti vsetkych dvojic vybranych bodov (alebo nieco o trochu mensie). Kedze tych bodov je konecne vela, minimum musi existovat.

Lubovolny nekonecny pocet vybratych bodov vo stvorci uz takejto definicii nemoze vyhovovat. Totiz ak by sme si zvolili akokolvek male (ale kladne) r, a stvorec by sme rozdelili na male stvorceky s uhloprieckou r (proste by sme natiahli nekonecnu stvorcekovu siet), tak potom podla Dirichletovho principu (http://en.wikipedia.org/wiki/Pigeonhole_principle) by v niektorom stvorceku museli byt aspon 2 vybrate body, cize ich vzdialenost by bola mensia ako r. Takze neexistuje ziadne take kladne r, aby vzdialenost lub. dvoch vybratych bodov bola aspon r.

Mne by sa pacila takato definicia:
Mnozina bodov M (leziacich v jednej rovine) sa nazyva mnozina navzajom nedotykajucich sa bodov, ak pre kazdy bod X z mnoziny M existuje take kladne r, ze v kruhu so stredom X a polomerom r nelezi ziadny dalsi bod z mnoziny M.

rasťo povedal(a)...

Jej, Katka, vdaka, super definicia, je dost mozne, ze tym myslel Gardner prave toto (nenasiel som k tomu od neho zatial viac).

OK, v takomto duchu by teda opat mohlo byt zaujimave, ake velke nekonecno tychto bodov mozno ulozit do stvorca.

Spocitatelne mnozstvo by islo lahko napr. [x; y] = [(1/2)^n ; 0,5], kruh pre n-ty bod by potom mohol mat polomer napr. (1/2)^(n+2).

Dalo by sa ich tam ale dat c?

goober povedal(a)...

V každom kruhu kladného polomeru sa nachádza aspoň jeden bod s racionálnymi súradnicami. No a keďže tých je v štvorci (ba aj v celej rovine) iba spočítateľne veľa, oných kruhov (a ich stredov) nemôže byť viac než spočítateľné nekonečno.

goober povedal(a)...

Aha, ešte som zabudol spomenúť jednu podstatnú ingredienciu -- samozrejme, tie "kruhy" patriace k jednotlivým bodom by nemuseli byť disjunktné (a teda úvaha o tom, že každý kruh má "svoj" racionálny bod by neprešla). Stačí však každý kruh zmenšiť na polovičný polomer a tento problém odpadne.

Inak, tá úloha je super -- ukazuje, že prehodením kvantifikátorov sa úloha a jej výsledky môžu podstatne zmeniť. Ak E bude existenčný, V univerzálny kvantifikátor a d(x,y) je vzdialenosť bodov, tak sa to dá napísať takto:

Pôvodná verzia:
Vx Vy Er>0: d(x,y)>r => nespočítateľne

Katkina verzia:
Vx Er>0 Vy: d(x,y)>r => spočítateľne

Charonova verzia:
Er>0 Vx Vy: d(x,y)>r => konečný počet