Un principio de encasillamiento de la lista de la OMI.

Question

Hasta ahora he resuelto muchos problemas del principio de encasillamiento. El enunciado del problema es el siguiente

Sea $p$ sea un primo impar. Consideremos $p-1$ enteros positivos $x_1,x_2,x_3,...,x_{p-1}$ ninguna de las cuales es divisible por $p$ . A continuación, considere todas las sumas posibles de la forma $\pm x_1 \pm x_2 \pm x_3 \pm \cdots \pm x_{p-1}$ . Es evidente que existen $2^{p-1}$ tales sumas. Demostrar que al menos una de estas sumas es divisible por $p$ .

Answer 1

Demostraremos por inducción lo siguiente

Reclamación. Sea $1\le k \le p-1$ sea un número entero. Supongamos que $x_1, x_2, \ldots, x_k$ son números enteros, ninguno de ellos divisible por $p$ . Entonces el conjunto $$\{\varepsilon_1x_1 + \varepsilon_2 x_2 \ldots +\varepsilon_k x_k \pmod{p} \ \colon \ \varepsilon_i \in \{\pm 1\} \text{ for } i=1,2,\ldots,k \}$$ tiene al menos $k+1$ elementos.

Prueba. Si $k=1$ entonces la tesis es cierta. En efecto, puesto que $p \nmid x_1$ , $$x_1 \not\equiv -x_1 \pmod p \iff 1 \not\equiv -1 \pmod p$$ lo cual es cierto ya que $p$ es impar.

Supongamos ahora que para algunos $1\le k<p-1$ el conjunto $$\{\varepsilon_1x_1 + \varepsilon_2 x_2 \ldots +\varepsilon_k x_k \pmod{p} \ \colon \ \varepsilon_i \in \{\pm 1\} \text{ for } i=1,2,\ldots,k \}$$ tiene al menos $k+1$ elementos. Si este conjunto tiene $k+2$ elementos distintos entonces claramente el conjunto $$\{\varepsilon_1x_1 + \varepsilon_2 x_2 \ldots +\varepsilon_k x_k + x_{k+1} \pmod{p} \ \colon \ \varepsilon_i \in \{\pm 1\} \text{ for } i=1,2,\ldots,k \}$$ tiene al menos $k+2$ y, por tanto, su superconjunto $$\{\varepsilon_1x_1 + \varepsilon_2 x_2 \ldots +\varepsilon_k x_k + \varepsilon_{k+1} x_{k+1} \pmod{p} \ \colon \ \varepsilon_i \in \{\pm 1\} \text{ for } i=1,2,\ldots,k,k+1 \}$$ tiene al menos $k+2$ elementos. Así pues, la tesis de la alegación es cierta en este caso.

Supongamos ahora que el conjunto $$\{\varepsilon_1x_1 + \varepsilon_2 x_2 \ldots +\varepsilon_k x_k \pmod{p} \ \colon \ \varepsilon_i \in \{\pm 1\} \text{ for } i=1,2,\ldots,k \}$$ tiene exactamente $k+1$ elementos. Sea $y_1, y_2, \ldots, y_{k+1}$ sean los elementos de este conjunto.

Afirmamos que los conjuntos $$\{\varepsilon_1x_1 + \varepsilon_2 x_2 \ldots +\varepsilon_k x_k + x_{k+1} \pmod{p} \ \colon \ \varepsilon_i \in \{\pm 1\} \text{ for } i=1,2,\ldots,k \} = \\ \{y_i + x_{k+1} \pmod p \ \colon \ i=1,2,\ldots,k+1 \}$$ y $$\{\varepsilon_1x_1 + \varepsilon_2 x_2 \ldots +\varepsilon_k x_k - x_{k+1} \pmod{p} \ \colon \ \varepsilon_i \in \{\pm 1\} \text{ for } i=1,2,\ldots,k \}= \\ \{y_i-x_{k+1} \pmod p \ \colon \ i=1,2,\ldots,k+1 \}$$ son distintos. Supongamos que estos conjuntos son iguales. Comparando su suma módulo $p$ conduce a $$y_1+y_2+\ldots+y_{k+1} + (k+1)x_{k+1} \equiv y_1+y_2+\ldots+y_{k+1} - (k+1)x_{k+1} \pmod p,$$ es decir $$(k+1)x_{k+1}=-(k+1)x_{k+1} \pmod p.$$ Desde $p\nmid x_{k+1}$ y $p\nmid k+1$ tenemos $1\equiv -1 \pmod p$ lo cual es una contradicción, ya que $p$ es impar. Con esto termina la prueba de la reclamación. $\square$

Ahora utilizamos la demanda de $k=p-1$ . De ello se deduce que el conjunto $$\{\varepsilon_1x_1 + \varepsilon_2 x_2 \ldots +\varepsilon_{p-1} x_{p-1} \pmod{p} \ \colon \ \varepsilon_i \in \{\pm 1\} \text{ for } i=1,2,\ldots,p-1 \}$$ tiene al menos $p$ elementos. Así, uno de ellos es $0 \pmod p$ ya que sólo hay $p$ residuos módulo $p$ . Con esto termina la prueba.

Answer 2

¿Qué le parece utilizar el Cauchy-Davenport ¿teorema?

A saber, consideremos los conjuntos $A_i = \{x_i, -x_i\}$ . Desde $p$ es impar, $|A_i|=2$ para todos $i$ . Ahora observe que $$ |A_1 + A_2| \geq 2 + 2 - 1 = \min\{p, 3\}$$ Ahora se puede demostrar por inducción que $$|A_1 + \ldots + A_k| \geq \min\{p, k+1\}$$ En efecto, suponiendo la hipótesis, el teorema nos da $$|A_1 + \ldots + A_k + A_{k+1}| \geq \min\{p, \min\{p, k+1\} + 2 - 1\}=\min\{p, k+2\}$$ y así al final $$|A_1 + \ldots + A_{p-1}|\geq \min\{p,p\}=p$$ así que de hecho hemos demostrado algo más fuerte: podemos escribir cualquier residuo módulo $p$ como una suma de la forma $\pm x_1 \pm\ldots\pm x_{p-1}$ .