6. (7 points) On a chessboard, there were 21 kings. Each king was under attack by at least one of the others. After some kings were removed, no two of the remaining kings attack each other. What is the maximum number of kings that could remain?

a) Provide an example of the initial arrangement and mark the removed kings.

b) Prove that a greater number of kings could not remain.
Answer: b) 16.

Solution: Note that each king removed from the board could not have attacked more than 4 of the remaining ones (otherwise, some of the remaining ones would also attack each other). Therefore, the number of remaining kings cannot exceed the number of removed ones by more than 4 times, meaning it cannot be more than 16. An example is shown in the figure: gray marks the kings that need to be removed.

![](https://cdn.mathpix.com/cropped/2024_05_06_09b0e7336bad4773d41eg-4.jpg?height=603&width=623&top_left_y=1629&top_left_x=725)

## Grading Criteria.

- Any complete and correct solution of both parts - 7 points.
- Only one part is correctly solved - 3 points
- Only the answer is provided - 0 points.

Maximum score for all completed tasks - 42.