Problem

Source: Baltic Way 2013, Problem 10

Tags: combinatorics



A white equilateral triangle is split into $n^2$ equal smaller triangles by lines that are parallel to the sides of the triangle. Denote a line of triangles to be all triangles that are placed between two adjacent parallel lines that forms the grid. In particular, a triangle in a corner is also considered to be a line of triangles. We are to paint all triangles black by a sequence of operations of the following kind: choose a line of triangles that contains at least one white triangle and paint this line black (a possible situation with $n=6$ after four operations is shown in Figure 1; arrows show possible next operations in this situation). Find the smallest and largest possible number of operations.


Attachments: