Pedagogical Puzzles

Only one puzzle this time, which is more an open problem than a puzzle. Please send your contributions to this column to the editor.

Let F be a family of subsets of a finite set X which is closed under intersection---i.e., if A,B are elements of F , then so is A intersection B . Prove or disprove the following statement:
There is an element x in X which belongs to at most |F|/2 sets in F .

Solutions to last time's puzzles

There were three puzzles last time, all from the book Elements of the Theory of Computation by Harry Lewis and Christos Papadimitriou. We discuss the solutions here.

The links below will show you the "pseudo-latex" files. Click here for a postscript file containing the solutions.
Previous Puzzle 1 (weak PCP)
Previous Puzzle 2 (emptiness for 2H-FA)
Previous Puzzle 3 (Tiling)