Iberoamericana 2013 - Problema 1

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Caro - V3

Colaborador-Varias OFO - Jurado-OFO 2015
Mensajes: 358
Registrado: Sab 16 Oct, 2010 4:20 pm
Medallas: 2
Nivel: Exolímpico

Iberoamericana 2013 - Problema 1

Mensaje sin leer por Caro - V3 » Mar 24 Sep, 2013 4:42 pm

Un conjunto [math] de enteros positivos distintos se llama canalero si para cualesquiera tres números [math], todos diferentes, se cumple que [math] divide a [math], [math] divide a [math] y [math] divide a [math].
a) Demostrar que para cualquier conjunto finito de enteros positivos [math] existen infinitos enteros positivos [math], tales que el conjunto [math] es canalero.
b) Demostrar que para cualquier entero [math] existe un conjunto canalero que tiene exactamente [math] elementos y ningún entero mayor que [math] divide a todos sus elementos.
Guía de [math]: sirve para escribir ecuaciones como [math]

Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020
Mensajes: 991
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 7
Nivel: Exolímpico

Re: Iberoamericana 2013 - Problema 1

Mensaje sin leer por Matías V5 » Mar 24 Sep, 2013 8:13 pm

Para la parte a):
Spoiler: mostrar
Basta tomar cualquier [math] que sea divisible por todos los [math]. Veamos que funciona: si [math] son tres índices distintos en el conjunto [math], entonces [math], lo cual ocurre pues de hecho [math]. Análogamente se ve que vale con las otras permutaciones de [math].
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore!

Numberblocks - https://www.youtube.com/watch?v=SoRiOoqao5Y

Avatar de Usuario
Ivan

Colaborador-Varias
Mensajes: 1021
Registrado: Vie 15 Oct, 2010 7:18 pm
Medallas: 1
Nivel: Exolímpico

Re: Iberoamericana 2013 - Problema 1

Mensaje sin leer por Ivan » Mar 24 Sep, 2013 8:17 pm

Para la parte b):
Spoiler: mostrar
Sean [math] primos distintos. Llamemos [math]. Es fácil ver que [math] cumple lo pedido.
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)

tuvie

Colaborador-Varias OFO - Medalla de Oro-OFO 2015 OFO - Medalla de Oro-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años 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
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020
Mensajes: 607
Registrado: Dom 09 Sep, 2012 11:58 am
Medallas: 12
Nivel: Exolímpico

Re: Iberoamericana 2013 - Problema 1

Mensaje sin leer por tuvie » Mar 24 Sep, 2013 8:27 pm

a)
Spoiler: mostrar
Notemos que en el nuevo conjunto debe ocurrir que [math] para todo [math] en el conjunto considerado. Una condición para que pase esto es que [math] para todo [math]. Entonces tenemos que [math]. Entonces [math], pero si tomamos un múltiplo de éste [math], entonces sigue funcionando, pues un número divide a todos sus múltiplos, y como en esta construcción se pueden utilizar todos los múltiplos, sigue que hay infinitos [math], como queríamos demostrar.
b)
Spoiler: mostrar
Sea [math] el i-ésimo número primo. Sean [math] los elementos del conjunto que nos vamos a armar. Definamosnos a [math]. Veamos que efectivamente funciona, pues ningún primo divide a todos los elementos, y además, al agarrar a un [math] y a un [math] arbitrario, supongamos que no existe un [math] tal que [math]. En la factorización en primos de [math] aparecen todos los primos de [math] menos [math], pero como el primo que le falta a [math] no puede ser el que le falta a [math] ni el que le falta a [math], por como nos definimos la sucesión, sigue que [math] tiene ese primo faltante y se cumple la condición, como queríamos demostrar.
EDIT: creo que es lo mismo que subieron @Ivan y @Matías V5

ktc123

OFO - Medalla de Plata-OFO 2015 OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Bronce-OFO 2017 OFO - Mención-OFO 2019 OFO - Medalla de Plata-OFO 2020
Mensajes: 204
Registrado: Jue 21 Jun, 2012 9:09 pm
Medallas: 5
Nivel: Exolímpico
Ubicación: La Plata, Buenos Aires

Re: Iberoamericana 2013 - Problema 1

Mensaje sin leer por ktc123 » Jue 26 Sep, 2013 5:47 pm

Otro ejemplo bastante parecido para el b)
Spoiler: mostrar
Consideremos los primeros [math] primos [math]. Sabemos que la cantidad de formas de seleccionar [math] de ellos tal que todos los primos seleccionados sean distintos es [math]. Entonces para formar un conjunto canalero tenemos que un elemento es [math] y los restantes [math] elementos son cada uno, el producto de todos los primos de cada conjunto en donde hay [math] primos distintos. Así ningún primo aparece en la factorización de todos los números y siempre se cumple la condición del enunciado
¨Todos somos muy ignorantes. Lo que ocurre es que no todos ignoramos las mismas cosas¨

Ricardouch

OFO - Medalla de Bronce-OFO 2016
Mensajes: 5
Registrado: Sab 16 Ene, 2016 10:51 am
Medallas: 1
Nivel: 1

Re: Iberoamericana 2013 - Problema 1

Mensaje sin leer por Ricardouch » Sab 16 Ene, 2016 1:25 pm

Parte a)
Spoiler: mostrar
Sea el conjunto [math] un conjunto cualesquiera. Probaremos que basta con tomar [math], donde [math] es un entero, para probar lo que nos pide el problema. En efecto sean [math] índices arbitrarios distintos entre si. Probaremos que el conjunto [math] es canalero. Notemos que [math], y como [math] divide a [math] entonces definitivamente dicho conjunto es canalero (las otras dos comparaciones son obvias, pues [math] son arbitrarios).
Parte b)
Spoiler: mostrar
Para cada entero positivo [math] sea [math] el [math]-ésimo número primo. Sea el conjunto R =[math] y para cada entero positivo [math] sea [math] =[math][math] entre [math] . En efecto sean [math] índices arbitrarios notemos que [math] [math] [math] [math] [math] [math] [math] [math] ([math]) [math] lo cual obviamente es cierto(Las otras dos comparaciones son obvios pues e,f,g son arbitrarios ) por lo que el conjunto R es canalero además es fácil notar que el Máximo común divisor de todos los elementos de R es 1.

Hernan26

OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020
COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 23
Registrado: Sab 08 Dic, 2018 5:51 pm
Medallas: 6
Nivel: 3
Ubicación: Uruguay

Re: Iberoamericana 2013 - Problema 1

Mensaje sin leer por Hernan26 » Lun 12 Oct, 2020 3:18 pm

¿Funciona esto?
b)
Spoiler: mostrar
Para $n=3$ tenemos que $\{2,3,6\}$ es canalero y el $MCD$ de los $3$ números es $1$.
Supongamos que tenemos un conjunto $H=\{a_1,a_2,..., a_n\}$ que es canalero y tal que $MCD\{a_1,a_2\}=1$.
Consideremos el conjunto $T=\{a_1,pa_1,pa_2,..., pa_{n}\}$ con $p$ un primo mayor que todos los elementos de $H$.
Tenemos $3$ casos:
- $a_1| p^2 a_i a_j$ con $1\leq i,j\leq n$ que se cumple porque $H$ era canalero.
- $pa_i|p^2 a_j a_k$ con $1\leq i,j,k\leq n$ que se cumple porque $H$ era canalero.
- $pa_i|p a_j a_1$ con $1\leq i,j\leq n$ que se cumple porque $H$ era canalero.

Luego, $T$ es canalero. Además, $MCD\{a_1,pa_2\}=1$.
Por inducción, el caso base lo tenemos para $n=3$ y el paso inductivo es pasar del conjunto $H$ al $T$, por lo que, probamos la parte b.

Responder