Entrenamiento Ibero 2019 P9

Problemas que aparecen en el Archivo de Enunciados.
Matías

OFO - Medalla de Bronce-OFO 2016 OFO - Medalla de Bronce-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años
OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 206
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 8
Nivel: 3

Entrenamiento Ibero 2019 P9

Mensaje sin leer por Matías »

Sea $X$ un conjunto con $n$ elementos. Probar que el número de pares $(A,B)$ tales que $A$, $B$ son subconjuntos de $X$, $A$ es un subconjunto de $B$ y $A\neq B$ es igual a $3^n-2^n$.
Avatar de Usuario
AgusBarreto

OFO - Medalla de Bronce-OFO 2015 OFO - Medalla de Bronce-OFO 2016 OFO - Jurado-OFO 2017 FOFO 7 años - Jurado-FOFO 7 años OFO - Jurado-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 COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022
Mensajes: 157
Registrado: Sab 15 Sep, 2012 6:28 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: San Martín, Buenos Aires

Re: Entrenamiento Ibero 2019 P9

Mensaje sin leer por AgusBarreto »

Spoiler: mostrar
Sin la condición de $A \neq B$ tenemos $3^n$ posibilidades, ya que cada uno de los $n$ elementos de $X$ puede:

1. No estar ni en $A$ ni en $B$
2. Estar en $B$ pero no en $A$
3. Estar en $A$

Ahora sólo queda restar las posibilidades en las que $A=B$, pero esas son $2^n$ pues cada uno de los $n$ elementos de $X$ puede:

1. Estar en $A=B$
2. No estar en $A=B$

Luego el total de posibilidades es $3^n-2^n$ como queríamos ver.■
2  
Responder