FOFO 7 años Problema 6

Avatar de Usuario
AgusBarreto

OFO - Medalla de Bronce OFO - Jurado
Mensajes: 86
Registrado: Sab 15 Sep, 2012 6:28 pm
Medallas: 3
Nivel: Exolímpico
Ubicación: San Martín, Buenos Aires

FOFO 7 años Problema 6

Mensaje sin leer por AgusBarreto » Vie 13 Oct, 2017 2:58 pm

Una permutación del conjunto [math] es una sucesión [math] tal que cada elemento de [math] aparece exactamente una vez como un termino de la sucesión. Por ejemplo, [math] es una permutación [math]. Sea [math] la cantidad de permutaciones de [math] para las cuales [math] es un cuadrado perfecto para todo [math]. Hallar el menor entero positivo [math] tal que [math]

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial
Mensajes: 417
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario

Re: FOFO 7 años Problema 6

Mensaje sin leer por Gianni De Rico » Mar 17 Oct, 2017 9:59 am

Spoiler: mostrar
Notemos que [math], ya que cuando los números aparecen en orden creciente [math].
Entonces tenemos que [math] (*)
Digo que una permutación es válida si cumple que [math] es un cuadrado perfecto para todo [math]

Lema:
Dada una permutación válida, [math] números pueden cambiarse entre ellos de lugar y que la permutación resultante sea válida si y sólo si esos números son todos cuadrados o todos (en orden creciente) de la forma [math], es decir, cada uno de los números es el producto de un número por un cuadrado. Siendo [math] el [math] del conjunto.

Demostración:
La ida se ve fácil ya que el producto de dos cuadrados es un cuadrado, si [math] es un cuadrado, entonces [math] es un cuadrado y si [math] es un cuadrado, entonces [math] es un cuadrado. Para la vuelta, supongamos que los números que pueden cambiar manteniendo una permutación válida son de la forma [math] y [math], tenemos entonces que [math] es un cuadrado y que [math] es un cuadrado, pero entonces [math] es un cuadrado.

Esto nos dice que [math] (**). Por (*) tenemos que [math], como [math] es primo, entonces necesitamos una permutación válida que pueda permutarse una cantidad de veces múltiplo de [math]. Como queremos el mínimo, entonces esa cantidad tiene que ser [math].
Por lo tanto, lo que buscamos es un número que puede cambiarse de lugar con [math] números menores (por el lema sabemos que si [math] puede cambiarse con [math] y [math] puede cambiarse con [math], entonces [math] puede cambiarse con [math]).

Por el lema sabemos que los números tienen que ser todos cuadrados o todos productos de cuadrados por un número. El número [math] tiene [math] cuadrados menores que él, por lo que puede cambiarse con cada uno de ellos, y claramente es el menor de los que son todos cuadrados. Ahora veamos que es el mínimo:
Sea [math] un entero positivo y [math] un cuadrado para todo [math] ([math] puede o no ser igual a [math]). Sean [math] [math] los términos intercambiables, tenemos entonces [math], siendo [math]. En particular, [math], como queremos que [math] sea mínimo, entonces [math]. Ahora, se ve fácilmente que [math], [math], [math], [math], [math]. Entonces como queremos que [math], el [math] puede aparecer como mucho [math] veces, el [math] como mucho [math] veces, el [math] como mucho [math] veces, el [math] como mucho [math] veces y cualquier número del [math] en adelante como mucho [math] veces. Consultando la Criba de Eratóstenes (o tabla de números primos), vemos que hay [math] primos menores a [math], si descontamos a [math] tenemos [math] que aparecerán a lo sumo [math] veces en el productorio (en realidad, hay varios que no pueden aparecer juntos, por ejemplo [math] y [math], pero no importa), por lo tanto tendremos a lo sumo [math] términos en el productorio, pero éste tiene [math] términos. Absurdo.
El absurdo provino de suponer que existía un número menor que [math] tal que multiplicado por [math] números menores fuese siempre un cuadrado, entonces, [math] es el menor de ellos.

Comprobando a mano las [math] permutaciones de [math] vemos que [math], por (**) tenemos que [math], entonces [math]

Queda demostrado que el menor entero positivo que cumple es [math]
[math]

Avatar de Usuario
Violeta

OFO - Mención FOFO 7 años - Medalla Especial
Mensajes: 323
Registrado: Sab 04 Jun, 2016 11:50 pm
Medallas: 2
Ubicación: Puerto Rico

Re: FOFO 7 años Problema 6

Mensaje sin leer por Violeta » Mié 18 Oct, 2017 1:14 pm

Spoiler: mostrar
Afirmamos que el menor entero es [math].

Consideremos los conjuntos [math], donde [math] es un número de la forma [math], donde los [math] son primos (incluimos los valores de primos y el [math] también). *Siempre que mencionemos [math] de aquí en adelante nos referimos a un número de esa forma*

Ahora, varios hechos sobre los [math].

0. Todo entero está en un [math].

Demostración: Trivial.

1. Dos números tienen como producto un cuadrado perfecto sii están en el mismo [math].

Demostración: El "si" es trivial. Probaremos el "solo si". Asumamos que hay dos números [math] y [math] en distintos [math] con producto de cuadrado perfecto. Digamos [math] y [math]. Entonces [math] tiene que ser un cuadrado perfecto, que es absurdo porque hay por lo menos un primo [math] que está en uno de los dos números y no en el otro, porque [math] y [math] son distintos. Como este primo [math] tiene exponente impar, [math] no es cuadrado perfecto, de donde se llega al absurdo y [math].

2. No hay dos [math]s con un término en común.

Demostración: Asumamos que hay tres númeroz [math] con [math] en [math] pero no en [math], [math] en [math] pero no en [math] (vemos que estos existen porque el primer elemento del conjunto [math] es [math] y [math]) y [math] en ambos. Como consecuencia de (1), [math] y [math] son cuadrados perfectos, de donde [math] es un cuadrado perfecto. Pero entonces, por (2), [math]. Absurdo.

3. Si [math] es la cantidad de elementos de [math] que son menores que [math], pues [math]

Demostración: [math] es sabido que es la cantidad de números menores que [math] divisiables por [math]. Si tomamos la raíz cuadrado y función piso de esa cantidad, pues tenemos la cantidad de números menores que [math] divisibles por [math] que están multiplicados por un cuadrado perfecto.

4. [math]

Demostración: Consederemos conjuntos [math] con todos los elementos de [math] menores o iguales que [math]. Ahora consideremos permutaciones [math] de estos conjuntos [math]. Sea [math] el i-ésimo término de [math]. Coloquemos cada [math], [math] en el [math] término de una permitación [math] de los números del [math] al [math]. (Podemos hacer esto porque [math], que es el máximo término de [math]. También, estos [math] recorren todos los valores del [math] al [math], si recorremos todos los valores de [math] e [math]).

Veamos que esta permutación [math] está contada en [math]. El número [math] está en una posición [math]. Es obvio que el producto de esos dos es un cuadrado perfecto. Luego, la cantidad de tales permutaciones [math] es simplemente el producto de todas las permutaciones de [math], que es [math]. Para ver que no hay otra permutación, asumamos que hay una permutación [math] tal que para algún [math], [math] ([math] es el lugar que tiene [math] en la permutación [math] sea un cuadrado perfecto. Pero entonces [math] y [math] estarían en el mismo [math] y ya habríamos contado esa permutación. Por ende, esas son todas.

Sé que esos parrafo anterior son díficiles de digerir. La idea es que si cogemos una permutación de [math] y ponemos a la i-ésima entrada de esa permutación en el lugar [math], donde [math] es el i-ésimo término de [math], el producto de el número y el lugar en el que está serían un cuadrado perfecto.

Ahora que tenemos una formula de [math] como un producto de factoriales, tenemos que encontrar el menor de estos productos que es divisible por [math]. Como [math], es primo, basta encontrar el menor [math] con un términ [math] mayor o igual que [math], ya que el factorial de este sería divisiblw por [math]. Es decir queremos buscar el mínino [math] para el cual, para cierto [math]: [math].

Como buscamos el menor, asumamos que la desigualdad es igualdad e ignoremos los signos de piso y elevemos al cuadrado:

[math]. Es obvio que el valor más pequeño de [math] entonces es para [math] y da [math].

En fin, el valor más pequeño de [math] que cumple que [math] es [math].
1  
Para todo [math], existen [math] primos en sucesión aritmética.

Responder