0
$\begingroup$

We've been told that a set $T$ is called even if it has even number of elements. Letting $n$ be a positive even integer, and letting $S_1, S_2, \dots, S_n$ be even subsets of the set $S = ${$1,2,\dots,n$}, I am trying to find a way to prove that there exist $i$ and $j$, $1 \leq i < j \leq n$, such that $S_i \cap S_j$ is even. If anyone might be able to help with general guidance on how to conceptualize this problem to get started on a proof, I would greatly appreciate it! I am thinking there might be a way to prove it using matrices, but I'm not positive... Thanks!

$\endgroup$
1
  • 2
    $\begingroup$ You're more likely to get a response on this site if you tell people what you think about the problem, what you've tried, where you're confused, where you heard the problem, etc. People don't like being commanded to prove something. $\endgroup$ Mar 6 '15 at 3:50
2
$\begingroup$

For $k=1,\ldots,n$ let $v_k\in\Bbb F_2^n$ be the incidence vector for $S_k$: $v_k$ is an $n$-place binary vector with a $1$ in the $i$-th component if and only if $i\in S_k$. All of my arithmetic will be modulo $2$.

Suppose that $S_k\cap S_\ell$ is odd whenever $1\le k<\ell\le n$; then $v_k\cdot v_\ell=1$ whenever $1\le k<\ell\le n$, and $v_k\cdot v_k=0$. Suppose that $\sum_{k=1}^n\alpha_kv_k=\mathbf{0}$, where $\alpha_k\in\Bbb F_2$ for $k=1,\ldots,n$, and $\mathbf{0}$ is the zero vector in $\Bbb F_2^n$. For each $j\in\{1,\ldots,n\}$ we have

$$0=v_j\cdot\mathbf{0}=v_j\cdot\sum_{k=1}^n\alpha_kv_k=\sum_{{1\le k\le n}\atop{k\ne j}}\alpha_k\;.$$

Thus, if $1\le k<\ell\le n$, we have

$$\alpha_k-\alpha_\ell=\sum_{{1\le j\le n}\atop{j\ne\ell}}\alpha_j-\sum_{{1\le j\le n}\atop{j\ne k}}\alpha_j=0\;,$$

and either $\alpha_k=0$ for $k=1,\ldots,n$, or $\alpha_k=1$ for $k=1,\ldots,n$.

Suppose that $\alpha_k=1$ for $k=1,\ldots,n$, so that $\sum_{k=1}^nv_k=\mathbf{0}$. Then

$$0=v_1\cdot\mathbf{0}=v_1\cdot\sum_{k=1}^nv_k=\sum_{k=2}^n1=n-1=1\;,$$

which is absurd. (Recall that all arithmetic here is modulo $2$.) Thus, $\alpha_k=0$ for $k=1,\ldots,n$, and $\{v_1,\ldots,v_n\}$ is linearly independent.

Let $v=\sum_{k=1}^nv_k\ne\mathbf{0}$, and let $S\subseteq\{1,\ldots,n\}$ have $v$ as its incidence vector. For $j\in\{1,\ldots,n\}$ we have

$$v_j\cdot v=\sum_{k=1}^nv_j\cdot v_k=n-1=1\;,$$

so $S_j\cap S$ is odd. Now finish deriving a contradiction as follows:

  • Show that $S$ is even.
  • Show that $S\notin\{S_1,\ldots,S_n\}$.
  • Conclude that $\{S,S_1,\ldots,S_n\}$ is a set of $n+1$ even subsets of $\{1,\ldots,n\}$ whose pairwise intersections are all odd, which is impossible.
$\endgroup$
3
  • $\begingroup$ $0 = 1$, that is absurd! That is way more work than I'd hoped would be necessary, I'd been toying with hypercubes for this question but haven't really got anywhere. Kudos! $\endgroup$
    – pjs36
    Mar 7 '15 at 4:50
  • $\begingroup$ @pjs36: Thanks! I have to admit that it took quite a while for the pieces to fall into place. $\endgroup$ Mar 7 '15 at 4:52
  • $\begingroup$ This solution illustrates that the problem is equivalent to the harder (i.e. $n$ even) half of Putnam 2011 problem A4. $\endgroup$ Aug 3 '20 at 21:07
0
$\begingroup$

Suppose by way of contradiction that all intersections are odd.

Let $A$ be the $n× n$ matrix whose rows are the indicator vectors for the subsets; that is, $A_{i,j}=1$ when $j∈ S_i$, zero otherwise. Think of the entries as integers modulo $2$.

Let $I$ be the $n×n$ identify matrix, and let $J$ be the $n× n$ matrix with all ones. The condition on even sizes and assumption on odd intersections implies $$ AA^T = J-I $$ Furthermore, $J-I$ is invertible mod $2$, since $(J-I)^2\equiv J^2 + I^2\equiv 0+I\pmod 2$. Therefore, we have $$ n\ge\def\r{\text{rank }}\r A \ge \r AA^T = \r J-I = n, $$ so $\r A=n$. However, letting $\def\one{{\bf 1}}\one$ be the $n× 1$ column vector of all ones, then $A\one={\bf 0}$, since each row has an even number of ones. Having a nonzero vector in the kernel of $A$ contradicts $\r A=n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy