There are n odd citizens living in StrangeBrew.

There are n odd citizens living in StrangeBrew. Their main occupation was forming various groups (with

"We're strange doesn't mean we are strangers" being their motto), which at some point started threatening

the very survival of the city. In order to limit the number of groups, the city council decreed the following

innocent-looking rules:

Each group has to have an odd number of members.

Every two groups must have an even number of members in common.

 Prove that under these rules, it is impossible to form more groups than n , the number of citizens. You must

use matrix properties to prove this theorem. [Hint: Consider defining an mn matrix A (for n citizens and

m groups G1;G2; : : : ;Gm ) by aij = 1 if j 2 Gi  and 0 otherwise.]