MathDB

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, \ldots , n)

on the top to any permutation

(\sigma_1, \sigma_2, \ldots, \sigma_n)

on the bottom.

Problem Statement