MathDB

Problem 2

Part of 2019 CIIM

Problems(1)

CIIM 2019 Problem 2

Source:

8/30/2021
Consider the set {0,1}n={X=(x1,x2,…,xn):xi∈{0,1},1≤i≤n}.\{0, 1\}^n = \{X = (x_1, x_2,\dots , x_n) : x_i \in \{0, 1\}, 1 \leq i \leq n\}. We say that X>YX > Y if X≠YX \neq Y and the following nn inequalities are satisfy x1≥y1,x1+x2≥y1+y2,…,x1+x2+⋯+xn≥y1+y2+⋯+yn.x_1 \geq y_1, x_1 + x_2 \geq y_1 + y_2,\dots , x_1 + x_2 + \cdots + x_n \geq y_1 + y_2 + \cdots + y_n. We define a chain of length kk as a subset Z1,…,Zk⊆{0,1}n{Z_1,\dots , Z_k} \subseteq \{0, 1\}^n of distinct elements such that Z1>Z2>⋯>Zk.Z_1 > Z_2 > \cdots > Z_k. Determine the lenght of longest chain in {0,1}n\{0,1\}^n.
CIIM