Mravce na tyči (súťažná úloha č.10)

Desiatu súťažnú úlohu nám poslal Peťo Richtárik; pekné je na nej to, že riešenie môže napadnúť aj žiačika na základnej škole, no nemusí napadnúť ani profesora na univerzite. (Úloha má neznámy pôvod; Peťo sa ju dozvedel od kolegu.)


Na tyč dĺžky 10 metrov sme súčasne rozmiestnili 100 mravcov. Každý mravec sa pohybuje vpred rýchlosťou 1 meter za minútu. Ak dôjde mravec na niektorý z dvoch koncov tyče tak z nej spadne, avšak ak sa dva mravce zrazia, tak sa oba v okamihu otočia a pokračujú svojim konštantným tempom v opačnom smere. Otázka znie: Vedeli by ste určiť po akom čase spadne z tyče posledný mravec v závislosti od počiatočného smeru pohybu a umiestnenia mravcov?

Poznámka 1: Mravce považujeme za "body", t.j. akoby mali nulovú dĺžku. Tyč nemá žiadnu šírku (považujeme ju za idealizovanú úsečku), t.j. proti sebe idúce mravce sa nemôžu obísť, ale nutne sa musia po čase zraziť.

Poznámka 2: Predpokladáme, že na začiatku je každý mravec v inom bode tyče.

Mount & Blade (Súťažná úloha č.9)

Mount and Blade je názov počítačovej hry a súčasne 9. úlohy do našej súťaže, ktorú nám zaslal doktorand na matematickom ústave SAV Branislav Novotný. (To by človek nepovedal, čím všetkým sa Braňo ešte zaoberá okrem matematickej topológie a vyparovania čiernych dier :-)

Táto úloha je síce pomerne jednoduchá, ale pekné na nej je to, že je to úplne reálny problém, ktorý možno trápi viacerých hráčov hry Mount&Blade. Nie som si však vedomý toho, že by ju už niekto v nasledovnom znení formuloval.

Pri hraní M&B hráte za hrdinu, ktorý môže mať v partii okrem bežných vojakov aj tzv. hrdinov, ktorí sú mimo iného nesmrteľní ( hrdinovia predsa neumierajú :-), teda sa ich oplatí mať v partii čo najviac. Ich základným problémom však je, že majú medzi sebou spory a dokážu sa tak pohádať, že opustia partiu. Nasleduje tabuľka mien (ženy majú hviezdičku, lebo z mena je to ťažko poznať) a zoznam kto koho má, či nemá rád.


Ľahko si všimneme, že všetky vzťahy sú vzájomné. Definujme konflikt ako dvojicu, čo sa nemá rada a priateľstvo ako dvojicu čo sa má rada. Povedzme, že parta je maximálna, ak za daných podmienok má maximálny počet členov a medzi partiami s max. počtom členov má max. počet priateľstiev. Povedzme, že partia je bezkonfliktná, ak neobsahuje konflikt. Nech je udržateľná ak ľubovoľný člen je účastníkom najviac takého počtu konfliktov ako priateľstiev.

Treba nájsť všetky:
a) maximálne bezkonfliktné partie,
b) maximálne udržateľné partie,
c) maximálne udržateľné partie obsahujúce všetky ženy.

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.

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? ;-)

Slnečné kolektory

Náš vesmírny koráb stroskotal na púštnej planéte X a to práve na takom mieste, na ktorom je neustále jasno a (tamojšie) slnko sa celý (tamojší) deň pohybuje tesne nad obzorom. K dispozícii máme 4 rovnaké slnečné kolektory širky 1 meter, ktoré z technických dôvodov musíme umiestniť všetky v rovnakej výške a naviac tak, aby osi týchto kolektorov boli na hranici, alebo vo vnútri štvorca 2 krát 2 metre. Po inštalácii sa budú kolektory otáčať za slnkom okolo svojej osi, no samotné osi už musia byť nehybné.

Nanešťastie, na vyslanie signálu SOS potrebujeme trvale dostatočne vysoký výkon kolektorov, ktorý dosiahneme len vtedy, keď počas celého dňa bude dopadať svetlo aspoň na 2,61 metra šírky kolektorov. To znamená, že štandardné postavenie kolektorov zobrazené na ilustračnom obrázku je nevyhovujúce, pretože dokonca až štyrikrát počas dňa si kolektory navzájom príliš tienia a svetlo dopadá spolu len na 2 metre šírky kolektorov.

Dá sa vôbec nájsť také rozmiestnenie kolektorov, aby sa trvale dosahoval požadovaný výkon?

Prechádzka po mriežke

Do ukončenia našej súťaže chýba ešte 5 úloh. Neváhajte poslať aj niečo jednoduchšie (najmä vlastných nápadov tu zatiaľ veľa nemáme); napríklad také, ako je úloha, ktorá ma napadla dnes:

Máme pravouhlú mriežku zostavenú z n × m úsečiek, kde n aj m sú nepárne čísla. Ukážte, že nie je možné po nej prejsť všetkými uzlovými bodmi tak, aby sme každý z nich navštívili práve raz a nakoniec sa vrátili do toho uzlového bodu, v ktorom sme začali. T.j. chceme dokázať, že v príslušnom grafe neexistuje hamiltonovská kružnica.

Jeden neúspešný pokus o uzavretú hamiltonovskú prechádzku na mriežke 5 × 5 je znázornený na ilustračnom obrázku vľavo hore.

Poznámka 6.1.: V komentári nám misof formuloval zaujímavú úlohu s trochu podobným námetom (aj keď ťažšiu); neprehliadnite!

Všetky uhly sú rovnaké (súťažná úloha č.7)

Prvý tohtoročný príspevok na blog QED a súčasne siedmu úlohu do našej súťaže napísal Mišo 'mišof' Forišek. Táto úloha je, ako píše Michal, "matematický folklór" a autor nie je známy.

Ak by ste to nevedeli, všetky uhly sú rovnaké a matematika nefunguje. Aby sme si to dokázali, ukážeme, že 90° uhol je rovnako veľký ako 100°. Začneme tým, že si zostrojíme štvorec ABCD. Teraz zvolíme bod E mimo štvorca tak, aby mal uhol DAE 10 stupňov a aby platilo |AE|=|AB|. Teraz zostrojíme osi úsečiek AB a CE, nazveme ich p a q. Tie sa zjavne pretínajú, ich priesečník označíme F.

Celá situácia vyzerá nasledovne:


Všimnime si teraz trojuholníky FAE a FBC. Zjavne platí |FA|=|FB|, lebo F leží na osi AB. Tiež zjavne platí |FC|=|FE|, lebo F leží na osi CE. No a platí aj |AE|=|BC|, lebo E sme zvolili tak, aby jeho vzdialenosť od A bola rovná strane štvorca. Teda podľa "vety SSS" sú tieto dva trojuholníky zhodné.

Keďže sú trojuholníky FAE a FBC zhodné, sú uhly FAE a FBC rovnaké. Pre veľkosti uhlov FAE a FBC platí: |∠FAE|=|∠FAB|+100, |∠FBC|=|∠FBA|+90. Keďže |∠FAE|=|∠FBC|, tak |∠FAB|+100°=|∠FBA|+90°.

Lenže, ako sme už povedali, |FA|=|FB|, a teda trojuholník FAB je rovnoramenný. Potom ale |∠FAB|=|∠FBA|, a preto 100°=90°, q.e.d.

Kde, ak vôbec niekde, je chyba?