Home › Archief › Internationale Olympiades › APMO › 2005 › brandweer

brandweer

Tags:

Opgave - APMO 2005 vraag 4

In een klein stadje zijn er $n\times n$ huizen, met index $(i,j)$ voor $1\leq i,j\leq n$ met $(1,1)$ het huis in de linkerbovenhoek, waar $i$ en $j$ respectievelijk de rij- en kolomindices zijn. Op het tijdstip 0 breekt er vuur uit in het huis met index $(1,c)$ met $c\leq\frac n2$. Tijdens ieder tijdsinterval $[t,t+1]$ verdedigt de brandweer een huis een huis dat nog niet in brand staat terwijl het vuur zich verspreidt naar alle onverdedigde buren van ieder huis dat in brand stond op tijdstip $t$ (een huis met index $(i,j)$ is een buur van huis met index $(k,l)$ als $|i-k|+|j-l|=1$). Eénmaal een huis verdedigd is, blijft het verdedigd gedurende de ganse tijd omwille van de vochtigheid. Het proces eindigt wanneer het vuur zich niet langer kan verspreiden. Wat is het maximum aantal huizen dat door de brandweer gered kan worden?