Segunda Ronda Regionales 2014 N2 P1

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
AgusBarreto

OFO - Medalla de Bronce OFO - Jurado FOFO 7 años - Jurado FOFO 8 años - Jurado FOFO Pascua 2019 - Jurado
Mensajes: 120
Registrado: Sab 15 Sep, 2012 6:28 pm
Medallas: 8
Nivel: Exolímpico
Ubicación: San Martín, Buenos Aires

Segunda Ronda Regionales 2014 N2 P1

Mensaje sin leer por AgusBarreto » Vie 12 Dic, 2014 1:16 pm

Sea [math] el conjunto de todos los divisores positivos de [math] (incluyendo a [math] y a [math]). Se consideran todos los subconjuntos de [math] que tienen exactamente [math] elementos. Llamamos grandes a los subconjuntos tales que la multiplicación de sus [math] elementos es mayor que [math] y llamamos pequeños a los subconjuntos tales que la multiplicación de sus [math] elementos es menor que [math].
Determinar si hay más conjuntos grandes o más conjuntos pequeños.
1  

Avatar de Usuario
Turko Arias

Colaborador OFO - Medalla de Plata OFO - Medalla de Oro FOFO Pascua 2019 - Medalla
Mensajes: 343
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 4
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: Segunda Ronda Regionales 2014 N2 P1

Mensaje sin leer por Turko Arias » Lun 15 Dic, 2014 8:40 pm

Spoiler: mostrar
Tomamos un conjunto pequeño cualquiera [math] y le asignamos el nuevo conjunto [math]. Notamos que si [math] entonces [math], ademas es claro que si [math] es divisor de [math] entonces [math] también lo es, luego [math] es un conjunto grande. Se ve fácil que si [math] y [math] difieren en al menos un elemento entonces sus respectivos conjuntos asignados también van a diferir. Luego a conjuntos distintos se les asignan conjuntos distintos. Como a cada conjunto pequeño le asignamos un conjunto grande podemos afirmar que, siendo [math] la cantidad de conjuntos pequeños y [math] la cantidad de conjuntos grandes, [math]. Consideramos ahora el conjunto [math] que es grande, vemos que si a un conjunto [math] pequeño se le asigna el conjunto grande [math] mediante nuestro método entonces a partir del conjunto [math] se puede volver a obtener [math] mediante nuestro método, ahora tomamos a [math] y le aplicamos el método y vemos que el conjunto que obtenemos es el mismo, luego encontramos un conjunto grande que no es el asignado a ningún pequeño, por ende [math] y terminó.
Un comentario
Spoiler: mostrar
Lo que estamos haciendo es hacer una inyección entre los pequeños y los grandes, y demostrar que no es una sobreyección por lo tanto el conjunto de llegada tiene más elementos que el de partida.

Avatar de Usuario
Vladislao

Colaborador OFO - Jurado FOFO 6 años - Jurado FOFO Pascua 2017 - Jurado
Mensajes: 809
Registrado: Mar 28 Dic, 2010 3:26 pm
Medallas: 6
Nivel: Exolímpico
Ubicación: Córdoba

Re: Segunda Ronda Regionales 2014 N2 P1

Mensaje sin leer por Vladislao » Lun 15 Dic, 2014 9:16 pm

Agrego que lo que muchos hicieron (y no está mal, sólo que no es lo ideal) es contar cuántos conjuntos grandes y cuántos pequeños hay.

Esa cuenta creo que da:
Spoiler: mostrar
97 pequeños y 113 grandes.
Sea [math] Para todo entero positivo [math] se cumple que [math] es un número primo.

Avatar de Usuario
Tomás Morcos Porras
Mensajes: 24
Registrado: Dom 13 Oct, 2019 5:04 pm
Nivel: 2
Ubicación: Córdoba, Córdoba

Re: Segunda Ronda Regionales 2014 N2 P1

Mensaje sin leer por Tomás Morcos Porras » Sab 08 Feb, 2020 3:14 am

Spoiler: mostrar
$S=\{1, 2, 3, 4, 6, 8, 12, 16, 24, 48\}$ y llamamos $S_i$ al elemento de $S$ en el lugar $i$. Como hay $10$ elementos, $S_i$ tiene una contraparte $S_j=S_{11-i}$ y se da que $S_i\times S_j=48$. Defino también $T_x=\{S_a,S_b,S_c,S_d\}$ y $T_y$ al conjunto integrado por las contrapartes de los cuatro elementos de $T_x$.
Vemos que, si $S_i=2^{n_i}\times 3^{m_i}$, se da que $S_{11-i}=2^{4-n_i}\times 3^{1-m_i}$ porque $S_i=\frac{2^4\times 3^1}{S_1}$.
Vemos también que $2^{11}>2014>2^{10}$.
Sean ahora $\alpha_x$ y $\beta_x$ enteros tales que se cumpla: $S_a\times S_b\times S_c\times S_d=2^{\alpha_x}\times 3^{\beta_x}$, y $2\leq\alpha_x\leq14$ y $0\leq\beta_x\leq4$.
Sabemos que $n_a+n_b+n_c+n_d=\alpha_x$, por lo que:
$4-n_a+4-n_b+4-n_c+4-n_d=\alpha_y$
$16-(n_a+n_b+n_c+n_d)=\alpha_y$
$16-\alpha_x=\alpha_y$
De la misma forma, $4-\beta_x=\beta_y$.
Ahora, demuestro por absurdo que $T_x$ y $T_y$ no pueden ser ambos pequeños con tres casos:
Spoiler: mostrar
*$\alpha_x=8$, $\alpha_y=8$

$\frac{2014}{2^8}<3^2$

$\beta_x+\beta_y<4$
Absurdo.


*$\alpha_x=9$, $\alpha_y=7$

$\frac{2014}{2^9}<3^2$

$\frac{2014}{2^7}<3^3$

$\beta_x+\beta_y<4$
Absurdo.


*$\alpha_x=10$, $\alpha_y=6$

$\frac{2014}{2^{10}}<3^1$

$\frac{2014}{2^6}<3^4$

$\beta_x+\beta_y<4$
Absurdo.
Para terminar la prueba, voy a indicar que si $S_b=S_{11-a}$ y $S_d=S_{11-c}$, entonces $T_x=T_y$ y ambos son grandes.

Queda demostrado que, para todo conjunto pequeño, su contraparte es un conjunto grande y hay, por lo menos, $10$ subconjuntos de $S$ que son grandes y tienen contraparte grande, por lo que, necesariamente, hay más conjuntos grandes que pequeños.
Puede que no me reconozcas, pero a lo mejor te suene la cara de un joven que creyó encontrar un ciclo hamiltoniano en el grafo de Petersen, y no satisfecho con creerlo corroborado, subió a un escenario a intentar demostrarlo. Ese soy yo 8-)

Responder