Demostrar que el producto de los primos en algún subconjunto de $n+1$ enteros es un cuadrado perfecto.

Question

Estoy tratando de probar lo siguiente:

El conjunto $A$ consiste en $n + 1$ enteros positivos, ninguno de los cuales tiene un divisor primo que sea mayor que el $n$ número primo más pequeño. Demostrar que existe un subconjunto no vacío $B\subseteq A$ tal que el producto de los elementos de $B$ es un cuadrado perfecto.

Es evidente que cada número es del tipo $2^{\alpha_1}3^{\alpha_2}5^{\alpha_3}\cdots p_n^{\alpha_n}$ donde $p_n$ es el $n$ número primo y $\alpha_i\ge 0$ .

Ahora bien, si me dieran más entonces $2^n$ números entonces podría haber dividido los números por la paridad de los exponentes de los primos en $2^n$ clases. Por el principio de encasillamiento, dos números estarían en la misma clase y, por tanto, su producto sería un cuadrado perfecto.

Ya que se me da $n+1$ números que necesito para dividirlos en $n$ clases para que funcione el casillero. Lo obvio es dividir en clases mod $n$ . Pero es evidente que esto no funciona, como se desprende de $n=4$ y los números $2,3,5,6,7$ .

¿Sugerencias de Anu sobre cómo debo probar este resultado?

Answer 1

Aquí hay una buena presentación de la prueba usando álgebra lineal:

Identificar cada número $p_1^{a_1}\dots p_n^{a_n}$ con la tupla $(a_1,\dots,a_n)$ con cada $a_i$ módulo reducido $2$ y observe que multiplicar números corresponde a sumar sus tuplas, y que un cuadrado es precisamente un número cuya tupla asociada es $(0,\dots,0)$ .

Podemos pensar en estas tuplas como vectores en ${\mathbb F_2}^n$ , donde $\mathbb F_2$ es el campo de dos elementos. Se trata de un espacio vectorial de dimensión $n$ y $n+1$ están dados, por lo que son linealmente dependientes, es decir, existe una combinación lineal no trivial de ellos que es igual a $0$ . Pero una combinación lineal no es más que la suma de algunas de ellas (ya que los únicos escalares son $0$ y $1$ ), y hemos terminado.

Answer 2

Ah, ya ves, te dan $n+1$ números, sino cuántos subconjuntos de esos números tienes?

Si tienes un conjunto $B$ cuyos elementos se multiplican por $\pi=p_{1}^{\beta_1}\cdots p_n^{\beta_n}$ , separa la parte libre de cuadrados, de modo que $\pi=m^2\chi$ donde $\chi$ es algún producto de primos distintos. Hay $2^n-1$ conjuntos no vacíos de primos distintos de $p_1,\ldots,p_n$ y $2^{n+1}-1$ subconjuntos no vacíos de su $n+1$ enteros, así que aquí es donde se puede utilizar el principio de encasillamiento.

Después de tener sus conjuntos $A$ y $B$ con el mismo $\chi$ partes, el producto de sus $\pi$ 's es un cuadrado perfecto como has dicho. Este número en sí mismo puede no ser un $\pi$ de cualquier subconjunto; en ese momento, debe buscar $(A\cup B)\setminus (A \cap B)$ y demostrar que ese es su cuadrado perfecto.

Answer 3

Dada la $n+1$ números, ¿cuántos productos no vacíos hay? Cada producto es $2^{\beta_1}3^{\beta_2}\cdots p_n^{\beta_n}$ ¿Cuántas "cajas de paridad" hay para los exponentes? Ahora puedes utilizar el encasillamiento, aunque todavía tienes que resolver cómo terminar las cosas una vez que tienes tus dos palomas en el mismo agujero.

Answer 4

Para un número $n=\prod_{i=1}^np_i^{e_i}$ , donde $p_i$ son números primos distintos, definimos la parte no cuadrada $$u(n)=\prod_{i=1}^np_i^{e_i\bmod 2}$$ Así, por ejemplo $u(6)=6,u(9)=1,u(12)=3,u(24)=6$ . De esta definición obtenemos

$$u(mn)=u(u(m)u(n)),\,\forall m,n \in \mathbb N \tag {a1}$$ $$u(u(n)u(n))=1, \,\forall n \in \mathbb N \tag{a2}$$

Desde $(a1)$ y $(a2)$ obtenemos

$$u(n^2)=1, \,\forall n \in \mathbb N \tag {b1}$$ $$u(u(n))=u(n), \,\forall n \in \mathbb N \tag {b2}$$

$$u(\prod_{i=1}^nm_i)=u(\prod_{i=1}^nu(m_i)), \,\forall m_i \in \mathbb N \tag {b3}$$

$$u(km)=u(kn) \implies u(mn)=1, \,\forall k,m,n \in \mathbb N \tag{b4}$$

---

Prueba por el principio de los casilleros

Desde $n+1$ números $a_1,\ldots,a_{n+1}$ se puede construir $2^{n+1}-1$ productos

$$\prod_{i=1}^{n+1}a_i^{e_i}, e_i \in \{0,1\}, (e_1,\ldots,e_{n+1})\ne(0,\ldots,0)\tag 1$$ a partir de la cual podemos crear $2^{n+1}-1$ piezas no cuadradas $$u\left(\prod_{i=1}^{n+1}a_i^{e_i}\right), e_i \in \{0,1\}, (e_1,\ldots,e_{n+1})\ne(0,\ldots,0) \tag 2$$ que puede tomar $2^n$ valores diferentes $$\prod_{i=1}^np_i^{e_i}, e_i \in \{0,1\}\tag 3$$

por lo que, según el principio del encasillamiento, hay al menos dos productos diferentes $(3)$ , $\prod_{t=1}^{n_1}a_{i_t}\cdot\prod_{t=1}^{n_2}a_{j_t}$ y $\prod_{t=1}^{n_1}a_{i_t}\cdot\prod_{t=1}^{n_3}a_{k_t}$ con $\{a_{i_1},\ldots,a_{i_{n_1}}\}$ , $\{a_{j_1},\ldots,a_{j_{n_2}}\}$ y $\{a_{k_1},\ldots,a_{k_{n_3}}\}$ son disjuntos entre sí y de manera que su parte no cuadrada $(2)$ es igual $$u\left(\prod_{t=1}^{n_1}a_{i_t}\cdot\prod_{t=1}^{n_2}a_{j_t}\right)=u\left(\prod_{t=1}^{n_1}a_{i_t}\cdot\prod_{t=1}^{n_3}a_{k_t}\right)$$
y así por $(b4)$ $$u\left(\prod_{t=1}^{n_2}a_{j_t}\cdot \prod_{t=1}^{n_3}a_{k_t}\right)=1$$ así que $\prod_{t=1}^{n_2}a_{j_t}\cdot \prod_{t=1}^{n_3}a_{k_t}$ es un cuadrado perfecto y el producto de $n_2+n_3$ números diferentes $a_i$ .

---

Prueba por inducción

La existencia de dicho número también se puede demostrar por inducción sin utilizar el principio de la colombofilia.

Para $n=1$ tenemos $a_1=p_1^{e_{1,1}}$ y $a_2=p_1^{e_{1,2}}$ . Uno de $a_1,a_2$ o $a_3=p_1^{e_{1,1}+e_{1,2}}$ tiene un exponente par y por tanto es un cuadrado perfecto.

Si ya está probado para $n-1$ números primos entonces, dado $n$ números primos $p_1,\ldots,p_n$ y $n+1$ números $a_1,\ldots,a_{n+1}$ construido por estos primos entonces aplicamos la hipótesis de inducción a los primos $p_1,\ldots,p_{n-1}$ y $a'_1,\ldots,a'_n$ , donde $a'_i$ es $a_i$ dividido por la mayor potencia de $p_n$ que divide $a_i$ . Hay un conjunto $i_1,\ldots,i_n$ tal que $a'_{i_1}\cdot\ldots\cdot a'_{i_k}$ es un cuadrado perfecto y por lo tanto o bien $a_{i_1}\cdot\ldots\cdot a_{i_k}$ es un cuadrado perfecto o $u(a_{i_1}\cdot\ldots\cdot a_{i_k})=p_n$ Ahora aplicamos de nuevo la hipótesis de inducción a los primos $p_1,\ldots,p_{n-1}$ y el $n$ números $a'_1,\ldots,a'_{n+1}$ sin $a'_{i_1}$ del resultado anterior. Obtenemos un $j_1,\ldots,j_m$ de manera que $a_{j_1}\cdot\ldots\cdot a_{j_m}$ es un cuadrado perfecto o $u(a_{j_1}\cdot\ldots\cdot a_{j_m})=p_n$ O hemos encontrado un cuadrado perfecto o $$u(a_{i_1}\cdot\ldots\cdot a_{i_k})=u(a_{j_1}\cdot\ldots\cdot a_{j_m})$$ y de nuevo podemos construir un cuadrado perfecto mediante $(b4).$