CombinatoricsDifficulty 7.3National Olympiad, round 2Prove itCzech-Polish-Slovak Mathematical Match
Triangular lattice cuts an equilateral triangle with a side of length n into n2 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 n2−k contaminations to get the whole triangle infected. The perimeter of the (infected) area is then 3n. Thus 3n≤3k−(n2−k), or k≥4n2+3n. For n=12 the estimate gives k≥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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.