La situació és la següent: tenim un conjunt d'illes iguals de cases, posem-ne com les de l'Eixample de Barcelona. En la situació d'exemple tenim un rectangle de 4x7 illes. Si col·loquem un vigilant a una cruïlla només pot observar els carrers que s'hi troben a la cruïlla i el seu abast visual és de la longitud d'una illa, és a dir, fins a la cruïlla següent (a l'Eixample serien 100 m). Quin és el nombre mínim de vigilants que calen per controlar tots els carrers?
Pots practicar amb aquest applet enllaçat clicant sobre els botons que hi ha a les cruïlles.
Enllaç a l'applet (flash) |
Si observes la solució mínima (que imaginem que hauràs obtingut sense dificultats especials o, si més no després de no masses proves) veuràs que la distribució dels vigilants segueix un patró força regular. La investigació que proposem és justament aquesta: es pot saber la quantitat mínima de vigilants, sense distribuir-los, coneixent quantes illes té cada costat del rectangle.
T'animes a investigar?
T'animes a investigar?