Consider an $m\times n$ board where $m, n \ge  3$ are positive integers, divided into unit squares. Initially all the squares are white. What is the minimum number of squares that need to be painted red such that each $3\times 3$ square contains at least two red squares?

 Andrei Eckstein and Alexandru Mihalcu
1. **Case 1: Neither \( m \) nor \( n \) is congruent to 2 modulo 3**

   We can partition the \( m \times n \) board into \(\left\lfloor \frac{m}{3} \right\rfloor \times \left\lfloor \frac{n}{3} \right\rfloor\) disjoint \(3 \times 3\) squares. Each \(3 \times 3\) square requires at least 2 red squares to satisfy the condition. Therefore, the minimum number of red squares required is:
   \[
   2 \left\lfloor \frac{m}{3} \right\rfloor \left\lfloor \frac{n}{3} \right\rfloor
   \]

2. **Case 2: Either \( m \) or \( n \) is congruent to 2 modulo 3**

   Suppose \( m \equiv 2 \pmod{3} \). We can partition the board into \(\left\lfloor \frac{m}{3} \right\rfloor \times \left\lfloor \frac{n}{3} \right\rfloor\) disjoint \(3 \times 3\) squares and an additional \(2 \times n\) strip. For the \(2 \times n\) strip, we can paint the rightmost two squares of each \(3 \times 3\) square in the last row. This ensures that each \(3 \times 3\) square contains at least two red squares. The minimum number of red squares required is:
   \[
   2 \left\lfloor \frac{m}{3} \right\rfloor \left\lfloor \frac{n}{3} \right\rfloor
   \]

3. **Case 3: Both \( m \) and \( n \) are congruent to 2 modulo 3**

   We need to show that the minimum number of red squares is:
   \[
   2 \left\lfloor \frac{m}{3} \right\rfloor \left\lfloor \frac{n}{3} \right\rfloor + \min\left(\left\lfloor \frac{m}{3} \right\rfloor, \left\lfloor \frac{n}{3} \right\rfloor\right)
   \]

   - **Base Case: \( m = n = 5 \)**

     For a \(5 \times 5\) board, we need at least 3 red squares. This can be verified by considering different configurations and ensuring that each \(3 \times 3\) square contains at least two red squares.

   - **Induction Hypothesis:**

     Assume the statement is true for \( (3a+2) \times (3b+2) \).

   - **Induction Step:**

     - **For \( (3a+5) \times (3b+2) \):**

       Partition the board into \( (3a+2) \times (3b+2) \) and \( 3 \times (3b+2) \). The second part contains \( b \) disjoint \(3 \times 3\) squares. By the induction hypothesis, the new board requires at least:
       \[
       2ab + b + 2b = 2(a+1)b + b
       \]
       red squares.

     - **For \( (3a+5) \times (3b+5) \):**

       Partition the board into \( (3a+2) \times (3b+2) \) and the figure formed by the union of \( (3a+2) \times 3 \), \( (3b+2) \times 3 \), and \( 3 \times 3 \). This grid contains \( a+b \) disjoint \(3 \times 3\) squares. By the induction hypothesis, the new board requires at least:
       \[
       2ab + b + 2a + 2b + 3 = 2(a+1)(b+1) + b + 1
       \]
       red squares.

   - **Construction:**

     For the construction, consider every third column and paint it such that the last square of the column gets painted. This ensures that each \(3 \times 3\) square contains at least two red squares.

\(\blacksquare\)

The final answer is \( \boxed{ 2 \left\lfloor \frac{m}{3} \right\rfloor \left\lfloor \frac{n}{3} \right\rfloor + \min\left(\left\lfloor \frac{m}{3} \right\rfloor, \left\lfloor \frac{n}{3} \right\rfloor\right) } \)