Problem K. 217. (October 2009)

K. 217. Three kinds of bombs can be placed on a squared playing field. When a bomb explodes, it will destroy its own cell and the cells around, including the contents of those cells. The diagram shows the ranges of the three types of bombs. (The numbers indicate the location and type of the bomb.) If a cell destroyed by a bomb contains another bomb, that bomb will also explode, together with all cells in its range. Place 2 of each kind of bomb on the squared field so that the largest possible number of cells are destroyed if any of the bombs is exploded.

(6 pont)

Deadline expired on November 10, 2009.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. A bombák hatósugarába eső területek átfedik egymást, ha láncreakció szerint szeretnénk felrobbantani őket. A közös mezők számát az alábbi táblázatban foglaljuk össze. A táblázat nem szimmetrikus, ha nem kölcsönösen robbantják fel egymást a bombák. Ebben az esetben a sorokban az először felrobbanó (ok), az oszlopokban az általuk felrobbantott bombatípusok vannak. A második táblázatban az egymást kölcsönösen felrobbantó bombák közös mezőinek minimális száma szerepel.

Mivel egy bomba felrobbantása újabb mezők, vagy újabb bomba felrobbantását jelenti, célunk az összes bomba felrobbantása. Legyen az \(\displaystyle i.\) bomba és az általa felrobbantott mezők területe összesen \(\displaystyle t_i\), az \(\displaystyle i.\) és \(\displaystyle j.\) bomba által közösen lefedett (felrobbantott) terület \(\displaystyle k_{ij}\). Ekkor együtt \(\displaystyle t_i+t_j-k_{ij}\) mezőt robbantanak fel. Ha ezek együtt felrobbantják az \(\displaystyle m.\) bombát, akkor a bombák alakja miatt biztos, hogy az \(\displaystyle i.\) és a \(\displaystyle j.\) küzül kiválasztható az egyik, mellyel az \(\displaystyle m.\) közös hatóterülettel rendelkezik és a másik -a közös területen kívülivel- nem. Ha ez az \(\displaystyle i.\), akkor a három közösen felrobbantott területe \(\displaystyle t_i+t_j-k_{ij}+t_m-k_{im}\), és így tovább. Tehát a felrobbantott terület a bombák összterületének az átfedésekkel való csökkentésével számolható. A bombák összesen külön-külön \(\displaystyle 2(5+9+13)=54\) mezőt fednek le. A kölcsönös felrobbantáshoz kell egy láncot találni, és a célunk, hogy ez lánc a legkisebb összátfedést adja.

A cél tehát, hogy a lánc-robbanások által minél kevesebb legyen a közös hatóterület. Minden bombának fel kell robbania, tehát valamelyik bomba okozza a másik robbanását (az elsőt kivéve): a táblázatban keressük azon öt számot, melyek összege a legkisebb, és egy oszlopból legfeljebb kettőt választhatunk. Ezen számok a \(\displaystyle 2, 2, 4, 4, 5\), összegük \(\displaystyle 17\). Az összesen felrobbantott terület \(\displaystyle 54-17=\mathbf{37}\). A táblázatbeli mezők kiválasztásával a bombák egymás után sorba fűzhetőek.

Megjegyzés: Ha bármelyik bomba felrobbantásával elpusztított mezők maximális számát keressük, akkor a következőt tehetjük. A második táblázat alapján az azonos típusú bombák robbantják fel egymást a legkevesebb átfedéssel, továbbá mivel az 1 és 2 átfedés kisebb mint 1 és 3-as, a legnagyobb pedig a 2 és 3-as, ezért a következő lánc lesz az optimális: \(\displaystyle 3a - 3b - 1a - 1b - 2a - 2b\), az összes átfedés pedig \(\displaystyle 5+5+2+4+4=20\), tehát a felrobbantott mezők száma \(\displaystyle 34\).

Statistics:

240 students sent a solution.
6 points:	67 students.
5 points:	12 students.
4 points:	10 students.
3 points:	9 students.
2 points:	13 students.
1 point:	51 students.
0 point:	63 students.
Unfair, not evaluated:	15 solutionss.

Problems in Mathematics of KöMaL, October 2009