Combinatoria intersección de conjuntos de preguntas.

Question

Deje $ A_1,. . . , A_m $ y $ B_1,. . . , B_m $ serán subconjuntos de$[n]$ de manera que $ | A_i ∩ B_i | $ es impar para todos$i$ y $ | A_i ∩ B_j | $ es par para todos $ i \ neq j $. Demuestre que $ m ≤ n $.

He intentado usar la prueba por contradicción pero no el éxito. ¡Cualquier ayuda muy apreciada, gracias!

Answer 1

La pregunta parece que está pidiendo que se recrea como un problema de álgebra lineal. En el campo con dos elementos, $\mathbb F_2$, y el espacio vectorial $\mathbb F_2^n$.

Interpretar un subconjunto $X$ $[n]$ como el vector $x = (x_1, x_2, \ldots x_n)$ donde $x_i$ $1$ fib $i \in X$. Definir la habitual forma bilineal $\langle \cdot \rangle : \mathbb F_2^n \times \mathbb F_2^n \to \mathbb F_2$:

$$\langle x , y \rangle = \sum_{i=1}^n x_iy_i$$

Deje $X, Y \subseteq [n]$, y deje que sus correspondientes vectores en $\mathbb F_2^n$ $x$ $y$ respectivamente. A continuación, $|X \cap Y|$ es que aun si y sólo si $\langle x, y \rangle = 0$.

Considere ahora un determinado$A_1, \ldots, A_m$$B_1, \ldots, B_m$. Deje que sus correspondientes vectores de ser$a_1, \ldots, a_m$$b_1, \ldots, b_m$. Sabemos que para todos los $i,j$, $\langle a_i, b_j \rangle$ $1$ si $i=j$ $0$ lo contrario.

Reclamo: $(a_1, \ldots, a_m)$ es linealmente independiente.

Prueba: Supongamos que tenemos

$$s_1a_1 + s_2a_2 + \cdots + s_ma_m = 0$$

con cada una de las $s_i \in \mathbb F_2$. A continuación, aplicar la $\langle \cdot, b_i \rangle$ en ambos lados, obtenemos $s_i = 0$. Esto es válido para todas las $i$, y así la independencia lineal se ha establecido.

Ya que disponemos de un conjunto linealmente independiente del tamaño de la $m$ en un espacio vectorial de dimensión $n$, obtenemos $m \leq n$.