Circle chains

Let a chain of $10$ circles be called a bundle .

Note that if we have a chain of $n$ circles, then the number of chains of size $k$ in this chain is simply $\binom{n}{k}$ ; pick any $k$ circles and they form a chain.

First, we claim that this number is at most $154$ . Consider a collection of circles: $12$ circles form a single chain, and the remaining $88$ circles are divided into $8$ chains of $11$ circles each; these $9$ chains are otherwise disjoint. By pigeonhole principle , there are $10$ circles picked but only $9$ chains present, so there are two circles that come from the same chain, and thus they form a chain, satisfying the condition of the problem. Afterwards, we can easily see that there are $\binom{12}{10} = 66$ bundles in the chain of size $12$ , and $\binom{11}{10} = 11$ bundles in any chain of size $11$ , for a total of $66 + 8 \cdot 11 = 154$ bundles. Finally, there is no other bundle; picking two circles from different chains won't make them a chain.

We will now prove that $154$ is indeed the minimum (any such collection of circles must have at least $154$ bundles).

Consider a partial order $(S, \le)$ where $S$ is the set of circles on the plane and $\le$ is the relation completely contained in ; that is, if $a \le b$ , then $a$ is completely contained in $b$ . It's straightforward to see that $\le$ is a partial order:

• $a \le a$ (reflexivity)
• $a \le b \wedge b \le a \implies a = b$ (antisymmetry)
• $a \le b \wedge b \le c \implies a \le c$ (transitivity)

Recall that if $a \le b$ or $b \le a$ , then $a$ and $b$ are said to be comparable ; otherwise, they are incomparable . A chain is thus an actual chain in order theory terminology: a set of elements such that any two of them are comparable. Also recall that an antichain (or independent set ) is a set of elements such that any two of them are incomparable.

The condition of the statement states that there is no antichain of size $10$ , for if there is any, those $10$ circles are pairwise incomparable, contradicting that some two circles should form a chain and thus comparable. Thus the size of the largest antichain is $9$ . By Dilworth's theorem , this implies that it's possible to partition the circles into at most $9$ (disjoint) chains; call these chains as big chains .

Suppose there is a big chain of $13$ or more circles. Then there are at least $\binom{13}{10} = 264 > 154$ bundles, already passing our target.

Now suppose that there are $a$ big chains of size $12$ , $b$ big chains of size $11$ , and $c$ big chains of size $10$ or less. Also suppose there are $B$ bundles in total. We have:

• $a+b+c \le 9$ : the number of big chains is at most $9$
• $12a+11b+10c \ge 100$ : the number of circles among the big chains is $100$ , but the big chains with size less than $10$ are augmented up to $10$ , so $12a+11b+10c$ counts more than the number of circles
• $\binom{12}{10}a + \binom{11}{10}b \le B$ : the number of bundles from big chains of size $12$ and size $11$ doesn't exceed $B$

Note that by pigeonhole principle, there are $100$ circles and $9$ big chains, so at least one big chain has $12$ circles. This means $a \ge 1$ . Also,

$\begin{aligned} 100-12a &= 11b+10c \\ &= b + 10(b+c) \\ &\le b + 10(9-a) \end{aligned}$

Simplifying, this gives $b \ge 10-2a$ . Also, we know that $b \ge 0$ , so we have $b \ge \max \{0, 10-2a\}$ . Substituting to the last inequality, we have:

$\begin{aligned} B &\ge \binom{12}{10}a + \binom{11}{10}b \\ &= 66a + 11b \\ &\ge 66a + 11 \cdot \max \{0, 10-2a\} \\ &\ge 66a + 11 \cdot (10-2a) \\ &= 110+44a \\ &\ge 110 + 44 \cdot 1 = 154 \end{aligned}$

This proves the claim, showing that $\boxed{154}$ bundles is the minimum.