# Problems

One wonders about the point of brain teasers like the following. Find the minimum cardinality set $X$ such that there exists a family $\mathcal{F}$ of $70$ subsets $\{A_i\}$ of $X$ none of which contains the other.

The minimal cardinality is $8$. Let $\mathcal{F}$ be the family of $4$-element subsets of a set of eight elements. We have

Such a family works: for any $1\le i,j\le 70$, $A_i \subseteq A_j$ if and only if $A_i = A_j$.

The cardinality of such an $X$ is at most 8; is it at least 8?

Consider the lattice $(\mathcal{L}_7,\subseteq)$ of subsets of a set of seven elements under inclusion. To show that the cardinality of $X$ is at least $8$, we have to show that the size of the largest antichain in $\mathcal{L}_7$ is less than $70$. By Sperner’s Theorem, the cardinality of the largest antichain in $\mathcal{L}_7$ is at most

If I wanted to rearrange an array of integers so that all the even integers were to the left of the odd integers, then I might do this.

 1 2 3 4 5 6 7 8 9 10 11 12  def evenodd(a): i = 0 while a[i] % 2 == 0 and i < len(a): i += 1 j = i i -= 1 # invariant [0,i] even [i+1,j] odd while j < len(a): if a[j] % 2 == 0: a[i+1],a[j] = a[j],a[i+1] i += 1 j += 1 

Only, I’m not sure why I would want to do this.