Problema saptamanii (solutie)

Cosmin Negruseri
16 februarie 2008

Am luat o pauza destul de lunga cu problema saptamanii. La ultima problema am primit doar doua solutii si am uitat de la cine (amintiti-mi si va trec ca rezolvitori). Gasiti textul aici .

Solutia problemei e destul de misto: Ne gandim la spatiul starilor problemei ca un patratul unitate din planul cartezian cu originea in (0, 0) si cu punctul diagonal opus in (1, 1). Abscisa unui punct din patratul acesta reprezinta pozitia normalizata pe intervalul [0, 1] a unui mobil sau un robot pe unul dintre cele doua drumuri de la A la B, iar ordonata punctului va reprezenta pozitia normalizata a celuilalt mobil respectiv robot pe al doilea drum de la A la B. Acum pentru ca ambele mobile pleaca din A si ajung in B, punctele asociate pozitiilor lor ne vor da o curba pornind din punctul (0, 0) si ajungand in punctul (1, 1). Iar punctele ce reprezinta miscarea celor doi roboti, care unul pleaca din A si ajunge in B si celalalt pleaca din B si ajunge in A, ne descriu o curba ce pleaca din punctul (0, 1) in (1, 0). Cele doua curbe trebuie sa se intersecteze si de aici rezulta ca orice doua drumuri am forma intre orasele A si B si orice itinerariu ar avea robotii, daca doua mobile pot ajunge de la A la B fiind legate cu o sfoara de lungime 10 m, atunci robotii nu pot ajunge unul din A in B si celalat din B in A fara sa se atinga.