19 januára 2009

Stěhovací problém (Súťažná úloha č.8)

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.

19 komentárov:

Tychi povedal(a)...

Já nad tím občas přemýšlím, ale pořád nejsem u cíle..

Anonymný povedal(a)...

Tady je moje řešení této skvělé úlohy.

Řešení

Václav Kotěšovec

Brano povedal(a)...

hm, teda zatial to vyzera tak, ze najlepsie sa stahuju telefony, to bude mat T-Com radost

Radoslav Harman povedal(a)...

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.

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.)

Anonymný povedal(a)...

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.
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

Anonymný povedal(a)...

Jestli jsem ten obrázek z knihy dobře pochopil, tak jejich plocha je
pi/4 + sqrt(2) = 2.199611725

Takže opravdu stále o "chlup" více i než moje vylepšené řešení.
VK

Radoslav Harman povedal(a)...

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ť.

Peter Richtárik povedal(a)...

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ú.

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.

Ondro Budac povedal(a)...

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 :)

Radoslav Harman povedal(a)...

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.

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 :)

Ondro Budac povedal(a)...

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ť.

Peter Richtárik povedal(a)...

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.

Radoslav Harman povedal(a)...

Peter: Ty si sa rozpraval s Erikom Weissteinom? Ty brďo.

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. :-)

Peter Richtárik povedal(a)...

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í.

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ť...

Anonymný povedal(a)...

Pěkná diskuse, ale nikdo neuvedl link, tak tady je:
MovingSofaProblem
2.2195 !!!

Václav

Radoslav Harman povedal(a)...

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ť.

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/π :-)

Anonymný povedal(a)...

Efektní animaci i horní odhad maximální plochy 2*sqrt(2) lze nalézt i ve Wikipedii:
Moving sofa problem

Radoslav Harman povedal(a)...

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.

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.

Radoslav Harman povedal(a)...

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.