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.
