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.

Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Cs translation
Send comment on task by email