Consider a $4 \times 4$ grid consisting of 16 cells. What is the minimum number of cells that need to be blackened so that by eliminating any two columns and any two rows, we are sure that at least one black cell remains?

## 2 Solution
We will show that at least 7 squares must be blackened. First, if we color the squares as follows:

![](https://cdn.mathpix.com/cropped/2024_05_10_7286ba4d154441c7d078g-19.jpg?height=428&width=434&top_left_y=182&top_left_x=802)

then we verify the hypothesis of the statement. Indeed, let's try to erase two rows and two columns so that the four remaining squares are white. We need to erase the square in the top left corner, so let's erase the first row (erasing the first column would be the same). I leave it to you to verify that afterwards it is impossible to erase one row and two columns such that there are four remaining white squares.

Now suppose we have blackened 6 squares or fewer. We will erase the two rows with the most black squares. How many black squares remain in the remaining rows? Already, there are fewer than half, so 3 or fewer. But there cannot be 3 left, otherwise it would be one row of 2 and one row of 1, and in those we erased there were 3, so one row of 2 and one row of 1, and we would have had to erase the two rows of 2. Therefore, there are at most 2 black squares left in the remaining rows, and we can erase the two columns corresponding to these two squares, and the remaining squares will all be white.

It is therefore impossible to have a configuration that satisfies the condition of the statement if we color only 6 squares. We must indeed have at least 7 squares.

## IV. Beginners

## 1 Tuesday: Combinatorics

## 1 Morning: Irène Marcovici

## Pigeonhole Principle

PIGEONHOLE PRINCIPLE - If at least \( n+1 \) objects are placed in \( n \) drawers, at least one drawer (at least) will contain at least two objects. More generally, if at least \( k n+1 \) objects are placed in these same \( n \) drawers, at least one drawer (at least) will contain at least \( k+1 \) objects.

A very simple example: among 13 people, we can find 2 who were born in the same month of the year.

One of the first mathematical results that can be deduced from this is that the decimal expansion of the fraction \(\frac{p}{q}\) is periodic, with a period strictly less than \( q \). Indeed, when performing the division, each new decimal corresponds to a new remainder. Among \( q \) consecutive remainders, either one is zero (and the division stops, which corresponds to a period of 1, since from a certain rank, all the decimals are equal to 0), or these \( q \) remainders are all between 1 and \( q-1 \), which proves that at least two of them, \( r_i \) and \( r_j \), are equal. Since each remainder determines the entire sequence of the division, \( r_{i+1} = r_{j+1}, r_{i+2} = r_{j+2} \ldots \) therefore the decimal expansion will be periodic, with a period of at most \( |i-j| < q \).