Given an column and row chessboard, on which we have placed some coins (at most one per square). We call two coins adjacent if they are in the same row or column, and there is no other coin on the segment connecting them. Each coin has at most three neighbors. What is the maximum number of coins on the chessboard?
Solution
I. solution. If every disc has at most three neighbors, or sees at most three other discs on the board, this means that in at least one direction, it has no neighbor. We can say that it looks out of the board through a window, where the "window" is a unit part of the chessboard's perimeter.
We can establish that a disc can be placed in any corner in any arrangement without obstructing the view of any other disc. This is true because the discs in the outermost rows and columns directly look out of the board, as one of their sides is on the board's perimeter. The four discs placed in the corners cover a total of 8 windows.
Then, windows remain. We can place the most discs if each one looks out of exactly one window. Such an arrangement exists, for example, if we fill all the edge squares with discs. From this, we can generate more good solutions by pushing the edge discs inward, but we cannot place any more discs (a ́ b r a).
!
It can be established that for , the number of discs can be at most . If or , then the maximum number of discs that can be placed on the board is the number of squares, in which case each disc has at most two neighbors.
II. solution. The number of neighbors a disc has indicates how many of the directions "above it in its column," "below it in its column," "to its left in its row," and "to its right in its row" contain another disc.
Consider an arrangement where the maximum number of discs is on the board such that each disc has at most three neighbors. In this case, there must be a disc in every corner, because if there were not, placing one more disc in the corner would result in a valid arrangement with more discs. (A disc placed in the corner can have at most two neighbors. The placement would only increase the number of neighbors for discs in the outermost row or column, so their number of neighbors would not exceed three.)
Mark the discs that have no other disc above them in their column. There can be at most one such disc per column, so a total of at most marks. Now mark the discs that are the lowest in their column, which again can be at most marks. Mark the discs that are the first in their row, of which there can be at most marks, and the discs that are the last in their row, of which there can be at most marks. This totals at most marks, but the discs in the corners are marked twice. Therefore, there can be at most marked discs.
There cannot be any unmarked discs, because if there were, it would mean that there is another disc below and above it in its column and before and after it in its row, giving it four neighbors.
Thus, the maximum number of discs that can be placed on the board in the correct manner is .
If , then this many can indeed be placed, for example, by filling all the edge squares with discs. In this case, the discs in the corners will have two neighbors, and the others will have three.
If or , then the maximum number of discs that can be placed on the board is the number of squares. In this case, the two edge discs will have one neighbor each, and the others will have two.