CUARENTENA Problema 8

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
CUARENTENA
Mensajes: 33
Registrado: Mié 25 Mar, 2020 11:48 am
Nivel: Otro

CUARENTENA Problema 8

Mensaje sin leer por CUARENTENA »

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$.

Avatar de Usuario
CUARENTENA
Mensajes: 33
Registrado: Mié 25 Mar, 2020 11:48 am
Nivel: Otro

Re: CUARENTENA Problema 8

Mensaje sin leer por CUARENTENA »

Aquí publicaremos la solución oficial.

Avatar de Usuario
enigma1234

OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2020 - Copa-FOFO Pascua 2020
Mensajes: 107
Registrado: Sab 03 Jun, 2017 8:07 pm
Medallas: 4
Nivel: 2

Re: CUARENTENA Problema 8

Mensaje sin leer por 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.

1  

jujumas

OFO - Mención-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Oro perfecto-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017
FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
FOFO 9 años - Jurado-FOFO 9 años OFO - Jurado-OFO 2020 COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 401
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 13
Nivel: Exolímpico

Re: CUARENTENA Problema 8

Mensaje sin leer por jujumas »

enigma1234 escribió:
Mié 22 Abr, 2020 7:48 pm
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!
1  

Responder