One wonders about the point of brain teasers like the following. Find the minimum cardinality set such that there exists a family of subsets of none of which contains the other.
The minimal cardinality is . Let be the family of -element subsets of a set of eight elements. We have
Such a family works: for any , if and only if .
The cardinality of such an is at most 8; is it at least 8?
Consider the lattice of subsets of a set of seven elements under inclusion. To show that the cardinality of is at least , we have to show that the size of the largest antichain in is less than . By Sperner’s Theorem, the cardinality of the largest antichain in 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.
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.