El problema del MO de los Balcanes

Question

Deje que $S = \{A_1,A_2, \ldots ,A_k\}$ ser una colección de subconjuntos de un $n$ -elemento establecido $A$ . Si para cualquier dos elementos $x, y \in A$ hay un subconjunto $A_i \in S$ que contiene exactamente uno de los dos elementos $x, y$ probar que $2^k \geq n$ .

Esta es una pregunta del MO de los Balcanes de 1997, y no entendí bien la pregunta, así que no pude hacer ningún intento. Por favor, ayúdeme.

Answer 1

Usted tiene un conjunto $A$ con $n$ elementos.

Luego hay una colección de $k$ establece $\{A_1,\ldots,A_k\}$ cada uno de los cuales es un subconjunto de $A$ Es decir, $A_i \subseteq A$ para $1 \leq i \leq k$ . Es necesario demostrar que

Si para cualquier par $x,y \in A$ hay un conjunto $A_i$ que distingue entre $x$ y $y$ (es decir, contiene exactamente uno de ellos), entonces hay muchos conjuntos $A_i$ , a saber $2^k \geq n$ .

Por ejemplo, para $A = \{1,2,3,4,5\}$ y $A_1 = \{1,2\}, A_2 = \{2,3,4\}$ tenemos que $A_1$ distingue entre $2$ y $3$ pero no entre $3$ y $4$ . De hecho, ningún conjunto distingue entre $3$ y $4$ .

Otro ejemplo podría ser $A = \{1,2,3,4\}$ y $A_1 = \{1,2\}$ y $A_2 = \{1,3\}$ . En este contexto, cada par de elementos $x,y \in A$ es distinguible por conjuntos $A_1,A_2$ y de hecho $2^2 \geq 4$ .

Una pista:

Considere la función $f : A \to \mathbb{N}$ dado por \begin{align} f(a) = 1\cdot\chi_{A_1}(a) + 2\cdot\chi_{A_2}(a) + 4\cdot\chi_{A_3} + \ldots + 2^{k-1}\cdot\chi_{A_k}(a), \end{align} donde $\chi_{A_i}(x)$ es el función característica de $A_i$ es decir \begin{align} \chi_{A_i}(x) = \begin{cases} 1 &\text{ if }x \in A_i,\\0&\text{ otherwise.}\end{cases}\end{align} Obsérvese que para cualquier elemento $a \in A$ tenemos $0 \leq f(a) \leq 2^k-1$ .

Solución:

En otras palabras, si $n > 2^k$ entonces hay dos elementos $x$ y $y$ tal que $f(x) = f(y)$ . Esto implica a su vez que $\chi_{A_i}(x) = \chi_{A_j}(y)$ para cualquier $1 \leq i,j \leq k$ Así que no $A_i$ distingue estos dos elementos.

Espero que esto ayude $\ddot\smile$

Answer 2

Aquí hay una reformulación: dejemos $S=\{A_1,\ldots,A_k\}$ sea una colección de subconjuntos de un $n$ -conjunto de elementos $A.$ Dejemos que $x,$ $y$ sea un par de elementos de $A.$ Diremos que $S$ tiene el Propiedad XOR para $(x,y)$ si al menos un elemento de $S$ contiene sólo uno de $x,$ $y.$ En otras palabras, $S$ no tendría la propiedad XOR para $x,$ $y$ si cada elemento de $S$ contenía ambos $x$ y $y$ o ninguno de los dos $x$ ni $y.$

La pregunta le pide que demuestre que si $S$ tiene la propiedad XOR para todos los pares de elementos de $A,$ entonces $S$ no puede ser demasiado pequeño. En particular, $S$ debe consistir en al menos $\log_2 n$ subconjuntos de $A.$

Answer 3

Pues aquí otra formulación de la solución. Mira el álgebra booliana generada por $A_i$ . Esta álgebra tiene como máximo $2^k$ átomos. Ahora observemos que los átomos son exactamente los subconjuntos de $A$ .