nice one

sam-n

let $A$ and $B$ be families of the subsets of an n-element set with the property that $|a\cap b|$ is odd for all $a\in A$ and $b\in B|$ . prove that then $|A||B|\leq 2^{n-1}$ .

**Posted:** Wed Mar 02, 2005 10:56 am

iura

Translating the problem into vector language we have two sets of vectors $A,B \subset \{0,1\}^n$ with $uv=1$ whenever $u \in A, v \in B$ .
Now let $b_1,\cdots,n_m$ be a basis of $B$ . Then we have $|B|\leq 2^{m-1}$ because obviously the sets $B, B+b_1$ are disjoint subsets of the vectorial space spanned by $b_1,\cdots,b_m$ .
Now we are left to prove that $|A|\leq 2^{n-m}$ . But since $b_i$ are linearly independent there exist vectors $b_i'$ with $b_ib_j'=1$ iff $i=j$ .
We see that $b_1',\cdots,b_m'$ are linearly independent because if $\sum e_i b_i'=0$ then multiplying by $b_i$ we get $e_i=0$ for any $i$ .
Hence $H$ the subspace spanned by $b_1',\cdots,b_m'$ satisfies $|H|=2^m$ .
Now we see that the sets $A+x, x \in H$ are all disjoint subsets of $\{0,1\}^n$ . Thus we get $|A|\leq 2^{n-m}$
QED

**Posted:** Wed Mar 02, 2005 1:39 pm

Myth

WoW! Great!

**Posted:** Wed Mar 02, 2005 10:44 pm

_________________
Myth is out of here