本問の状況を一般に表したものとして、Mirsky の定理があります。

参考：https://en.wikipedia.org/wiki/Mirsky%27s_theorem

[定理] 有限順序集合 \(P\) について、次の \(2\) つの値は等しい。

• 鎖の最大の要素数 \(a\)。つまり、\(a = \max\{n|x_1\leq x_2\leq \cdots \leq x_{n}\}\)。
• \(P\) を反鎖 \(n\) 個に分割するとき、\(n\) の最小値 \(b\)。

[証明]

• \(a\leq b\) の証明：要素数 \(a\) の鎖 \(C\) を固定する。反鎖は \(C\) の要素をひとつまでしか含むことができない。よって、\(C\) を反鎖で被覆するために \(a\) 個以上の反鎖が必要。
• \(a\geq b\) の証明：各 \(x\in P\) に対して、\(f(x) = \max\{n\mid x_1 < \cdots < x_n = x\}\) として、反鎖 \(A_n\) を \(A_n = \{x\mid f(x) = n\}\) と定めると、\(a\) 個の反鎖による \(P\) の分割が得られる。

本問では、\(a\) 個の反鎖による \(P\) の分割の構築パートが問われていました。