renrepS

Probability Level 4

Let S S be a set of subsets of the set { 1 , 2 , 3 , … , 13 } \{1,2,3,\ldots ,13\} such that no element of S S contains another element of S S . What is the maximum number of elements S S can have?


The answer is 1716.

Jorge Fernández by Jorge Fernández , 25, Mexico

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Abhishek Sinha
Aug 21, 2015

In other words, the problem asks for the cardinality of a maximum antichain of the ground set S S of cardinality n = 13 n=13 . The result is ( n ⌊ n 2 ⌋ ) \binom{n}{\lfloor\frac{n}{2}\rfloor} and is given by Sperner's theorem .

5 Helpful 1 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...