31 januára 2009

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.

6 komentárov:

katka povedal(a)...

Jej, toto je velmi pekna uloha. Pamatam si, ze som sa s nou uz stretla, ale nepamatala som si riesenie, teda vlastne som si ani nepamatala, ci som riesenie niekedy vedela. Pred chvilou som sa nad tym trochu zamyslela (popritom ako som zaspavala:)) a dostala som napad. Nechcem ho tu hned takto verejne prezradit, nech maju moznost aj ini na to prist, ale prezradim aspon dolnu a hornu hranicu. Vlastne dolna hranica ani neexistuje - ked povazujem mravcov len za body, tak ich mozem napchat lubovolne blizko k jednemu okraju a nasmerovat ich vsetkych smerom k nemu, a zachvilu vsetci popadaju. Horna hranica je podla mna 10 minut.

Charon ME povedal(a)...

ked som si zacal kreslit graf x=poloha mravcov y=cas tak som okamzite uvidel ze odrazenie sa protiiducich mravcov je ekvivalentne ich obideniu sa. takze zoberieme mravca ktory to ma na zaciatku najdalej od okraja v jeho zaciatocnom smere chodu a tuto vzialenost vydelime rychlostou. tymto som sa zrejme zaradil do kategorie prvacika :)

Brano povedal(a)...

ak by sme pridali cas zrazky 1s - teda tolko budu stat, kym sa nepohnu, tak aky bude stredny cas popadania vsetkych mravcov pri nahodnych (rozdelenie podla vkusu) zaciatocnych podmienkach?

Radoslav Harman povedal(a)...

Charon: Zaradil si sa do ketegórie bystrého prváčika. Lepšie ako kategória zaspatý profesor.

Inak nedá mi, aby som nenapísal riešenie, ktoré ako prvé napadlo mňa (hoci obvykle súťažné úlohy veľmi nekomentujem):

Predpokladajme, že každý mravec má na sebe tričko a keď sa dva mravce zrazia, v okamihu si svoje tričká vymenia. Takto sa bude každé tričko pohybovať rovnomerne rýchlosťou 1 meter za minútu len v jednom smere. Keďže každý mravec má stále na sebe nejaké tričko, tak posledný mravec spade práve vtedy, keď spadne posledné tričko. Z toho už plynie známe riešenie.

Braňo: Nápad na "znáhodnenie" tejto úlohy sa už vyskytol (aj so správnym riešením) medzi komentármi k tejto úlohe na pozri.sk.

Tvoja obmena s čakaním je však o dosť ťažšia. Riešenie ma v priebehu tých pár minút, čo som sa zamýšľal, nenapadlo.

Brano povedal(a)...

v skutocnosti znahodnenie je len taky vtip. kluc je v tom ako sa vysporiadat s cakanim. tak ako bez cakania pocitame pre kazdeho mravca cas k okraju, tak treba pripocitat pocet mravcov ktore maju na zaciatku opacny smer a stoja mu v ceste (tolko sekund) - na to treba este doriesit co sa stane pri kolizii troch, ale tam aby to vyslo, tak treba aby sa cakanie scitavalo. cize celkovy cas bude pre zadane podmienky
max{cas k okraju pre najpravsieho dolavaiduceho mravca + (pocet dopravaiducich mravcov pred nim)*1s, -naopak- }

pri znahodneni, by som povedal, ze kvoli jednoduchosti, by sa malo uvazit symetricke rozdelenie (x,v) teda pre rychlost Alt(0.5) a pre polohu napr R(.,.) potom by to uz nemalo byt tazke, len otrva (asi:-)

Brano povedal(a)...

inak ked som si pozeral tu ulohu, tak som bol v miestnosti doktorandov na teoretickej fyzike a prvy komentar z plena po precitani bol, "hm jednorozmerny plyn? to bude lahke"