Príspevok číslo 8 nám do súťaže poslal šachový skladateľ Ivan Skoba. Táto zaujímavá úloha sa na blogu QED už síce kedysi dávno objavila, avšak nevyvolala väčší záujem a riešenie nám dosiaľ chýba.Jaké plošně největší těleso lze přestěhovat chodbou s pravoúhlým zalomením o jednotkové šířce? Projde čtverec (plocha = 1), dále půlkruh (1,57), ale stále to není největší těleso. Zdá se, že to bude část mezikruží (viz obrázek). Je to pravda? Jakou největší plochu můžeme chodbou přemístit?
Komentár I. Skoba: Úloha je převzatá – Technický magazín („Téčko“) někdy z přelomu 70.–80. let. V „Téčku“ vycházela na pokračování rubrika Matematické rekreace, ve které byly předkládány k řešení zajímavé úlohy, jejichž řešení bývalo uveřejňováno později. Tato je jednou z nich (je formulována po paměti).
Komentár R. Harman: Ja som sa s touto úlohou stretol prvýkrát predminulý rok v jednej peknej knihe o optimalizácii. Uvedené riešenie bolo označené ako "najlepšie známe", takže tento problém je dosiaľ nevyriešený. Zadanie úlohy teda môžeme chápať ako súťaž, kto nájde útvar s čo najväčšou plochou.
Já nad tím občas přemýšlím, ale pořád nejsem u cíle..
OdpovedaťOdstrániťTady je moje řešení této skvělé úlohy.
OdpovedaťOdstrániťŘešení
Václav Kotěšovec
hm, teda zatial to vyzera tak, ze najlepsie sa stahuju telefony, to bude mat T-Com radost
OdpovedaťOdstrániťVáclav našiel veľmi zaujímavý útvar, ktorého plocha je viac ako 2. Toto riešenie však stále nie je optimálne, hoci k najväčšiemu známemu útvaru mu chýba len máličko.
OdpovedaťOdstrániťKto nájde zlepšenie, má môj obdiv a to napriek tomu, že najlepší známy útvar nie je veľmi komplikovaný. (Pozn.: Nad týmto problémom sa už zamýšľalo viacero ľudí s PhD. z matematiky a nenašli ani útvar veľkosti 2. Napriek tomu nájsť väčší útvar je aj v silách stredoškoláka s dobrou geometrickou predstavivosťou a základnými znalosťami o kvadratickej funkcii.)
Moje řešení s dvěma elipsami (a plochou 2.003) jde ještě trochu vylepšit, když nebudu předpokládat, že elipsy jsou si podobné. Vyšel mi útvar, kde vnější hranicí je elipsa, ale vnitřní elipsa zdegeneruje na kružnici. Plochou jsem se tak dostal na 2.1817.
OdpovedaťOdstrániťPředpokladám ale, že to je stále ještě méně než plocha útvaru z té knihy? Znáte její přesnou hodnotu ?
Václav
Jestli jsem ten obrázek z knihy dobře pochopil, tak jejich plocha je
OdpovedaťOdstrániťpi/4 + sqrt(2) = 2.199611725
Takže opravdu stále o "chlup" více i než moje vylepšené řešení.
VK
Václav: Podľa mojich výpočtov má ten útvar z knihy plochu až 2/π+π/2, čo je približne 2,207. Nechajme na ostatných, nech sa ho pokúsia nájsť.
OdpovedaťOdstrániťPekná úloha. Chcelo by sa mi nad ňou aj zamyslieť (viac než včera o polnoci na 10 minút, pričom som na nič dôležité neprišiel), ale teraz mám práce ajajáj juchuchú.
OdpovedaťOdstrániťBudem teda aspoň sledovať či sa ešte bude diskusia vyvíjať.
Neviem si však celkom predstaviť ako by dôkaz o optimálnosti útvaru vyzeral; resp. nevidím zatiaľ žiadne "tools" ktoré by ho umožňovali.
Stálo by ale za to sa zamyslieť nad nájdením optimálneho >>konvexného<< útvaru.
Najlepšie známe riešenie je o trošku väčšie ako to jednoduché (2/pi + pi/2), ktoré sa tu spomína. Je však veľmi komplikované. Na sústredení o dva týždne budem mať zhodou okolností sťahovaciu prednášku, ale zašneme niečím jednoduchším, ako rebríky a tak ;) Uvidíme, kam sa s deckami dostanem :)
OdpovedaťOdstrániťOndro: Ďakujeme za znalecký komentár. To riešenie 2/π+π/2 mám z jednej veľmi serióznej knihy vydanej vydavateľstvom Princeton University Press, kde je označené ako "best attempt known". A vidíš ho, mýlia sa.
OdpovedaťOdstrániťTo komplikované riešenie by ma zaujímalo; možno by si mi ho mohol ukázať po prednáške práve na tom sústredení o dva týždne :)
To riešenie nepoznám. Je o ňom niečo na Mathworlde, ale neni tam nakreslené a nechcelo sa mi lúštiť tie rovnice. Akurát sa snažím prísť na jednoduchý spôsob ako odvodiť rovnicu astroidy (nevyužívajúci calculus). Túto rovnicu potrebujeme ak chceme sťahovať rebrík cez L-chodbu, kde tie dve chodby, ktoré sa spávajú, majú rôznu veľkosť.
OdpovedaťOdstrániťOndro: Inak povedal by si, že Mathworld spravuje a píše len jeden človek? Raz som ho v US stretol a roprával o tom ako to založil a ako na tom robí. Vtedy sa ešte porovnával s Math na Wiki, a vychádzalo mu to na 50-50. Teraz už asi ani nie, tipujem.
OdpovedaťOdstrániťPeter: Ty si sa rozpraval s Erikom Weissteinom? Ty brďo.
OdpovedaťOdstrániťInak prednedávnom som čítal jednu knihu od Oliviera Sacksa a tam spomínal, že pracoval s jedným fenomenálnym chlapcom, ktorého nazýval skratkou EW. Ten chlapec údajne vedel čítať ako dvojročný a navyše aj tomu čo čítal rozumel. Vedel by som si tipnúť, kto to bol. :-)
Hej, Eric študoval kedysi na Cornelli (myslím, že v 90tom roku skončil?), a raz nám prišiel na department dať talk o tom čo robí na Mathworlde. Prehodili sme zopár slov ale bližšie ho nepoznám. Spomenul som si na neho pri tom Ondrovom odkaze na MathWorld. Bol to zaujímavý talk, i keď trošku melancholický, keďže jeho skvelé stránky začal predbiehať Wiki model robenia vecí.
OdpovedaťOdstrániťOn je na všetko sám, a má to tak rád. Vravel, že má určitý štýl, ktorý mu vyhovuje. Inak prijíma aj návrhy na to, čo by bolo treba poupraviť alebo doplniť a podobne. Prípadne aj celú stránku keď niekto spravíte a bude sa mu páčiť...
Pěkná diskuse, ale nikdo neuvedl link, tak tady je:
OdpovedaťOdstrániťMovingSofaProblem
2.2195 !!!
Václav
Tá stránka z Mathworldu je trochu zvláštna. Človek sa dozvie úplne presný a extrémne komplikovaný popis ako vypočítať obsah dosiaľ najväčšieho útvaru, ktorý sa tým rohom dá premiestniť, ale ako ten útvar vlastne vyzerá už nie je nijako spomenuté. Aspoň približný náčrt mohli uviesť.
OdpovedaťOdstrániťKaždopádne je jasné, že nájsť optimálne riešenie (a dokázať jeho optimalitu) je brutálne ťažký problém.
Inak vlastne stále tu nikto neuviedol tvar tej oblasti s plochou π/2+2/π :-)
Efektní animaci i horní odhad maximální plochy 2*sqrt(2) lze nalézt i ve Wikipedii:
OdpovedaťOdstrániťMoving sofa problem
Pekná animácia na tej wikipedii; ďakujeme za link. Myslel som aj ja na to, že takú animáciu neskôr urobím (samotná sofa ako aj jej dráha je veľmi jednoduchá), ale takto to už nemá zmysel.
OdpovedaťOdstrániťStále by ma však veľmi zaujímalo ako vyzerá, aspoň približne, tá väčšia Gerverova sofa. Nikde nie je ani len jej náčrt.
Tak Václav už našiel zdroj, v ktorom sa tá dosiaľ optimálna Gerverova sofa nachádza. Veľmi sa podobá na tú jednoduchú sofu animovanú na wikipedii, ale je trochu "zaoblenejšia" a to v tvare komplikovaných kriviek.
OdpovedaťOdstrániť