Una permutación del conjunto [math][n]=\{1,2,\ldots,n\} es una sucesión [math](a_1,a_2,\ldots,a_n) tal que cada elemento de [math][n] aparece exactamente una vez como un termino de la sucesión. Por ejemplo, [math](6,2,4,1,3,5) es una permutación [math][6]. Sea [math]P(n) la cantidad de permutaciones de [math][n] para las cuales [math]ka_k es un cuadrado perfecto para todo [math]1\leq{k}\leq{n}. Hallar el menor entero positivo [math]n tal que [math]2018\mid{P(n)}
Notemos que [math]P(n)>0\forall n, ya que cuando los números aparecen en orden creciente [math]a_k=k\Rightarrow ka_k=k\times k=k^2\forall 1\leq k\leq n.
Entonces tenemos que [math]2018=2\times 1009\Rightarrow 2\mid P(n) \wedge 1009\mid P(n)(*)
Digo que una permutación es válida si cumple que [math]ka_k es un cuadrado perfecto para todo [math]1\leq k\leq n
Lema:
Dada una permutación válida, [math]s 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]a_k,a_kb^2=a_{k+i},\ldots a_kd^2, es decir, cada uno de los números es el producto de un número por un cuadrado. Siendo [math]a_k el [math]DCM del conjunto.
Demostración:
La ida se ve fácil ya que el producto de dos cuadrados es un cuadrado, si [math]ta_k es un cuadrado, entonces [math]ta_kb^2 es un cuadrado y si [math]ta_kb^2 es un cuadrado, entonces [math]ta_k 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]t y [math]th, tenemos entonces que [math]ta_k es un cuadrado y que [math]tha_k es un cuadrado, pero entonces [math]h es un cuadrado.
Esto nos dice que [math]P(n)=r\times P(n-1)(**). Por (*) tenemos que [math]1009\mid P(n), como [math]1009 es primo, entonces necesitamos una permutación válida que pueda permutarse una cantidad de veces múltiplo de [math]1009. Como queremos el mínimo, entonces esa cantidad tiene que ser [math]1009.
Por lo tanto, lo que buscamos es un número que puede cambiarse de lugar con [math]1008 números menores (por el lema sabemos que si [math]x puede cambiarse con [math]z y [math]x puede cambiarse con [math]y, entonces [math]y puede cambiarse con [math]z).
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]1009^2 tiene [math]1008 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]t un entero positivo y [math]c_i un cuadrado para todo [math]i ([math]c_i puede o no ser igual a [math]c_j). Sean [math]t_l[math]1\leq l\leq 1009 los términos intercambiables, tenemos entonces [math]t_1=t,t_2=tc_1,t_3=tc_2\ldots t_n=t\prod_{i=1}^{n-1}c_i=t\left (\prod_{i=1}^{n-1}o_i\right )^2, siendo [math]o_i=\sqrt{c_i}. En particular, [math]t_{1009}=t\left (\prod_{i=1}^{1008}o_i\right )^2, como queremos que [math]t_{1009} sea mínimo, entonces [math]t=1. Ahora, se ve fácilmente que [math]2^{10}>1009>2^9, [math]3^7>1009>3^6, [math]5^5>1009>5^4, [math]7^4>1009>7^3, [math]11^3>1009>11^2. Entonces como queremos que [math]\prod_{i=1}^{n-1}o_i<1009, el [math]2 puede aparecer como mucho [math]9 veces, el [math]3 como mucho [math]6 veces, el [math]5 como mucho [math]4 veces, el [math]7 como mucho [math]3 veces y cualquier número del [math]11 en adelante como mucho [math]2 veces. Consultando la Criba de Eratóstenes (o tabla de números primos), vemos que hay [math]168 primos menores a [math]1009, si descontamos a [math]2,3,5,7 tenemos [math]164 que aparecerán a lo sumo [math]2 veces en el productorio (en realidad, hay varios que no pueden aparecer juntos, por ejemplo [math]101 y [math]103, pero no importa), por lo tanto tendremos a lo sumo [math]164\times 2+9+6+4+3=350 términos en el productorio, pero éste tiene [math]1008 términos. Absurdo.
El absurdo provino de suponer que existía un número menor que [math]1009^2 tal que multiplicado por [math]1008 números menores fuese siempre un cuadrado, entonces, [math]1009^2 es el menor de ellos.
Comprobando a mano las [math]4! permutaciones de [math][4] vemos que [math]P(4)=2, por (**) tenemos que [math]P(1009^2)=e\times P(4)=2e, entonces [math]2\mid P(1009^2)\wedge 1009\mid P(1009^2)\Rightarrow 2018\mid P(1009^2)
Queda demostrado que el menor entero positivo que cumple es [math]n=1009^2
Consideremos los conjuntos [math]A_k = \{ k\times n^2 : n=1,2,3 \ldots \}, donde [math]k es un número de la forma [math]p_1p_2\ldots p_i, donde los [math]p_i son primos (incluimos los valores de primos y el [math]1 también). *Siempre que mencionemos [math]k de aquí en adelante nos referimos a un número de esa forma*
Ahora, varios hechos sobre los [math]A_k.
0. Todo entero está en un [math]A_k.
Demostración: Trivial.
1. Dos números tienen como producto un cuadrado perfecto sii están en el mismo [math]A_k.
Demostración: El "si" es trivial. Probaremos el "solo si". Asumamos que hay dos números [math]x y [math]y en distintos [math]A_k con producto de cuadrado perfecto. Digamos [math]x=n\times a^2 \in A_n y [math]y=m \times b^2 \in A_m. Entonces [math]nm tiene que ser un cuadrado perfecto, que es absurdo porque hay por lo menos un primo [math]p que está en uno de los dos números y no en el otro, porque [math]n y [math]m son distintos. Como este primo [math]p tiene exponente impar, [math]nm no es cuadrado perfecto, de donde se llega al absurdo y [math]n=m.
2. No hay dos [math]A_ks con un término en común.
Demostración: Asumamos que hay tres númeroz [math]x,y,z con [math]x en [math]A_n pero no en [math]A_m, [math]z en [math]A_m pero no en [math]A_n (vemos que estos existen porque el primer elemento del conjunto [math]A_k es [math]k y [math]n \neq m) y [math]y en ambos. Como consecuencia de (1), [math]xy y [math]yz son cuadrados perfectos, de donde [math]xz es un cuadrado perfecto. Pero entonces, por (2), [math]n=m. Absurdo.
3. Si [math]x_k(n) es la cantidad de elementos de [math]A_k que son menores que [math]n, pues [math]x_k(n)= \left \lfloor \sqrt{ \left \lfloor \frac{n}{k} \right \rfloor } \right \rfloor
Demostración: [math]\left \lfloor \frac{n}{k} \right \rfloor es sabido que es la cantidad de números menores que [math]n divisiables por [math]k. Si tomamos la raíz cuadrado y función piso de esa cantidad, pues tenemos la cantidad de números menores que [math]n divisibles por [math]k que están multiplicados por un cuadrado perfecto.
4. [math]P(n) = \prod (x_k(n)!)
Demostración: Consederemos conjuntos [math]A_k(n) con todos los elementos de [math]A_k menores o iguales que [math]n. Ahora consideremos permutaciones [math]A'_k(n) de estos conjuntos [math]A_k(n). Sea [math]a_{i,k} el i-ésimo término de [math]A'_k(n). Coloquemos cada [math]a_{i,k}, [math]1 \leq i \leq x_k en el [math]k \times i^2 término de una permitación [math]\pi de los números del [math]1 al [math]n. (Podemos hacer esto porque [math]k \times i^2 \leq k\times x_k^2, que es el máximo término de [math]A_k(n). También, estos [math]k \times i^2 recorren todos los valores del [math]1 al [math]n, si recorremos todos los valores de [math]k e [math]i).
Veamos que esta permutación [math]\pi está contada en [math]P(n). El número [math]k \times i^2 está en una posición [math]k \times j^2. Es obvio que el producto de esos dos es un cuadrado perfecto. Luego, la cantidad de tales permutaciones [math]\pi es simplemente el producto de todas las permutaciones de [math]A_k(n), que es [math]x_k(n)!. Para ver que no hay otra permutación, asumamos que hay una permutación [math]\pi' tal que para algún [math]n, [math]n\times p_n ([math]p_n es el lugar que tiene [math]n en la permutación [math]\pi sea un cuadrado perfecto. Pero entonces [math]n y [math]p_n estarían en el mismo [math]A_k 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]A_k(n) y ponemos a la i-ésima entrada de esa permutación en el lugar [math]x_{i,k,n}, donde [math]x_{i,k,n} es el i-ésimo término de [math]A_k(n), 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]P(n) como un producto de factoriales, tenemos que encontrar el menor de estos productos que es divisible por [math]2018=2 \times 1009. Como [math]1009, es primo, basta encontrar el menor [math]P(n) con un términ [math]x_k(n) mayor o igual que [math]1009, ya que el factorial de este sería divisiblw por [math]2018. Es decir queremos buscar el mínino [math]n para el cual, para cierto [math]k: [math]\left \lfloor \sqrt{ \left \lfloor \frac{n}{k} \right \rfloor } \right \rfloor \geq 1009.
Como buscamos el menor, asumamos que la desigualdad es igualdad e ignoremos los signos de piso y elevemos al cuadrado:
[math]\frac{n}{k} = 1009^2. Es obvio que el valor más pequeño de [math]n entonces es para [math]k=1 y da [math]n=1009^2.
En fin, el valor más pequeño de [math]n que cumple que [math]2018 \mid P(n) es [math]n=1009^2.
