Goban stones
Task number: 3992
In go, stones are placed at intersections, that is, at the vertices, of the \( 19 \times 19 \) grid. This board is called goban.
There are several stones placed on the goban so that in each row and column has the same number of stones.
In this situation, is it possible to remove several stones from the board so that exactly one stone remains in each row and column (without moving the others in any way)?
Solution
Create a bipartite graph with both classes of bipartition \( R \) and \( C \) of size 19. We draw an edge between the vertices \( r \) and \( c \), if a stone is placed on the intersection of the \( r \)-th row and the \( c \)-th column.
The graph is bipartite regular, so it has a perfect matching and this corresponds to the position of the remaining stones.
Answer
Yes, you can always keep a suitable group of stones.
