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.
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.
OdpovedaťOdstrániť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.
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?
OdpovedaťOdstrániť(To som pominul otazku spojitosti, lebo s tou sa ani ja neviem korektne vysporiadat.)
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)?
OdpovedaťOdstrániť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...:-)
OdpovedaťOdstrániť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.
OdpovedaťOdstrániťHm?
To, že tie priamky majú byť kolmé, som si nevšimol. Ten môj postup sa asi už nedá opraviť, aby to fungovalo.
OdpovedaťOdstrániť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).
OdpovedaťOdstrániť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).
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... :-)
OdpovedaťOdstrániťjej..skusim napriklad tuna tak heuristicky...
OdpovedaťOdstrániť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?
Nanyk: Podobné techniky založené na spojitosti sa naozaj dajú použiť, ale Tvoje riešenie nie je úplne kosher.
OdpovedaťOdstrániť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!
vidim, unahlil som sa
OdpovedaťOdstrániť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)
preklep: x'S'A' pretransformovala na B'S'X'
OdpovedaťOdstrániť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ý.
OdpovedaťOdstrániť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.