11.3. On a grid sheet of size $100 \times 100$, several non-overlapping cardboard isosceles right triangles with a leg of 1 were placed; each triangle occupies exactly half of one of the cells. It turned out that each unit segment of the grid (including boundary segments) is covered by exactly one leg of a triangle. Find the maximum possible number of cells that do not contain any triangle.

(D. Khramtsov)
Answer. $49 \cdot 50=2450$ cells

Solution. Let $n=50$. We will call a triangle upper if it is located above the line containing its horizontal leg, and lower otherwise. Number the horizontal lines of the grid from bottom to top with numbers from 0 to $2n$.

Denote by $u_{k}$ (respectively $d_{k}$) the number of segments on the $k$-th line that are part of upper (respectively lower) triangles; then $u_{k}+d_{k}=2n$ and $u_{0}=d_{2n}=2n$. Moreover, the vertical segments of the grid located between the $k$-th and $(k+1)$-th lines participate in exactly $u_{k}+d_{k+1}$ triangles, so $u_{k}+d_{k+1}=2n+1$. From this, it is not difficult to obtain that $d_{k}=k$ and $u_{k}=2n-k$ for all $k$.

Now consider the cells located between the $k$-th and $(k+1)$-th lines of the grid. At least $u_{k}=2n-k$ of these cells contain an upper triangle, and at least $d_{k+1}=k+1$ of them contain a lower triangle. Therefore, the number of free cells in this row is no more than $2n-\max(u_{k}, d_{k+1})$, which is no more than $k$ for $k<n$ and no more than $(2n-1)-k$ for $k \geq n$. In total, the number of free cells is no more than $2(0+1+\ldots+(n-1))=n(n-1)$.

It remains to provide an example where this estimate is achieved. Figure 7 shows an example for $n=4$. The example for $n=50$ is constructed similarly: a "rectangle" of cells with sides of $n+1$ and $n$ cells, parallel to the diagonals of the board, is highlighted, its cells are painted in a checkerboard pattern (so that the corner cells of the rectangle are black), and two triangles are placed in each black cell (thus, $n(n-1)$ white cells remain free); in the remaining four "corners" of the board, the triangles are placed so that the right angle of the triangle is directed in the same direction as the entire "corner".