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) What is the maximum number of tokens Martin can place?

b) If, in addition to the previous constraints, each of the two main diagonals can contain at most 4 tokens, what is the maximum number of tokens Martin can place?

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_04_29_73269b600131539d27eeg-6.jpg?height=456&width=464&top_left_y=1821&top_left_x=825)