Oh my god! I didn't read $1 \leq i < j < k \leq n$... The answer is edited...

This problem is just Sperner's Theorem. Let's just say for now we can renumber things. If there is a 5-chain, by the $mn+1$ problem, we have a 3-chain in order of our previous numbering. We will use the well-known double counting method which is used to solve the original Sperner's Theorem. Also, note that 49-set, 48-set, 51-set, 50-set has no 3-chain in order. We will show that this is optimal. Change the notation a bit and generalize to $|X|=n$. Let $P$ be a cyclic permutation of $X$. Let $F$ be the set of subsets of $X$ which has no 3-chains. If $F$ has the empty set or $X$, we can say that there is no 4-chain (which can be shown that this is bad) So let's say that $F$ does not have the empty set or $X$ itself. Denote $F(P)$ as the set of sets in $F$ which form an interval/arc in $P$. Lemma. $|F(P)| \le 4n$. Proof of Lemma. For each "start" of the interval, there can be at most $4$ sets belonging to $F$. If there are five or more, they will form a chain, a contradiction. This gives the lemma. Now we have $\sum_{P} |F(P)| \le 4n \cdot (n-1)! = 4n!$. Also, note that the number of $P$ such that has a set $F$ as an interval is just $|F|!(n-|F|)!$ since $|F| \not= 0, n$. Let $s_i$ be the number of sets in $F$ that have cardinality $i$. Let's do double counting. We now have $4n! \ge \sum_{P} |F(P)| \ge \sum_{i=1}^{n-1} s_i \cdot i! \cdot (n-i)!$, so just $\sum_{i=1}^{n-1} \frac{s_i}{\binom{n}{i}} \le 4$. Let's do linear programming. We have $\sum_{i=1}^{n-1} \frac{s_i}{\binom{n}{i}} \le 4$, and $s_i \le \binom{n}{i}$. We want to maximize $\sum_{i=1}^{n-1} s_i$. I claim that the maximum is just the sum of four largest binomial coefficients. Set $(u_1, \cdots , u_{n-1})$ as the optimal values for $(s_1, \cdots , s_{n-1})$. If $\binom{n}{i} > \binom{n}{j}$ and $u_i < \binom{n}{i}$ and $u_j>0$, we can change $u_i$ to be $u_i+\epsilon \cdot \binom{n}{i}$ and $u_j$ to be $u_j - \epsilon \cdot \binom{n}{j}$. This makes $\sum_{i=1}^{n-1} \frac{u_i}{\binom{n}{i}}$ the same, while increasing $\sum_{i=1}^{n-1} u_i$. This is a contradiction. Therefore, it is good to "push" all values of $u$ to $u_i$ which has the largest $\binom{n}{i}$. This gives the desired claim. Now let $n=100$. The maximal number of subsets to not form a 5-chain is $\binom{100}{48}+\binom{100}{49}+\binom{100}{50} + \binom{100}{51}$. The answer is $\binom{100}{48}+\binom{100}{49}+\binom{100}{50} + \binom{100}{51}+1$, as desired.

What is wrong with the following? Consider a sequence of all 49-sets, then all 51-sets, then all 50-sets. This has no 3-chain and has length longer than $\binom{101}{50} + 1$.

@above f*** my life I thought we could renumber things Of course that would be too easy for #3 lol

Sniped . Actually, we should be able to view the set of solutions as a subset of the set of solutions to the 4-chain version of Sperner's Theorem (because of the well-known $mn+1$ problem), so we only need to show that Canton's example is one of the maximal constructions for the latter problem (which seems intuitively true).

If this can be reduced to 4-chain, one can just fix my proof to $|F(P)| \le 3n$, and the rest is the same.

Wait 49-set 48-set 51-set 50-set works doesn't it? So uh 5 chain -> dilworth gives contradiction, 4-chain maximum can be constructed

Yeah I can't add; $2\cdot 2+1=5$, but that seems to work

Well I still can't believe china gave a problem solved by just knowing sperner as a #3..

Well this isn't the first time. Check this out.

@above: The same subset can appear more than once! So the answer is $2\binom{100}{50}+2\binom{100}{49}+1$ Also the translation didn't mention $A_1~A_n$ are subsets of $X$.

There is actually an extremely beautiful solution ($3$ lines) to this problem.Here I translated this solution from YunHao Fu. The key to this problem is to guess the answer and applying Sperner. Miraculously this solution can even be generalized.

if you wanna find this solution yourself !

This question is very difficult. The answer is $\boxed{2\binom{100}{50}+2\binom{100}{49}+1}$. Call a sequence of subsets of $X$ good if it has size $3$ and is either an ``increasing'' or ``decreasing'' chain. The problem condition asks us to find the minimum $n$ such that any sequence of length $n$ is guaranteed to contain a good sub-sequence. Note that the sequence of subsets \[X_{50}\oplus X_{49}\oplus X_{51}\oplus X_{50}\]avoids any good sub-sequences where $X_k$ is a listing of all the subsets of $X$ of size $k$ (the set of which is denoted $\binom{X}{k}$) in an arbitrary order. Here $\oplus$ is concatenation. This sequence has size $2\binom{100}{50}+2\binom{100}{49}$, thus showing $n\ge 2\binom{100}{50}+2\binom{100}{49}+1$. Now suppose that a sequence of length $n$ avoids any good sub-sequences. We'll show that $n\le2\binom{100}{50}+2\binom{100}{49}$, which solves the problem. Let $P$ be the poset of subsets of $X$ ordered by inclusion. Note that the $k$th level is given by $\binom{X}{k}$. We have the following key lemma. Lemma: Our sequence contains at most $4$ elements from each chain of $P$. Proof: Suppose there are $5$ elements in a chain. Then we claim there is a good sub-sequence. Indeed, this can just be checked, or we can cite Erd\"{o}s-Szekeres. $\blacksquare$ Now comes the hard part of constructing an appropriate partial chain decomposition of $P$ to solve the problem. Claim: [Chain Decomposition] There is a saturated chain decomposition of $P$ such that if a chain contains an element on level $50$, it either has size $1$, or it contains elements from both levels $49$ and $51$. First we show how the claim finishes. We see that there are exactly $\binom{100}{50}-\binom{100}{49}$ elements on level $50$ that are part of a singleton chain, and we can select those sets at most twice. We can select at most $4$ sets (counting multiplicity) from the rest of the chains, so there are at most \[2\cdot\left[\binom{100}{50}-\binom{100}{49}\right]+4\binom{100}{49}\]chosen sets, which is the desired bound. Proof: [Proof of Chain Decomposition Claim] We actually do much more and construct a symmetric chain decomposition of $P$. A symmetric chain is one that goes from level $k$ to level $100-k$ for some $k$. Remark: This construction is due to de Brujin. One source can be found at https://arxiv.org/pdf/math/9502224.pdf. Let $m=100$, and let $B_m$ denote the Boolean lattice $(2^{[m]},\subseteq)$. In our case, $P=B_{100}$. We'll show that $B_m$ has a symmetric chain decomposition by induction on $m$, with $m=1$ being clear. Suppose we have chains $C_1,\ldots,C_t$ that are a symmetric chain decomposition of $B_m$. For the chain \[C_i:c_1\subseteq c_2\subseteq \cdots\subseteq c_r,\]add the chains \[c_1\subseteq c_2\le\cdots \subseteq c_{r-1}\subseteq c_r\cup\{m+1\},\]and if $r\ge 2$, then \[c_1\cup\{m+1\}\subseteq c_2\cup\{m+1\}\subseteq\cdots\subseteq c_{r-1}\cup\{m+1\}.\]It's not hard to see that these new chains form a symmetric chain decomposition of $B_{m+1}$, so we're done. $\blacksquare$

Actually I don't know how to solve this problem by sperner's theorem ...BUT erdos-szekeres throrem is definitely a good way to describe how sets are included.Because they are just like two numbers compared

Nice problem as an extension of Spencer Theorem. We view this problem on a hypercube $Q_{100},$ construction is taking the $48,49,50,51$-th layers, it is easy to prove that it doesn't work. For the proof part, first we use Erdos Szekeres Theorem, so we only need to find 5 sets such that $A\subseteq B\subseteq C\subseteq D\subseteq E.$ This is just similar as Spencer Theorem, so in fact, nearly every proof of Spencer Theorem works here. We construct symmetric chains. It is easy to prove by induction that $Q_{100}$ is a disjoint cup of $\binom{100}{50}$ symmetric chains. However the maximum number of sets that in each chain can be taken is achieved when taking the $48,49,50,51$-th layers of hypercube, this ends the proof immediately.$\Box$