Required reading: Section 3.2-3.4 (if you haven't read it yet), except p. 176-179

Assignment #8 is due on Wednesday , November 21.

Additional homework (do not hand in).

• Section 3.3, Problems 1, 2, 4, 10
• Section 3.4, Problems 1, 2 (pick a few)

Odd town puzzle revisited: In a town with $n$ inhabitants, there are $N$ clubs. Each club has an odd number of members, and for any two distinct clubs there is an even number of common members. Prove that $n\ge N$. We wrote a solution a few weeks ago, but here is a new solution using the properties of rank of matrices.

Another combinatorial problem, using a similar trick: Let $X$ be a set with $n\ge 3$ elements, and let $S_1,\ldots,S_m$ be proper subsets of $X$ (i.e., $S_j\not= X$ for each $j$). Suppose that every pair of distinct elements of $X$ is contained in a unique set $S_j$. Prove that $m\ge n$. Hint: Enumerate the elements of $X$, and consider the incidence matrix $A$, where $A_{ij}=1$ if the $i$-th element is contained in the set $S_j$, and $A_{ij}=0$ otherwise.