MathDB
Finding a chain within subsets

Source: China TSTST 3 Day 1 Problem 3

March 17, 2017
combinatoricsSetsChina TST

Problem Statement

Let XX be a set of 100100 elements. Find the smallest possible nn satisfying the following condition: Given a sequence of nn subsets of XX, A1,A2,…,AnA_1,A_2,\ldots,A_n, there exists 1≤i<j<k≤n1 \leq i < j < k \leq n such that Ai⊆Aj⊆Ak or Ai⊇Aj⊇Ak.A_i \subseteq A_j \subseteq A_k \text{ or } A_i \supseteq A_j \supseteq A_k.
Back to ProblemsView on AoPS