3. 16 cards with integers from 1 to 16 are laid face down in a $4 \times 4$ table so that cards with consecutive numbers are adjacent (touching by a side). What is the minimum number of cards that need to be flipped simultaneously to definitely determine the location of all numbers (regardless of how the cards are arranged)?
Answer. Eight cards

## Solution.

Evaluation. Let's number the cells as shown in Figure 1.

Notice that one of the cells numbered 1 must be open, otherwise the red and blue ways of filling the table in Figure 2 would be indistinguishable. One of the cells numbered 2 must also be open, otherwise the red and blue ways of filling the table in Figure 3 would be indistinguishable.
![](https://cdn.mathpix.com/cropped/2024_05_06_3b420d6da7f7eeaa987cg-1.jpg?height=362&width=744&top_left_y=1802&top_left_x=1162)

Similarly, at least one of the cells numbered $3,4,5,6,7,8$ must be open, meaning that at least 8 cards must be open.

Fig. $1 \quad$ Fig. $2 \quad$ Fig. 3

Example. Let's prove that by seeing the numbers in the second and third columns, we can restore the numbers in the first and fourth columns. Notice that in the black cells of the chessboard coloring, all numbers have the same parity, and in the white cells, the other parity. By seeing the second and third columns, we understand the parity of the number in each cell.

From the open cells, we highlight those for which not all adjacent numbers are open. From each such cell, we draw an edge to the only unopened adjacent cell and uniquely restore the number in it.

Notice that if an edge leads to a corner, we will restore the number in it. If no edge leads to a corner cell, then it contains an extreme number, i.e., 1 or 16, and since we know the parity of the number in each cell, we can also restore the number in the corner. Thus, the numbers in the corners are definitely restored.

If there are corner cells among the corners for which not all adjacent numbers are open, we draw an edge from each such corner to the unopened adjacent cell and uniquely restore the number in it.

The only numbers left un-restored are those in the non-corner cells of the first and fourth columns. Consider any of them. No edge leads to it from the adjacent column or from the corner, so in this cell, there must be an extreme number (since it has at most one adjacent cell with a number). By parity, it is easy to determine which extreme number should be there.

Thus, we have restored the numbers in all cells.