Homework 7

Deadline: Dec. 14, 22:00:00

1. Prove the even/odd town theorem:

   Suppose there are $m$ clubs and $n$ people such that (i) each club contains an even number of people and (ii) each pair of clubs shares an odd number of people. Then $m \leq n$.

2. Prove the odd/odd town theorem:

   Suppose there are $m$ clubs and $n$ people such that (i) each club contains an odd number of people and (ii) each pair of clubs shares an odd number of people. Then $m \leq 2^{\lfloor (n-1)/2\rfloor}$.

3. Suppose $\mathcal{F}$ is a family of set of $[n]$ such that (i) $\forall S \in \mathcal{F}$, $|S|$ is not divisible by $15$, and (ii) $\forall S\neq T \in \mathcal{F}$, $|S\cap T|$ is divisible by $15$. Show that $|\mathcal{F}| \leq 2n$.

4. Suppose $A, B \subseteq \mathbb{R}^3$ are two sets of points in $\mathbb{R}^3$ such that all distances between members of $A$ and members of $B$ are equal. Prove that $\min\,\{|A|, |B|\} \leq 2$.

5. We have $13$ balls of some weights. Suppose that if we remove any of them, the remaining $12$ weights can be divided into two sets of $6$, with equal weight. Prove that all balls have the same weight.

   (Hint: Suppose $M$ is an $2n\times 2n$ matrix with zeros in the diagonal and $\pm 1$ everywhere else. Then $M$ has an inverse matrix. (Prove this result before using it.))