A Variation of the even-town odd-town problem

Question

Let assume facebook has $n$ users. Mark Zuckerberg decided that people are allowed to open groups under the following restrictions:

1) No two different groups can exactly the same participants.

2) The number of users in each group is even.

3) Every two group has an odd number of common users.

Denote by $m$ the maximal number of groups that can be formed in facebook under the restrictions mentioned above. Prove $m \leq n$.

I tried solving this by defined a matrix, multiplying it by its transpose and using some rank considerations I thought I could derive the bound, but I didn't succeed. Could you please give me a hint?

The question had anther subsection : prove that in the case that $n$ is even than we have stron inequality

Answer 1

Let $[n]=\{1,\ldots,n\}$ be the set of users, and let $\mathscr{G}\subseteq\wp([n])$ be the collection of groups. As leonbloy pointed out, we can use the classic problem to show that $|\mathscr{G}|\le n+1$. Suppose that $|\mathscr{G}|=n+1$. For each $G\in\mathscr{G}$ let $v_G$ be the vector associated with $G$; $v_G\cdot v_H=1$ for distinct $G,H\in\mathscr{G}$, while $v_G\cdot v_G=0$ for all $G\in\mathscr{G}$. (All arithmetic is done modulo $2$.) The $n+1$ vectors $v_G$ for $G\in\mathscr{G}$ must be linearly dependent, so there are scalars $c_G$ for $G\in\mathscr{G}$, not all $0$, such that $\sum_{G\in\mathscr{G}}c_Gv_G=0$. Then for each $H\in\mathscr{G}$ we have

$$0=v_H\cdot\sum_{G\in\mathscr{G}}c_Gv_G=\sum_{G\in\mathscr{G}\setminus\{H\}}c_G\;.$$

Let $H$ and $K$ be distinct members of $\mathscr{G}$; then

$$c_H-c_K=\sum_{G\in\mathscr{G}\setminus\{K\}}c_G-\sum_{G\in\mathscr{G}\setminus\{H\}}c_G=0\;,$$

so $c_H=c_K$, and we must have $c_G=1$ for all $G\in\mathscr{G}$.

Fix $H\in\mathscr{G}$; $\sum_{G\in\mathscr{G}\setminus\{H\}}1=0$, so $n$ is even. For each $G\in\mathscr{G}$ let $G\,'=[n]\setminus G$; $n$ and $|G|$ are even, so $|G'|$ is even. Moreover, if $G$ and $H$ are distinct members of $\mathscr{G}$, then

$$|G\,'\cap H'|=n-|G\cup H|=n-|G|-|H|+|G\cap H|$$

is odd. Let $\mathscr{G}'=\{G\,':G\in\mathscr{G}\}$; then $\mathscr{G}'$ satisfies the same conditions as $\mathscr{G}$, soby the same argument we must have $\sum_{G\in\mathscr{G}}v_{G\,'}=0$, where $v_{G\,'}$ is of course the vector corresponding to the set $G\,'$. But then

$$0=\sum_{G\in\mathscr{G}}v_G+\sum_{G\in\mathscr{G}}v_{G\,'}=\sum_{G\in\mathscr{G}}(v_G+v_{G\,'})=\sum_{G\in\mathscr{G}}\mathbf{1}\;,$$

where $\mathbf{1}=v_{[n]}$ is the vector of all ones, and it follows that $n+1=|\mathscr{G}|$ is even and hence that $n$ is odd. This is a contradiction, and it follows that $|\mathscr{G}|$ cannot be $n+1$: it must be at most $n$.

Answer 2

Lets call this (groups are even, intersection are odd) a "$(n,m)$ even/odd town".

By adding a dummy user to each group, we now have the classical "$(n+1,m)$ odd/even town" (groups are odd, intersection are even)

Then we get that $m\le n+1$

(Yes, this is slightly weaker than your inequality I'm noy sure if this can be improved - are you sure you got it right?)

Answer 3

Let $A$ be the $m\times n$ matrix whose rows correspond to groups, whose columns correspond to people, with a $1$ in an entry if that person is in that group, and $0$ otherwise. From now on, we will think of these entries as elements of $\mathbb Z/2\mathbb Z$. The conditions on even sizes/odd intersections then imply $$ AA^T\equiv J_m-I_m, $$ where $J_m$ is the $m\times m$ matrix filled with ones, and $I_m$ is the $m\times m$ identity matrix. Therefore, $$ \def\r{\text{rank }}\r A\ge \r AA^T=\r (J_m-I_m). $$ Furthermore, the matrix $A$ has a nontrivial kernel; letting $v$ be the $n\times 1$ column vector with all ones, then $Av\equiv{\bf 0}\pmod 2$, since each row has an even number of ones. This means $\r A\le n-1$, so that $$ \r (J_m-I_m)\le n-1 \tag{*} $$ Now, we need the following:

Lemma: $$\r (J_m-I_m)=\begin{cases}m & m \text{ is even}\\ m-1 & m \text{ is odd}.\end{cases}$$

Proof: When $m$ is even, we have $(J_m-I_m)^2\equiv (J_m)^2+(I_m)^2\equiv 0+I_m$, so that $J_m-I_m$ is invertible. When $m$ is odd, then $(J_m-I_m)w=0$, where $w$ is the $m\times 1$ vector of all ones. This proves $\r(J_m-I_m)\le m-1$; since the upper $(m-1)\times (m-1)$ submatrix is $J_{m-1}-I_{m-1}$, which was just shown to be invertible, the rank is indeed $m-1$. $\square$

In either case, we have $m-1\le \r(J_m-I_m)$, which combined with $(*)$ implies $m\le n$. This answers your first question. Furthermore, when $n$ is even, we cannot have $m=n$, otherwise we would have $\r(J_m-I_m)=\r(J_n-I_n)=n\not \le n-1$, contradicting $(*)$. Therefore, when $n$ is even, we can further conclude $m\le n-1$.