MathDB

C4

Part of 2023-IMOC

Problems(1)

Ghost leg

Source: IMOC 2023 C4

9/9/2023
A ghost leg is a game with some vertical lines and some horizontal lines. A player starts at the top of the vertical line and go downwards, and always walkthrough a horizontal line if he encounters one. We define a layer is some horizontal line with the same height and has no duplicated endpoints. Find the smallest number of layers needed to grant that you can walk from (1,2,…,n)(1, 2, \ldots , n) on the top to any permutation (σ1,σ2,…,σn)(\sigma_1, \sigma_2, \ldots, \sigma_n) on the bottom.
combinatorics