AoPS - Problem

Source: Czech - Polish - Slovak Match 2013: P5

Tags: geometry, perimeter, inequalities, combinatorics unsolved, combinatorics

Sayan

29.05.2014 04:47

Triangular grid divides an equilateral triangle with sides of length $n$ into $n^2$ triangular cells as shown in figure for $n=12$. Some cells are infected. A cell that is not yet infected, ia infected when it shares adjacent sides with at least two already infected cells. Specify for $n=12$, the least number of infected cells at the start in which it is possible that over time they will infected all the cells of the original triangle. [asy][asy] unitsize(0.25cm); path p=polygon(3); for(int m=0; m<=11;++m){ for(int n=0 ; n<= 11-m; ++n){ draw(shift((n+0.5*m)*sqrt(3),1.5*m)*p); } } [/asy][/asy]

The number is 45. This is optimal because the sum (the number of infected cells + the total perimeter of the infected area) never increases when the infection spreads. At the end, we want 144 infected cells with perimeter 36, so the sum is 180. If at the start we have $n$ infected cells, the total perimeter is at most $3n$, so the sum is at most $4n$, and \[4n \geq 180 \Longrightarrow n \geq 45.\] A construction is easy to motivate --- all we need to make sure is the above inequality is tight and our chosen sum never goes down, which holds if no two initial triangles are adjacent and it is never true during the process that three infected triangles surround an uninfected one. I don't have an extremely neat one, though. Here's a picture: