13 marca 2008

Ortogonálne krájanie

Je možné každý konvexný rovinný útvar rozdeliť dvomi navzájom kolmými priamkami na štyri časti s rovnakým obsahom?

Poznámka 1: Konvexná množina v rovine je taká, že ak obsahuje body A a B, tak obsahuje aj všetky body úsečky AB.

Poznámka 2: Táto úloha patrí k matematickým evergreenom. Ťažko vystopovať jej pôvod, každopádne riešenie obsahuje už slávna kniha "What is Mathematics?" z roku 1941.

13 komentárov:

Lukáš povedal(a)...

Podľa mňa by to mohla byť pravda. Využijem fakt, že ak f je spojitá funkcia a nadobúda hodnotu 0 a 1, tak potom nadobúda aj 0.5.

Začnem tým, že rozrežem množinu na polovicu. To sa vždy dá. Zoberiem ľubovoľnú priamku niekde ďaleko od množiny a posúvam ju, až kým priamka nerozdelí množinu na polovicu (funkcia rozrezania by mala byť spojitá a nadobúdať hodnoty 0 a 1).

Rez množinou na polovicu tvorí úsečka AB (je to úsečka vďaka konvexnosti). Označme tieto polovice C a D. Teraz pre každý bod X na úsečke AB zavedieme funkciu f(X) a jej hodnotu určime takto: bodom X vedieme priamku p, ktorá rozdelí polovicu C na štvrtiny. Veľkosť jednej z rozrezaných častí v polovici D je hodnota f(X). (Jeden drobný detail: treba si na začiatku povedať, ktorá rozrezaná množina nás bude zaujímať; môžem si napríklad zvoliť tú južnejšiu). Znova, táto funkcia nadobúda hodnoty 0 a 1 medzi bodmi A a B. A snáď je aj spojitá.

Spojitosť oboch funkcií sa mi nechce formálne dokazovať, ale je vidno, že ak posuniem/otočím priamku o kúsok, hodnota sa nezmení o veľa.

Lev bez hrivy povedal(a)...

Lukas, podla mna tam mas jeden logicky nedostatok. Ako vies, ze ked f(X) je 0.5, tak prave vtedy je ta priamka kolma na povodnu priamku?

(To som pominul otazku spojitosti, lebo s tou sa ani ja neviem korektne vysporiadat.)

Anonymný povedal(a)...

a nie je to nahodou tak, ze staci tie dve kolmice prelozit taziskom utvaru a uloha je tym padom vyriesena (utvar je rozdeleny na styri obsahom zhodne casti)?

Anonymný povedal(a)...

aha, pardon. [dvakrat meraj a raz posielaj prispevok :-)] predchadzajuci prispevok beriem spat, akurat zostava tip, ze by sa tie kolmice mali prekladat taziskom. a dalej uz len hadam, ze sa daju vzdy vhodne natocit...:-)

Lev bez hrivy povedal(a)...

No ano, to je tusim ono! Povedzme, ze po prelozeni tych kolmic s priesecnikom v tazisku je obsah styroch casti po rade 1/4-a, 1/4+a, 1/4-a, 1/4+a, kde a<>0. Tocme teraz krizom. Mala by fungovat Lukasova spojitost, takze po stvrt otacke budu mat stale tie iste casti presne 1/4+a, 1/4-a, 1/4+a, 1/4-a. No a kedze sme sa od 1/4-a dostali spojite k 1/4+a, niekde sme museli byt v 1/4.

Hm?

Lukáš povedal(a)...

To, že tie priamky majú byť kolmé, som si nevšimol. Ten môj postup sa asi už nedá opraviť, aby to fungovalo.

Radoslav Harman povedal(a)...

Zdravím. Som rád, že Vás táto úloha zaujala. Mám pre Vás nejaké hinty: Máte pravdu, že také ortogonálne krájanie je vždy možné a Lukášov postup sa v istých detailoch dosť podobá správnemu dôkazu (napríklad využitie "zrejmej" spojitosti nejakej funkcie).

Ale to s tým ťažiskom je len "zvodnosť", ako by možno povedal kompozičný šachista. Pozri tento obrázok, kde ABC je rovnostranný pravouhlý trojuholník.

Mimochodom, veľmi podobný omyl je myslieť si, že stredná hodnota (čo je "ťažisko hustoty" náhodnej premennej) je to isté ako medián (čo je taká hodnota, ktorá delí plochu pod hustotou na polovice).

Lev bez hrivy povedal(a)...

Hm... kontrapriklad je kontrapriklad... s tym medianom a strednou hodnotou, to mas pravdu, uprimne povedane, myslel som si, ze tazisko je bod taky, ze kazda priamka cezen rozdeli utvar na polovicu. Takze to je dovidenia... :-)

Nanyk povedal(a)...

jej..skusim napriklad tuna tak heuristicky...

zalepim lubovolny bod X na hranici utvaru a druhy Y nech cestuje od X po hranici, spojitost a konvexnost ruci ze obsah povodne mensej oblasti stale rastie(usecka je stale vnutri utvaru) az zastavim ak bude pol na pol(zrejme pre kazde epsilo existuje delta vzdialenost na hranici o ktoru ked posunieme usecku tak zmena obsahu je epsilon)...teraz vezmem kolmicu a budem ju posuvat spojitost konvexnost (stejny dovod) a mame nase kolmice

je to zle?

Radoslav Harman povedal(a)...

Nanyk: Podobné techniky založené na spojitosti sa naozaj dajú použiť, ale Tvoje riešenie nie je úplne kosher.

Predstav si napríklad obdĺžnik s vrcholmi (-10,-1), (10,-1), (10,1), (-10,1). Potom Tvojou technikou (pre isté voľby fixného bodu X) môžeš získať kolmice y=x a y=-x. Je fakt, že na oboch stranách oboch priamok je plocha 1/2 obdĺžnika, ale vznikuté štyri odseky napriek tomu nemajú po jednej štvrtine!

Nanyk povedal(a)...

vidim, unahlil som sa

skusim to teda dotiahnut ale iba takto este viac heuristicky(a neohrabane):

po prevedeni uvedeneho algoritmu mame utvar rozdelani na 2x dve polky, problem je ci su to stvrtiny. Pozrieme sa na jednu polku urcenu priamkou XY, ta je delena na dve casti priamkou AB. Ak by boli tieto dve zhodne, tak je utvar cely rozdeleny na stvrtiny(pretoze protilahla polka je potom tiez rozdelena na zhodne casti)

ak teda nenastal tento pripad tak jedna cast tej polky je vacsia

prieniky kolmic s hranicou utvaru nech su teda X',Y',A',B'
S' priesecnik kolmic

budeme bodom X hybat po hranici od X' po B' a v kazdom bode hranice prevedieme spomenuty algoritmus ktory najde kolmice ktore rozdeluju 2x utvar na polky

vzniknute kolmice a ich prieniky budeme znacit bez ciary

nech obsah casti utvaru obmedzenej bodmi X'S'A' (prislusnymi useckami) je vacsi ako Y'S'A' oblast

ak sa budeme posuvat bodom X z povodneho X' k povodnemu bodu B' a nenastane pripad ze cely utvar sa rozdeli na stvrtiny tak to znamena ze stvrtina X'S'A' pretransformovala na stvrtinu Y'S'X' a pri tom bola stale vacsou castou polky, to je ale spor s tym ze A'B' deli utvar na polky.

(znovu sme pouzili spojitost)

Nanyk povedal(a)...

preklep: x'S'A' pretransformovala na B'S'X'

Radoslav Harman povedal(a)...

Nanyk: Áno, podstata Tvojej myšlienky je správna, aj keď zapísať to dokonale je dosť zdĺhave. Takže príklad považujem za vyriešený.

Ja som si poprivymyslel nasledovný dôkaz (má veľa spoločných čŕt s tým Tvojim):

Majme orientovanú priamku p, ktorá je na začiatku totožná s x-ovou osou. Túto priamku môžeme rovnobežne posunúť tak, aby rozdeľovala danú množinu na polovice (z hľadiska plochy).

Každý z dvoch vzniknutých odsekov vieme rozdeliť na polovice polpriamkami p1 a p2, ktoré sú kolmé na p a ich päty X1 a X2 ležia na p. Vo všeobecnosti však X1 a X2 nemusia byť totožné (Ak by boli, tak máme požadované delenie na štvrtinky.)

Vzdialenosť piet X1 a X2 v smere orientovanej priamky p si označme d, ktoré je, bez straty na všeobecnosti, kladné. Uhol náklonu priamky p budeme teraz spojite meniť až kým nebudeme mať priamku p totožnú s y-novou osou (stále pritom udržujeme to, aby p delila útvar na polovice plochy; pri každom náklone je to samozrejme možné). V tomto konečnom prípade však bude vzdialenosť piet X1 a X2 v smere orientovanej priamky p už nutne záporná! (Ak by nebola, dosiahli by sme spor ako je znázornené na tomto obrázku.)

Keďže vzdialenosť d sa mení spojite s uhlom náklonu p, tak pri niektorom sklone museli päty X1 a X2 splývať. V okamihu splynutia piet X1 a X2 sme museli mať delenie útvaru na štvrtinky priamkou p a na p kolmou priamkou, ktorá vznikne zjednotením p1 a p2.

QED.