Library / /13 of 16

, 2013

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it Czech-Polish-Slovak Mathematical Match

Triangular lattice cuts an equilateral triangle with a side of length $n$ into $n^2$ triangular cells (Fig. 1). Some of the cells are infected. A cell, which is not infected yet, could be infected if it is neighbouring (by side) with at least two already infected cells. Determine the minimal amount of initially infected cells such that eventually every cell in the triangle could get infected if $n = 12$ .

Fig. 1

Solution

Notice, that with a contamination of one cell, the perimeter of infected area decreases at least by 1. Let $k$ cells be infected at the beginning. Then the perimeter is at most $3k$ . It takes $n^2 - k$ contaminations to get the whole triangle infected. The perimeter of the (infected) area is then $3n$ . Thus $3n \le 3k - (n^2 - k)$ , or
$k \ge \frac{n^2 + 3n}{4}.$
For $n = 12$ the estimate gives $k \ge 45$ . The layout of 45 initially infected cells which cause the infection of the whole system could be as illustrated on Fig. 4.

Another option is to cover the triangle with three equilateral triangles of side 4 (covering one side of the big triangle) and the rest could be covered with three rhombs of side 4 (Fig. 5). Each of the smaller triangles could be infected with 7 cells, each of the rhombs with 8 cells. Possible initial state for infecting an equilateral triangle with side 4 and a rhomb with side 4 is on Fig. 6a and Fig. 6b, respectively. (Each triangle with side 4 can get infected itself independently of the rest area. To get an entire rhomb infected, we need the area to its left and upper side to be infected first.)

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.