Tanec molekúl

Keď som na Akadémii Trojstenu spomínal súvis Gaussovej krivky a objemov rezov mnohorozmerných kociek, napadlo ma, že by som rád vedel ako asi vyzerá "typická" množina ich vrcholov v dvojrozmernej projekcii. Včera večer som si teda v rámci oddychu napísal jednoduchý program, ktorý zobrazuje dvojrozmerné súradnice vrcholov pomaly rotujúcej mnohorozmernej kocky s farbami určenými súradnicami v ďalších troch rozmeroch.

Najprv som si myslel, že pre Vás vyrobím pomocou môjho programíku video, ale to by bolo nutne krátke. Rozhodol som sa preto dať Vám k dispozícii priamo zdrojový kód programu; stačí, keď si ho prekopírujete do R-ka a spustíte. Takto sa s ním môžete zabávať, vylepšiť ho podľa vlastných predstáv.

Ako navigovať robota II

Predchádzajúca úloha sa ukázala byť celkom úspešná; viacerí z Vás našli pekné riešenia logickou úvahou a Rori dokonca našiel riešenie optimálne v tom zmysle, že je najkratšie možné. Pomocou peknej myšlienky Rori tiež vygeneroval množstvo "ťažkých" diagramov, ktoré som si trochu poprezeral a jeden z nich som modifikoval do nasledovnej podoby:

Tak ako v predchádzajúcej úlohe, cieľom je nájsť postupnosť príkazov M/C, ktorá dovedie robota do miestnosti A z akejkoľvek inej* miestnosti.


Kto nájde optimálne riešenie len v hlave, je génius. A kto nájde riešenie pomocou počítača, je schopný programátor. Možno keby som bol zamestnávateľ a chcel by som zistiť, či vie niekto naozaj programovať a algoritmicky myslieť (čo si dnes o sebe myslí skoro každý), tak by som mu dal počítač a požiadal ho, nech mi do hodiny povie riešenie tejto úlohy :-)

* Pôvodne som formuloval úlohu so slovom "inej" a takáto úloha je zmysluplná a tiež pomerne obtiažna, pričom ju vyriešil Nanyk (pozri komentáre). Pôvodný zámer bol však taký, že dané riešenie musí dostať robota do miestnosti A aj ak ten robot začína v priamo v A. Pri riešení tohto pôvodne zamýšľaného problému sa však možno dajú Nanykove myšlienky použiť ...

Slnečné kolektory: riešenie

Problém "slnečné kolektory", ktorý som pre Vás vymyslel pred pár dňami, sa so silným ohlasom veru nestretol. Nuž, čím bližšie majú úlohy k praktickým aplikáciám, tým je obvykle ťažšie vyriešiť ich len pomocou dôvtipu; nie sú to už tie elegantné matematické hlavolamy z Gardnerovych kníh. Hľadanie riešenia "inžinierskych" úloh však má tiež svoje čaro a práve o tom by som Vás chcel tak trochu presvedčiť v tomto príspevku. Takže ako riešiť úlohu o optimálnej konfigurácii kolektorov?

Je zrejmé, že prvoradou úlohou je vedieť pre zadanú konfiguráciu a pre zadaný smer lúčov slnka vypočítať úhrnnú šírku kolektorov, na ktorú dopadá svetlo, t.j. veľkosť tieňa, ktorý by vrhala sústava štyroch kruhov s priemermi 1 meter a so stredmi v osiach kolektorov:


Napísať analytický predpis pre veľkosť tieňa v závislosti od polohy slnka je veľmi ťažké, avšak programík (napríklad pre prostredie R) na numerický výpočet je raz dva (procedúry, ako tá nasledujúca, môžete úplne kľudne preskočiť; sú tu len pre tých, ktorí by chceli vedieť podrobnosti):

shadow<-function (x,b){
# x ... uhol smeru kolmeho slnecne luce
# b ... suradnice osi v poradi x1,x2,x3,x4,y1,y2,y3,y4
h<-b[1:4]*cos(x)+b[5:8]*sin(x)
h<-sort(h); L<-h[4]-h[1]+1
for(i in 2:4) if(h[i]-h[i-1]>1){L<-L-(h[i]-h[i-1]-1)}
L }

Minimálnu veľkosť tieňa počas dňa potom určíme pomocou jednorozmernej minimalizačnej procedúry, ktorú nám poskytuje používaný software; v prípade programu R je to funkcia optimize. Treba si dať samozrejme pozor na to, že naša minimalizovaná funkcia môže obsahovať lokálne minimá; lepšie je preto rozbiť množinu smerov na viacero podintervalov, napríklad takto:

minshadow<-function b="" br=""># b ... suradnice osi v poradi x1,x2,x3,x4,y1,y2,y3,y4
 s<-seq(0,pi,length=11); res<-rep(Inf,10)
 for(i in 1:10){
  res[i]<-optimize(f=shadow,interval=c(s[i],s[i+1]),b=b)$objective}
 -min(res) }

Teraz už máme program, ktorým môžeme testovať "podozrivé" konfigurácie. Napríklad ak odskúšame konfiguráciu, ktorú navrhol Lev v komentári k predošlému príspevku, t.j. takú, v ktorej osi kolektorov ležia vo vrcholoch a v ťažisku najväčšieho rovnostranného trojuholníka, ktorý sa daného štvorca zmestí, dostaneme hodnotu minimálneho tieňa približne 2598 mm.

Je Levova konfigurácia optimálna? Aby som zodpovedal túto otázku, urobil som si krátky programík na maximalizáciu samotnej funkcie minshadow, ktorý je v zásade genetický algoritmus bez rekombinácie, čiže jednotlivé konfigurácie, čoby "jedinci populácie", produkujú potomkov "asexuálne", výlučne náhodnými mutáciami svojich vlastných polôh osí, aka "chromozómov". Všimnite si, aký je tento program doslova triviálny:

function(k,s,N) {
# k ... velkost populacie (volil som 500)
# s ... inicialna velkost mutacii (0.4)
# N ... pocet generacii (35)
 cents.mut<-cents k="" matrix="" ncol="k,nrow=8)<br" runif=""> vals<-rep br="" k=""> for(i in 1:N){
  for(j in 1:k){vals[j]<-minshadow br="" cents="" j="">  o<-order br="" cents="" o="" vals="">  for(r in 1:k){
   cents.mut[,r]<-pmax cents="" k="" pmin="" prob="(k:1)^5)]<br" sample="">     +(s/i)*rnorm(8),1),-1)}
  cents<-cents .mut="" br="">}

Polohy osí jednotlivých konfigurácií kolektorov som nechal vykreslovať červenými bodkami a spojnice medzi osami jednotlivých konfigurácií modrými spojnicami. Najlepšiu konfiguráciu v každej generácii som vyznačil čiernymi spojnicami a celý priebeh "vývoja" som zachytil na nasledovnom videu:



Iniciálna populácia je vygenerovaná úplne náhodne (rovnomerne na celom štvorci). Po úvodnej fáze divokého experimentovania sa vytvoria zhluky chromozómov podieľajúcich sa na "úspešných" konfiguráciách. Neskôr sa vytvoria oddelené "subpopulácie", z ktorých predposledná úplne vymizne až v 26. generácii. Ako vidíme, výsledná konfigurácia pôsobí akoby bola navrhnutá "inteligentne" a naviac je dostatočná na splnenie zadania našej pôvodnej úlohy; jej minimálna veľkosť je 2617 mm.

Všimnime si výslednú konfiguráciu bližšie. Tri body, označme si ich A,B,C, ležia veľmi blízko pri okraji štvorca a štvrtý bod, D, niekde vo vnútri. Ak by bola optimálna poloha bodu A presne (-1,-1), bodu B presne (1,0) a bodu C presne (-1,1), aká bude optimálna poloha bodu D? Netreba dlho uvažovať, kým si človek uvedomí, že minimálna veľkosť tieňa bude maximalizovaná vtedy, keď vzdialenosť bodu D od všetkých troch strán trojuholníka ABC bude rovnaká. To znamená, že bod D bude stredom do ABC vpísanej kružnice. Je už záležitosťou elementárnej matematiky dopočítať presnú polohu bodu D a výslednú hodnotu d minimálnej veľkosti tieňa:


Pochopiteľne, všetky štyri "rotácie" tohto riešenia sú takisto optimálne. Ak Vás tento problém zaujal, môžete sa ešte pokúsiť zodpovedať nasledovnú otázku: Existuje aj optimálna konfigurácia, ktorá nie je len rotáciou tej našej? ;-)

Prieskumná expedícia (súťažná úloha č.5)

Piatu súťažnú úlohu nám poslal Mišo 'mišof' Forišek, doktorand na FMFI UK.

Na štvorcovej mriežke žije národ panákov. Doteraz obývali polrovinu pod osou x. No teraz kráľ rozhodol, že vyšle zvedov, aby zistili, ako to vyzerá nad osou x.

Na začiatku expedície sa všetci zvedi rozostavia po kráľovstve, teda na navzájom rôzne políčka pod osou x. Následne začne expedícia. Počas expedície sa v každom kroku pohne práve jeden zved. Zvedi sa môžu pohybovať ako kamene v solitéri: Ak má zved v jednom zo 4 hlavných smerov pred sebou iného zveda a za ním voľné políčko, môže ho preskočiť. Preskočený zved už v expedícii nepokračuje.

Príklad povoleného ťahu.

Ľahko zistíme, že na to, aby sme dostali zveda do prvého riadku neznámeho územia, potrebujeme na začiatku zvedov aspoň dvoch, a na dosiahnutie druhého riadku treba zvedov aspoň štyroch:

Optimálne riešenia pre prvý a druhý riadok. V riešení vpravo si všimnite, že v okamihu, kedy najpravejší zved robí skok označený poradovým číslom 2, je už jeho cieľové políčko voľné.

Rozcvička číslo 1. Nájdite optimálne riešenie pre tretí riadok. Prezradíme, že stačí 8 zvedov. (Komu sa fakt nechce, tu nájde jedno možné riešenie. Ale odporúčame pohrať sa, nie je to ťažké.)

Po číslach 2, 4 a 8 je každému jasné, koľko zvedov treba na dosiahnutie štvrtého riadku, že? Až na to, že nemáte pravdu, lebo správny počet je 20.

Rozcvička číslo 2. Nájdite čo najlepšie riešenie pre štvrtý riadok a pochváľte sa v diskusii pod článkom.

No a už sme pri pointe: Použite svoju matematickú intuíciu a tipnite si, koľko najmenej zvedov treba na to, aby sa jeden z nich dostal až do piateho riadku neznámeho územia. A potom skúste nejaké, čo najlepšie riešenie zostrojiť.

Ak sa vzdáte a úlohu nevyriešite, tu je riešenie prezrádzajúce pointu.

(Zdroj: Berlekamp, E. R.; Conway, J. H; and Guy, R. K. "The Solitaire Army.")

Chaotický trojfarebný trojuholník

Chaotickým k-farebným trojuholníkom veľkosti n nazvime trojuholník poskladaný z 1+2+...+n kameňov k farieb, ktorý neobsahuje žiadnu trojicu kameňov rovnakej farby umiestnených vo vrcholoch trojuholníka so stranami rovnobežnými so základným trojuholníkom.

Formulujeme si jednu teoretickú úlohu a jednu súťaž pre všetkých, ktorí si myslia, že sú programátorskí machri.

Úloha: Dokážte, že existuje najväčší trojfarebný chaotický trojuholník. Inými slovami, ukážte, že existuje prirodzené číslo n také, že trojfarebný chaotický trojuholník veľkosti n už principiálne nie je možné skonštruovať. Môžete použiť Peťove riešenie predchádzajúceho príkladu a Van der Waerdenovu vetu, na ktorú nás upozornil Nanyk.

Súťaž: Pomocou počítača nájdite trojfarebný chaotický trojuholník s veľkosťou aspoň 15, t.j. väčší ako ten, ktorý som našiel ja:


Nie som si úplne istý s tým, že existuje väčší trojfarebný chaotický trojuholník ako ten môj, ale považujem to za veľmi pravdepodobné. Môj trojuholník je totiž výsledkom krátkeho výpočtu jednoduchého programu v pomalom jazyku R. Každopádne ak sa do riešenia tejto úlohy pustíte, pošlite nám najväčší trojfarebný chaotický trojuholník aký nájdete.

28.8.: Mišo našiel chaotický trojfarebný trojuholník veľkosti 16! Tu je:


Kto Miša prekoná má môj obdiv! To už ale bude asi poriadne ťažké...

Disjunktné párovanie

S knihou sa nenudím ani počas niekoľkohodinového čakania a ak aj nemám knihu, nie je problém sa príjemne zabaviť - len tak v mysli. Minule ma počas dlhej cesty autom (samozrejme keď som nešoféroval!) napadla takáto úloha:

Predpokladajme, že v rovine máme párny počet bodov. Zdá sa intuitívne zrejmé, že tieto body môžeme pospájať úsečkami do dvojíc tak, aby sa žiadne dve z týchto úsečiek nepretínali. Vedeli by ste vymyslieť úplne jasný dôkaz, že to je naozaj tak? A vedeli by ste popísať nejaký efektívny algoritmus, ktorý také párovanie bodov nájde?

Najmenšia vzdialenosť dvoch bodov

V práci môjho bakalára sa vyskytol nasledovný okrajový, ale celkom zaujímavý algoritmický problém:

Vstupom je n vektorov x₁,...,x_n v m-rozmernom Euklidovskom priestore. Cieľom je zistiť Euklidovskú vzdialenosť dvoch najbližších bodov, t.j. vypočítať hodnotu

Otázkou je, či je možné skonštruovať asymptoticky rýchlejší algoritmus, než výpočet vzdialeností medzi všetkými n(n-1)/2 dvojicami rôznych bodov.

Poznámka: Sám neviem na tento problém odpovedať v plnej všeobecnosti (vlastne len pre m=1), takže neviem ani odhadnúť, aký je vo všeobecnosti náročný. Naviac, som si takmer istý, že tomuto jednoducho formulovanému problému sa už ľudia venovali, takže vyriešený už asi je. To nám však nebráni, aby sme sa nad ním zamysleli.