Competition problem — Combinatorics

Library / /63 of 97

Combinatorics Difficulty 8.2 Shortlist Find the answer

Let $X$ be a set of $100$ elements. Find the smallest possible $n$ satisfying the following condition: Given a sequence of $n$ subsets of $X$ , $A_1,A_2,\ldots,A_n$ , there exists $1 \leq i < j < k \leq n$ such that
$A_i \subseteq A_j \subseteq A_k \text{ or } A_i \supseteq A_j \supseteq A_k.$

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let $X$ be a set of $100$ elements. We aim to find the smallest possible $n$ such that given a sequence of $n$ subsets of $X$ , $A_1, A_2, \ldots, A_n$ , there exists $1 \leq i < j < k \leq n$ such that
$A_i \subseteq A_j \subseteq A_k \text{ or } A_i \supseteq A_j \supseteq A_k.$

The smallest possible $n$ satisfying this condition is given by:
$2 \binom{100}{50} + 2 \binom{100}{49} + 1.$

The answer is: $\boxed{2 \binom{100}{50}}$ + 2 $\binom{100}{49}$ + 1}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.