[ Tiling with domino bones and tiles ] ..... ]
[ Examples and counterexamples. Constructions ]

On a grid sheet of size 100×100, several pairwise 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.
Let $n=50$. We will call a triangle upper if it is located above the line containing its horizontal leg, and lower otherwise. We will number the horizontal lines of the grid from bottom to top with numbers from 0 to $2n$.

Estimate. Let $u_{k}$ (respectively $d_{k}$) be 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 $(n+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)$. Example. The figure 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, the cells of the rectangle 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".

![](https://cdn.mathpix.com/cropped/2024_05_06_7b30f89ee421e63350f8g-27.jpg?height=343&width=346&top_left_y=1212&top_left_x=862)

## Answer

$49 \cdot 50 = 2450$ cells.