Problema 4 Cono Sur 2018

jujumas

OFO - Mención OFO - Medalla de Plata FOFO 7 años - Medalla Especial OFO - Oro perfecto FOFO Pascua 2017 - Medalla
OFO - Medalla de Oro
Mensajes: 342
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 7
Nivel: 2

Problema 4 Cono Sur 2018

Mensaje sin leer por jujumas » Dom 26 Ago, 2018 1:26 pm

Para cada entero $n \geq 4$, se consideran $m$ subconjuntos $A_1$, $A_2$, $A_3$, $\ldots$, $A_m$ de $ \{1, 2, 3, \ldots, n\}\ $ tales que:
$A_1$ tiene un elemento
$A_2$ tiene dos elementos
$\vdots$
$A_m$ tiene $m$ elementos
y ninguno de estos subconjuntos está incluido en otro.
Encontrar el mayor valor posible de $m$.

Heibor

OFO - Medalla de Bronce FOFO Pascua 2017 - Mención FOFO 7 años - Mención Especial
Mensajes: 17
Registrado: Mar 22 Sep, 2015 2:36 pm
Medallas: 4
Nivel: Exolímpico

Re: Problema 4 Cono Sur 2018

Mensaje sin leer por Heibor » Dom 26 Ago, 2018 4:45 pm

Spoiler: mostrar
Sea $A_1=1$, entonces $1$ no puede estar en ningún otro subconjunto.
Supongamos que para $m=n-1$ se puede, entonces $A_{n-1}$ contiene a todos los números menos el $1$, pero como $n>3$, $A_2$ esta incluido en $A_{n-1}$, por ende $m<n-1$
Veamos que para $m=n-2$ siempre se puede:
Los primeros $(n+1)/2$ (división entera) subconjuntos exceptuando $A_1$, serán de la forma:
$A_i={2,4,6,...,2(i-1),2(i-1)+1}$
Ahora defino los subconjuntos empezando por $A_{n-2}$ hasta $A_{(n-2)-(n+1)/2}$
Por comodidad sea $B_i=A_{n-2-i}$
$B_i=2,4,6,...,2i,2i+3,2i+4,...,n$
Para $n-2$, esto es $A_{n-2}={3,4,5,...,n-1,n}$
Es fácil ver que anda.

Responder