15 augusta 2008

Katalóg konvexných polyédrov

Pri riešení najnovšieho problému od Peťa ma napadlo, že by sme si mohli zadať nasledovnú úlohu trochu nezvyklého typu:

Na obrázku vyššie (kliknutím sa zväčší) zodpovedajú riadky počtu v vrcholov a stĺpce počtu e hrán. Do niektorých políčok som už doplnil telesá, ktoré majú príslušný počet vrcholov a hrán. Bod získava ten, kto ako prvý doplní do niektorého prázdneho políčka nejaký konvexný polyéder s príslušným počtom vrcholov a hrán, prípadne ak dokáže, že pre kombináciu v a e (spomedzi tých kombinácií, ktoré sú na obrázku) neexistuje žiadny konvexný polyéder s počtom vrcholov v a počtom hrán e.

Pochopiteľne, výhodu má ten, kto sa do riešenia pustí ako prvý, pretože neskôr sa budú hľadať príslušné telesá alebo dôkazy ťažšie. Nájdené telesá môžete popísať slovne (napríklad ako ich možno dostať z iných telies) v komentári k tomuto príspevku, alebo mi môžete poslať načrtnutý obrázok mailom. Pokúste sa riešiť daný problém vlastnými silami. Nikomu by nepomohlo, ak by ste vypátrali kompletné riešenie niekde na internete a potom sa ním tu prezentovali.

17.8.: Štyri polyédre doplnila Hugo.
18.8.: Ďalších päť polyédrov doplnila Hugo.
19.8.: Ešte ďalších päť polyédrov doplnila Hugo.
20.8.: Peťo ukázal nemožnosť konštrukcie 17-tich polyédrov.
20.8.: Posledné okienko zaplnila Hugo.

Ako Dumbledore udeľujem ešte 1 bod navyše pre Huga(u?) za pozitívne výsledky a Peťovi -1 bod za negatívne výsledky, čiže celkový výsledok zápasu Hugo-Peťo je 16:16. :-)

15 komentárov:

Anonymný povedal(a)...

no dobre, tak najprv tie najprimitivnejsie, aby sa to trochu rozbehlo :-) [a este preto, ze dalsie body uz mozno nenazbieram :-)]:
5,9 ziskame zlepenim dvoch 4,6; podobne 6,12 vznikne z 5,8; 7,15 zo 6,10. nuz a 9,16 mozme doplnit na motivy 8,14...

Radoslav Harman povedal(a)...

Pozliepať niektoré telesá dokopy je veľmi dobrý nápad. Zakreslil som ich do obrázku. Keďže Ťa nechcem nazvať "anonym", dal som Ti meno Hugo :) Ak chceš mať inú prezívku, napíš.

Anonymný povedal(a)...

hugo vyhovuje. :-) a super, ze si zakreslil tie telesa do obrazku, tiez ma vcera po odoslani prispevku napadlo, ze by si to mohol takto interaktivne doplnat.:-)

Anonymný povedal(a)...

no a este na dobru noc ma napadlo dalsie lepenie: 6,11 ziskame zlepenim 5,8 a 4,6; 7,13 ziskame zlepenim 6,9 a 5,8; 7,14 dostaneme spojenim 5,8 a dvoch 4,6; a 8,15 vznikne zo 6,9 a dvoch 4,6. teda, ak som sa nesekla. (hugo)

Anonymný povedal(a)...

aha, a este 8,16 zo 6,10 a dvoch 4,6 (hugo)

Radoslav Harman povedal(a)...

OK, Hugo. Veľmi dobre. Vidím, že lepenie je naozaj účinná metóda (ja sám som pri dopĺňaní tej tabuľky využíval inú všeobecnú metódu.) Ochvíľu sa nám zaplnia všetky okienka, kde príslušný polyéder existuje a potom už príde na rad len dokazovanie neexistencie :-)

V priebehu dneška si opäť nájdem čas a Tvoje objavy zakreslím do obrázku.

Anonymný povedal(a)...

no, vyzera to, ze som jedina, ktoru tato uloha chytila za srdce :-). tak skusim este pridat dalsich par telies: tentokrat to bude radikalnejsie: rezanim.:-) zacnem s kockou. a aby to bolo jasne, tak jej lavy dolny predny roh umiestnime do bodu [0,0,0], pravy predny dolny do [1,0,0], lavy zadny dolny do [0,1,0] a lavy predny horny do [0,0,1]. 8,13 by sme mali dostat, ked spravime rez cez [0,0,1],[0,1,0], [1/2,0,0];
9,14 : rez cez [1/2,0,0],[0,0,1/2],[0,1,0];
9,15: 9,14 + rez cez [1/2,0,0],[1,1,0],[1,0,1/2];
10,15: rez [1/2,0,0],[0,1/2,0],[0,0,1/2]; 10,16: 9,14 + rez [1,0,1],[1/2,1,1],[1,1,1/2]
teda, dufam, ze som trafila(hugo)

Radoslav Harman povedal(a)...

Nakreslil som si Tvoje telesá a naozaj udávaný počet hrán a vrcholov súhlasí. Výborne. (Do obrázku ich zakreslím zajtra.)

Najviac sa mi páči to teleso 10,16, pretože je tak pekne symetrické (na rozdiel od toho telesa 10,16, ktoré som si našiel ja).

Možno by bolo zaujímavé pre každú dvojicu v,e nájsť nielen "nejaký" polyéder s v vrcholmi a e hranami, ale ten, ktorý má najväčší možný počet symetrií. (T.j. pre ktorý má grupa symetrií čo najviac prvkov.)

Ešte dám pomôcku: už sa dá nájsť iba jeden ďalší polyéder; o ostatných kombináciách v,e sa dá ukázať (a to jednoducho), že polyéder s príslušným počtom vrcholov a hrán neexistuje. (Samozrejme hovorím o dvojiciach v,e na našom obrázku.)

Peter Richtárik povedal(a)...

Ahojte Hugo a Rado. Pridavam sa do hry. Pre zaciatok:

(5,10); (6,13); (6,14); (6,15); (7,16) nefunguju.

Tu je vysvetlenie:

V prvom rade, podla Eulerovej vety pre konvexne mnohosteny je

V - H + S = 2, kde

V = pocet vrcholov
H = pocet hran, a
S = pocet stien.

Kazda stena ma aspon 3 hrany, a teda pocet hran je aspon 3S/2 kedze kazda je zapocitana pocitanim 'cez steny' prave dvakrat.

Pre vsetky zostavajuce pripady teda skontrolujeme ci
H >= 3*(2 + H - V)/2.

Toto neplati pre vyssie uvedene pripady.

Peter Richtárik povedal(a)...

Ostatne zvysne pripady okrem (7,11) tiez nefunguju. Dovod:

Z kazdeho vrchola vidime aspon 3 hrany, teda pocitanim hran 'cez vrcholy' je jasne, ze by malo platit

H >= 3*V/2

(kazdu totiz takto pocitame dvakrat).

Tuto podmienku zasa nesplnaju vsetky ostatne pripady okrem (7,11).

Radoslav Harman povedal(a)...

Peter: Presne tak. Idem kresliť.

(Ak sa Peter nenahneváš, vynechám z estetických dôvodov posledný "prázdny" riadok, čím Ťa ukrátim o 4 body...)

Ako som prezradli, polyéder 7,11 existuje. Ak ho nájdete, máme posledný diel nášho puzzle.

Anonymný povedal(a)...

o ka. kedze existujuce polyedre vyzeraju byt mojou domenou :-), tak 7, 11 ziskame zo 6,9 (tak, ako je zobrazeny na obrazku) odrezanim praveho horneho rohu, pricom rez pojde cez pravy dolny vrchol (ale uz ziaden iny dalsi vrchol). dufam, ze sa tento popis da pochopit... (hugo)

Peter Richtárik povedal(a)...

Rado: Nenahnevam, bolo by to prilis vela much jednou, teda dvoma, ranami.

Uz len poznamenam, ze si zasa vymyslel peknu zabavku a ze s Hugom sme sa tu na Tvojom blogu celkom pekne zabavili ;-)

Co sa Tyka 'vyhry', tak podla mna je to 50%-50%, Hugo si zahral Vishnu stvoritela a ja Sivu nicitela ;-)

Radoslav Harman povedal(a)...

Hugo: OK. Aj tak sa dá, hoci ja som si našiel iný polyéder 7,11. No, škoda, prehrala si s Peťom (ktorý je zasa špecialista na neexistujúce polyédre) veľmi tesne, ale je to tak trochu moja chyba. Mal som to vyštelovať tak, aby bol rovnaký počet okienok s existujúcimi ako neexistujúcimi polyédrami.

Ale inak sa mi to celkom páčilo. Možno túto úlohu niekedy niekto ešte využije ako inšpiráciu, napríklad na nejakom sústredení mladých matematických olympionikov, alebo korešpondenčných seminaristov :)

Peter Richtárik povedal(a)...

Ked sa pozeram na ten vysledny obrazok, tak mi napadla otazka ci existuje par (V,H) taky, ze

a) (V,H) a (V,H+2) 'funguju' a (V,H+1) nie,

alebo

b) (V,H) a (V+2,H) 'funguju' a (V+1,H) nie.

Odpoved neviem, ale potesim sa ked na to niekto z citatelov Tvojho blogu pride ;-)

Co sa Tyka knizky, nedbam!

Samozrejme, ja by som musel poriadne sliapnut na plyn s vymyslanim uloh, kedze vacsina mojich je prebrata z kniziek. Ale vyzera to, ze si ma zatial 'nakazil' (read: inspiroval) a je to celkom sranda.