Collection of Maths Problems

Square coloring

Task number: 3923

• Variant

  At most 5 different colors appear in each row and column.

• Hint

  There are two ways to count the number of pairs \( (p, c) \), where \( p \) is a cell (position) and \( c \) is a color.

  Divide the colors into two groups: colors that occur in a limited number of columns, and the remaining colors.

• Solution

  The number of pairs \( (p, c) \) is \( 21 ^ 2 = 441 \), because this is the total number of cells.

  For contrary, assume that each color occurs in either two columns or two rows.

  From colors that occur in at most two columns, we create at most \( 21 {\cdot} 5 \cdot 2 = 210 \) pairs, because in each of the 21 rows we find at most 5 different colors and each of them has in this row at most two occurrences.

  The other colors appear in at most two lines. In a similar way they also cna make at most 210 pairs.

  However, we will only create 420 pairs in these two ways, which leads to a contradiction.

• Variant

  No more than 6 different colors in each column and row.

• Hint

  Use Dirichlet’s principle twice.

• Solution

  It is possible to use the procedure from the previous variant and, in addition, argue that each row contains a maximum of 5 ‘two-column’ colors. If ‘two-column’ there were 6 colors, only 12 cells out of 21 could be colored in a given row, because another colors would no longer be available.

  An alternative argument:

  Again, we divide the colors into those that appear in at most two rows. Let’s call them bright, and the other dark.

  The grid has 441 cells, so at least half of the colors are light or at least half are dark, w.l.o.g. consider that at least 221 cells are light-colored.

  According to Dirichlet’s principle, at least one column \( C \) contains \( \lceil \frac{221}{21} \rceil = 11 \) bright cells. Each of these light colors has at most two occurrences in \( C \). Thus, \( C \) contains at least \( \lceil \frac{11}{2} \rceil = 6 \) light colors. Because each color has at most 6 occurrences in each column, there are only these light colors and no dark colors in the column \( C \). These light colors can color up to 12 cells of \( C \). The remaining cells would remain uncolored, which is a contradiction.

• Answer

  Yes, even here some of the colors must appear in at least three rows and columns.