Deje $N=\{a_1,a_2,...,a_n\}$ ser un conjunto de números enteros cada $\ge$ $1$. Deje $P(k)$ ser el producto de la ${n\choose k}$ LCMs de todas las $k$-bloques de $N$ (subconjuntos de a $N$ $k$ elementos). Problema: Demostrar que el MCD de a $N$ es igual a $$\frac{P(1)P(3)P(5)\cdots}{P(2)P(4)P(6)\cdots}.$$
Respuesta
¿Demasiados anuncios?
Supongamos por el momento que $p$ es algunos de los mejores y que $\{a_1,\dots,a_n\} = \{p^{b_1},\dots,p^{b_n}\}$. Entonces el MCD de a $\{a_1,\dots,a_n\}$ es sólo $p^{\min\{b_1,\dots,b_n\}}$, mientras que el LCM de cualquier $k$-bloque es sólo $p$ hasta el máximo de la $b_j$ ocurren en ese bloque. Por lo tanto, en este caso especial, el problema es equivalente a la siguiente:
Deje $M = \{b_1,\dots,b_n\}$ ser un conjunto de números enteros no negativos. Deje $Q(k)$ la suma de los $\binom nk$ máximos de todas las $k$-bloques de $M$. Muestran que el mínimo de $M$ es igual a $$ P(1) - P(2) + P(3) - P(4) + P(5) - P(6) + \cdots. $$ Esto no es demasiado difícil de probar (tenga en cuenta que la reordenación de los elementos no importa, así que sin pérdida de generalidad $b_1 \le b_2\le \cdots\le b_n$).
La razón de este caso especial es que vale la pena mencionar es que el problema original puede ser probada de un primer a un tiempo. En otras palabras, se puede demostrar que el MCD de a $N$ es igual al producto/cociente de la $P(k)$ demostrando que, para cada prime $p$, el poder de la $p$ dividiendo el MCD es igual a la potencia de $p$ dividiendo el producto o cociente.
