1. let $n$ be a natural number. What is the maximum number of $1 \times 1$ squares that can be colored black in an $n \times n$ square, so that in every $2 \times 2$ square at most 2 small squares are colored black?

## Solution
- $\underline{n} \equiv 0 \bmod$ 2: This case is relatively simple: We cover the field with $2 \times 2$ cells. According to the prerequisite, each of these fields may have a maximum of 2 black fields. If we always color the bottom two fields black, we get a valid coloring:

![](https://cdn.mathpix.com/cropped/2024_04_28_2af68fe864fb49c618a9g-01.jpg?height=369&width=371&top_left_y=1226&top_left_x=366)

- $n \equiv 1 \bmod 2$ : Assertion: We can use at most

$$
n \cdot \frac{(n+1)}{2}
$$

Color fields black.

Construction: We color every second line black

![](https://cdn.mathpix.com/cropped/2024_04_28_2af68fe864fb49c618a9g-01.jpg?height=420&width=597&top_left_y=1960&top_left_x=387)

Upper bound: We show the bound inductively. This means that we take an $n \times n$ field and add a new border with width 2. We show that we can then color no more than $(n+2) \frac{(n+2)+1}{2}$ fields black.

We cover the new border with $2 \times 2$ fields and a $1 \times 1$ field, as in the following image:

| 2 | | | |
| :---: | :---: | :---: | :---: |
| 2 | $n \frac{n+1}{2}$ | | |
| 2 | | | |
| 2 | 2 | 2 | 2 |
| 1 | | | |

- There are a total of $2 \frac{n+1}{2}$ squares of size $2 \times 2$ (the sides are $n+2$ long). A maximum of 2 cells in each square can be black, i.e. a maximum of $4 \frac{n+1}{2}$.
- In the $1 \times 1$ field, a maximum of 1 field can be black.
- In the large rectangle, a maximum of $n \frac{n+1}{2}$ can be black (induction assumption).

Together, this results in a maximum number of

$$
\begin{aligned}
4 \frac{n+1}{2}+1+n \frac{n+1}{2} & =\frac{4 n+4}{2}+\frac{2}{2}+\frac{n^{2}+n}{2} \\
& =\frac{n^{2}+5 n+6}{2} \\
& =\frac{(n+2)(n+3)}{2} \\
& =(n+2) \frac{(n+2)+1}{2}
\end{aligned}
$$

This completes the induction step.