Entrenamiento IMO 2021 - Problema 71

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Tomás Morcos Porras

COFFEE - Mención-COFFEE Matías Saucedo OFO - Mención-OFO 2020 COFFEE - Mención-COFFEE Iván Sadofschi FOFO 10 años - Mención-FOFO 10 años OFO - Medalla de Bronce-OFO 2021
OFO - Medalla de Bronce-OFO 2022
Mensajes: 202
Registrado: Dom 13 Oct, 2019 5:04 pm
Medallas: 6
Nivel: 3
Ubicación: Córdoba, Córdoba

Entrenamiento IMO 2021 - Problema 71

Mensaje sin leer por Tomás Morcos Porras »

Sean $m, k$ enteros positivos, $k<m$ y $M$ un conjunto de $m$ elementos. Demostrar que el número máximo de subconjuntos $A_1, A_2, ..., A_p$ de $M$ para los cuales $A_i\cap A_j$ tiene a lo sumo $k$ elementos, para todo $1\leq i<j\leq p$, es igual a $$P={m\choose 0}+{m\choose 1}+{m\choose 2}+...+{m\choose k+1}.$$
¿Mis intereses? Las várices de Winston Churchill.
usuario250

OFO - Jurado-OFO 2015
Mensajes: 236
Registrado: Vie 30 Dic, 2011 12:30 pm
Medallas: 1

Re: Entrenamiento IMO 2021 - Problema 71

Mensaje sin leer por usuario250 »

dos partes:
obtener un ejemplo con P subconjuntos:
Spoiler: mostrar
queda de ejercicio para el lector
demostrar que no se puede con más de P subconjuntos:
Spoiler: mostrar
No entra en el margen de la hoja, por lo que no lo podré postear
1  
Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021 OFO - Jurado-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 269
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 11
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Re: Entrenamiento IMO 2021 - Problema 71

Mensaje sin leer por Fedex »

Spoiler: mostrar
Sean $h$ la cantidad de subconjuntos $S$ elegidos con $|S| \leq k$ notar que:
$$h \leq \sum_{i=0}^{k} \binom{m}{i}$$
Ahora sean $B_1, B_2, \cdots, B_j$ aquellos subconjuntos elegidos con $|B_i| \geq k+1$ notar que cada subconjunto de $M$ con $k+1$ elementos puede aparecer contado a lo sumo $1$ vez en $\sum_{i=1}^{j} \binom{|B_i|}{k+1}$ luego:
$$j \leq \sum_{i=1}^{j} \binom{|B_i|}{k+1} \leq \binom{m}{k+1}$$
$$p = h + j \leq \sum_{i=0}^{k+1} \binom{m}{i}$$
Donde el ejemplo se tiene tomando todos los subconjuntos $A_i$ de $M$ con $|A_{i}| \leq k+1$.
1  
This homie really did 1 at P6 and dipped.
usuario250

OFO - Jurado-OFO 2015
Mensajes: 236
Registrado: Vie 30 Dic, 2011 12:30 pm
Medallas: 1

Re: Entrenamiento IMO 2021 - Problema 71

Mensaje sin leer por usuario250 »

Muy buena solución.
Fedex escribió: Mar 26 Jul, 2022 2:53 pm
Spoiler: mostrar
Sean $h$ la cantidad de subconjuntos $S$ elegidos con $|S| \leq k$ notar que:
$$h \leq \sum_{i=0}^{k} \binom{m}{i}$$
Ahora sean $B_1, B_2, \cdots, B_j$ aquellos subconjuntos elegidos con $|B_i| \geq k+1$ notar que cada subconjunto de $M$ con $k+1$ elementos puede aparecer contado a lo sumo $1$ vez en $\sum_{i=1}^{j} \binom{|B_i|}{k+1}$ luego:
$$j \leq \sum_{i=1}^{j} \binom{|B_i|}{k+1} \leq \binom{m}{k+1}$$
$$p = h + j \leq \sum_{i=0}^{k+1} \binom{m}{i}$$
Donde el ejemplo se tiene tomando todos los subconjuntos $A_i$ de $M$ con $|A_{i}| \leq k+1$.
1  
Responder