Exercise 12. Martin is playing a game. His goal is to place tokens on an 8 by 8 chessboard such that there is at most one token per square, and each column and each row contains at most 4 tokens.

a) How many tokens can Martin place, at most?
b) If, in addition to the previous constraints, each of the two main diagonals can contain at most 4 tokens, how many tokens can Martin place, at most?

The main diagonals of a chessboard are the two diagonals running from one corner of the chessboard to the opposite corner.
Solution to Exercise 12 First, each column contains at most 4 tokens. Since there are 8 columns, Martin cannot place more than $4 \times 8=32$ tokens. Retrospectively, Martin can indeed place 32 tokens while respecting all the constraints of the statement, both in case a) and in case b). For example, he can proceed as in the grid below, which even allows Martin to arrange it so that none of the major diagonals contain a token.

![](https://cdn.mathpix.com/cropped/2024_06_04_ba585959d2e020eaf8cbg-6.jpg?height=455&width=466&top_left_y=1819&top_left_x=821)

Graders' Comment Exercise well understood. Each of the questions has two parts: showing that there are at most 32 tokens and then providing a configuration in which 32 tokens can indeed be placed while respecting the conditions. Several students were content with only one of these steps. For the configuration, a clear chessboard drawing was better than a long description in paragraphs.