Exercise 6. A set of $\mathrm{n}$ cells in an $\mathrm{n} \times \mathrm{n}$ grid is said to be distributed if it never includes two cells in the same row or column. In how many ways can one color some (possibly none) cells of an $\mathrm{n} \times \mathrm{n}$ grid so that all distributed sets contain the same number of colored cells?
Solution to Exercise 6 We notice that any set of rows is a valid coloring, and any set of columns is also valid. Let's show that these are the only ones. We fix a set of colored cells that works.

Suppose that on row $a$, the cell $(a, b)$ is colored but not $(a, c)$. Take a scattered set that contains $(a, b)$ and $\left(a^{\prime}, c\right)$ (This is possible, for example, by taking all $(x, x)$ for $x \neq a, b, a^{\prime}, c$, as well as $(a, b), (b, a), \left(a^{\prime}, c\right)$, and $\left(c, a^{\prime}\right)$; to verify that it works, one just needs to distinguish the cases where $a=b$ and where $a^{\prime}=c$). If we replace these two cells with $\left(a^{\prime}, b\right)$ and $(a, c)$, we still have a scattered set. The only way to keep the number of colored cells the same is for the cell $\left(a^{\prime}, b\right)$ to be colored but not $\left(a^{\prime}, c\right)$.

Thus, if we take a colored cell and its entire row is not colored, then we have just shown that its entire column is colored. By symmetry, if we take a colored cell and its entire column is not colored, then its entire row is colored. Therefore, either its entire row is colored, or its entire column is colored (or both).

Now suppose that row $a$ is colored as well as column $b$ and let's show that all cells in the grid are colored. Suppose, for the sake of contradiction, that there exists a cell $(c, d)$ that is not colored. We fix a scattered set containing $(a, b)$ and $(c, d)$. By replacing them with $(a, d)$ and $(c, b)$, we gain a colored cell; contradiction.

Finally, to obtain a valid configuration, we first choose an orientation (rows or columns) and then, for example, if we choose the rows, we decide which rows to color, and we color these rows entirely, and only these. By observing that a scattered set has exactly one cell in each row and each column, we deduce that the coloring thus obtained is valid.

We then count $2 \cdot 2^{n}$ configurations, $2^{n}$ for each orientation. However, two of them are identical, namely the configurations where everything is colored or nothing is colored, which can be obtained from both orientations. Therefore, there are a total of $2^{n+1}-2$ ways to color the grid.
![](https://cdn.mathpix.com/cropped/2024_06_04_7f99ab0e41c82ac4a4c9g-07.jpg?height=420&width=824&top_left_y=1652&top_left_x=648)

FIGURE 2 - The only possible types of configurations for scattered sets

Graders' Comments: The exercise is only partially successful. Many students identified the grids that satisfy the statement, but the whole point of the problem was to prove that either all rows were monochromatic or all columns were monochromatic, and many students did not do this rigorously.