In a $3 \times 3$ table, we placed a 1-forint coin heads up in each cell. What is the minimum number of coins we need to flip so that there are neither three heads nor three tails in a row (row, column, diagonal)?
Solution. Consider three rows of the table. They have no common part, and each of them must contain at least one head. This means that we must flip at least 3 coins, and these must be placed in different rows and, similarly, in different columns. If there were no heads in any corner, then only the positions marked on the 1st figure could be considered; however, it is not possible to choose three of these so that they are all in different rows and different columns. Therefore, there must be a head in one of the corners; let it be, for example, the top left.

![](https://cdn.mathpix.com/cropped/2024_05_02_297db299d46efff322f8g-1.jpg?height=193&width=195&top_left_y=397&top_left_x=954)

Figure 1

According to the requirement of different rows and columns, in this case, the other two heads can only be placed in two ways (cases 1 and 2, Figure 2). It can be seen that in case 1, three heads fall on a diagonal, and in case 2, one diagonal remains all tails; thus, flipping 3 coins is not enough, at least 4 are needed. However, 4 is sufficient, a possible arrangement is shown in Figure 3.

![](https://cdn.mathpix.com/cropped/2024_05_02_297db299d46efff322f8g-1.jpg?height=189&width=193&top_left_y=911&top_left_x=955)

Figure 2

![](https://cdn.mathpix.com/cropped/2024_05_02_297db299d46efff322f8g-1.jpg?height=189&width=193&top_left_y=1239&top_left_x=955)

Figure 3

We can generalize the problem to an $n \times n$ table instead of a $3 \times 3$ one, where $n \geq 4$. In this case, for $n \geq 4$, it is sufficient to flip $n$ coins; a suitable choice is shown in Figure 4.

![](https://cdn.mathpix.com/cropped/2024_05_02_297db299d46efff322f8g-1.jpg?height=437&width=379&top_left_y=1668&top_left_x=862)