Problem

Source: Mexico National Olympiad 2018 Problem 2

Tags: combinatorics, rectangle, covering



For each positive integer $m$, we define $L_m$ as the figure that is obtained by overlapping two $1 \times m$ and $m \times 1$ rectangles in such a way that they coincide at the $1 \times 1$ square at their ends, as shown in the figure. [asy][asy] pair h = (1, 0), v = (0, 1), o = (0, 0); for(int i = 1; i < 5; ++i) { o = (i*i/2 + i, 0); draw(o -- o + i*v -- o + i*v + h -- o + h + v -- o + i*h + v -- o + i*h -- cycle); string s = "$L_" + (string)(i) + "$"; label(s, o + ((i / 2), -1)); for(int j = 1; j < i; ++j) { draw(o + j*v -- o + j*v + h); draw(o + j*h -- o + j*h + v); } } label("...", (18, 0.5)); [/asy][/asy] Using some figures $L_{m_1}, L_{m_2}, \dots, L_{m_k}$, we cover an $n \times n$ board completely, in such a way that the edges of the figure coincide with lines in the board. Among all possible coverings of the board, find the minimal possible value of $m_1 + m_2 + \dots + m_k$. Note: In covering the board, the figures may be rotated or reflected, and they may overlap or not be completely contained within the board.