Partial order

Task number: 3839

Consider a chessboard \( 4 \times 4 \) and a knight located in its lower left corner. We define the relation \( \preceq \) on the chessboard squares, where \( a \preceq b \) means that the square \( a \) lies on some of the shortest paths by the knight from the lower left corner to the square \( b \).

How many maximum elements does \( \preceq \) have?

  • 2
  • 3
  • 4
  • Solution

    The breadth-first search reveals that the longest paths end in the corners – opposite corner at a distance of 2, the remaining two corners at a distance of 5. The remaining squares lie on these paths of length 5.

  • Answer

    The correct answer is b.

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