CUARENTENA Problema 8

[Mórtimer]

Sean $a$ y $b$ dos enteros positivos. Determinar el mayor valor de $n$ tal que existen conjuntos $A_1, A_2,..., A_n$ y $B_1, B_2,..., B_n$ tales que:\\
i) Los conjuntos $A_1, A_2,..., A_n$ tienen $a$ elementos cada uno.
ii) Los conjuntos $B_1, B_2,..., B_n$ tienen $b$ elementos cada uno.
iii) Para todos $1\leq i,j\leq n$, los conjuntos $A_i$ y $B_j$ son disjuntos si y sólo si $i=j$.

[Mórtimer]

Aquí publicaremos la solución oficial.

[enigma1234]

Spoiler: mostrar

Sea $X=A_1\cup A_2\cup...\cup A_n\cup B_1\cup B_2\cup...\cup B_n$. Sea $|X|=m$.
Decimos que un elemento $P$ aparece antes de $Q$ en una permutacion si al leerlo de izquierda a derecha $P$ aparece antes que $Q$.

Consideremos todas las permutaciones de los elementos de $X$ tal que todos los elementos de $A_i$ aparecen antes de todos los elementos de $B_i$. De las $m!$ permutaciones posibles solo fijamos los elementos que son de $A_i$ o $B_i$, si mantenemos fijos los demás al variar de posiciones los elementos de $A_i\cup B_i$ de orden habrá $a!b!$ de un total de $(a+b)!$ formas de poner los elementos de $A_i$ antes de todos los elementos de $B_i$. Entonces hay $\frac{m!a!b!}{(a+b)!}$ permutaciones de este tipo.

Ahora supongamos que una permutación donde todos los elementos de $A_i$ aparecen antes de todos los elementos de $B_i$ es igual a una permutación donde todos los elementos de $A_j$ aparecen antes de todos los elementos de $B_j$. Sea $x\in A_i\cap B_j$ y $y\in A_j\cap B_i$ estos existen por la definición de los conjuntos. Entonces en la permutación $x$ aparece antes de $y$ porque todos los elementos de $A_i$ aparecen antes de todos los elementos de $B_i$ pero $y$ aparece antes de $x$ porque todos los elementos de $A_j $ aparecen antes de todos los elementos de $B_i$ lo cual es una contradicción.

Por lo tanto todos las permutaciones son distintas, entonces en total:
$$m!\geq n\frac{m!a!b!}{(a+b)!}\to n\leq \binom{a+b}{a}$$

Ahora veamos que es posible que $n=\binom{a+b}{a}$. Sea $X$ un conjunto de $a+b$ elementos. Sea $A_1,A_2,...,A_n$ todos los subconjuntos de $a$ elementos de $X$ y sea $B_i=X-A_i$. Entonces si $A_i$ y $B_j$ son distintos $|A_i\cup B_j|=a+b$ y $A_i\cup B_j\subset X$ entonces $A_i\cup B_j=X\to B_j=B_i\to i=j$ . Entonces cumple lo pedido.

[jujumas]

Spoiler: mostrar

Sea $X=A_1\cup A_2\cup...\cup A_n\cup B_1\cup B_2\cup...\cup B_n$. Sea $|X|=m$.
Decimos que un elemento $P$ aparece antes de $Q$ en una permutacion si al leerlo de izquierda a derecha $P$ aparece antes que $Q$.

Consideremos todas las permutaciones de los elementos de $X$ tal que todos los elementos de $A_i$ aparecen antes de todos los elementos de $B_i$. De las $m!$ permutaciones posibles solo fijamos los elementos que son de $A_i$ o $B_i$, si mantenemos fijos los demás al variar de posiciones los elementos de $A_i\cup B_i$ de orden habrá $a!b!$ de un total de $(a+b)!$ formas de poner los elementos de $A_i$ antes de todos los elementos de $B_i$. Entonces hay $\frac{m!a!b!}{(a+b)!}$ permutaciones de este tipo.

Ahora supongamos que una permutación donde todos los elementos de $A_i$ aparecen antes de todos los elementos de $B_i$ es igual a una permutación donde todos los elementos de $A_j$ aparecen antes de todos los elementos de $B_j$. Sea $x\in A_i\cap B_j$ y $y\in A_j\cap B_i$ estos existen por la definición de los conjuntos. Entonces en la permutación $x$ aparece antes de $y$ porque todos los elementos de $A_i$ aparecen antes de todos los elementos de $B_i$ pero $y$ aparece antes de $x$ porque todos los elementos de $A_j $ aparecen antes de todos los elementos de $B_i$ lo cual es una contradicción.

Por lo tanto todos las permutaciones son distintas, entonces en total:
$$m!\geq n\frac{m!a!b!}{(a+b)!}\to n\leq \binom{a+b}{a}$$

Ahora veamos que es posible que $n=\binom{a+b}{a}$. Sea $X$ un conjunto de $a+b$ elementos. Sea $A_1,A_2,...,A_n$ todos los subconjuntos de $a$ elementos de $X$ y sea $B_i=X-A_i$. Entonces si $A_i$ y $B_j$ son distintos $|A_i\cup B_j|=a+b$ y $A_i\cup B_j\subset X$ entonces $A_i\cup B_j=X\to B_j=B_i\to i=j$ . Entonces cumple lo pedido.

Cuidado, $n$ y $m$ no tienen por qué ser finitos, y creo que lo estarías asumiendo. Salvo eso, muy linda la solución!