Algoritmo basado en el principio de encasillamiento

Question

Estaba intentando resolver este problema. http://olympiads.hbcse.tifr.res.in/olympiads/wp-content/uploads/2016/09/inmosol-15.pdf

INMO-2015 P6. A partir de un conjunto de $11$ enteros cuadrados, demuestre que se puede elegir $6$ números $a^2, b^2, c^2, d^2, e^2, f^2$ tal que $a^2 + b^2 + c^2 \equiv d^2 + e^2 + f^2 \mod 12$ .

Se me ocurrió la siguiente solución.

---

Observamos que hay 4 residuos distintos módulo $12$ a saber $\{0,1,4,9\}$ .

LEMA:

Entre 5 cuadrados cualesquiera podemos encontrar un par que sea congruente módulo 12. Como hay como máximo 4 residuos únicos mod 12, por la Principio de encasillamiento debemos tener dos cuadrados con el mismo residuo.

---

Describimos el siguiente algoritmo para encontrar $a,b,c,d,e,f$ .

1. Etiqueta el conjunto de los 11 cuadrados dados $\mathbf{Z}=\{Z_1,Z_2,Z_3\ldots\}$ y que $\mathbf{R}=\{\},\mathbf{L}=\{\}$ .
2. Consideremos el conjunto de los 5 últimos elementos. Entre estos elementos, podemos elegir dos elementos con el mismo residuo. Pongamos uno de ellos en $\mathbf{R}$ y el otro en $\mathbf{L}$
3. Retire los elementos de $\mathbf{Z}$ .
4. Repita el paso 2 dos veces más. Podemos hacer esto porque cada paso elimina dos elementos, y necesitamos eliminar sólo 6 elementos por lo que en cada paso todavía tenemos 5 elementos con los que trabajar.

De hecho, según mis cuentas, podemos hacer esto una vez más y terminar con 4 enteros en $\mathbf{R},\mathbf{L}$ cada uno.

---

Mis problemas

1. ¿Es un algoritmo un estilo de prueba válido?
2. Si es así, ¿algún consejo para escribirlo mejor?
3. ¿Es posible el 4º entero?

Gracias de antemano.

Answer 1

1. Su argumento es correcto y agradable.

2. Yo lo generalizaría: "Que $S$ sea un conjunto finito. Sea $d$ y $k$ sean dos enteros no negativos. Sea $\sim$ sea una relación de equivalencia en $S$ tal que haya como máximo $d$ clases de equivalencia con respecto a $\sim$ . Supongamos que $\left|S\right| \geq d + 2k-1$ . Entonces, podemos encontrar $2k$ elementos distintos $s_1, s_2, \ldots, s_k, t_1, t_2, \ldots, t_k$ de $S$ tal que $s_1 \sim t_1$ , $s_2 \sim t_2$ , ..., $s_k \sim t_k$ ." Ahora que ha girado el $k$ en una variable propia, puedes hacer inducción sobre $k$ esto ofrece una descripción más clara que el algoritmo (pero, por supuesto, no es más que una reformulación recursiva de este último).

3. Sí, porque $11 \geq 4 + 2 \cdot 4 - 1$ . Obsérvese que la introducción de un $4$ -ésimo entero en el problema original no lo hace más fuerte, porque $a^2 + b^2 + c^2 + d^2 \equiv e^2 + f^2 + g^2 + h^2 \mod 12$ no implica $a^2 + b^2 + c^2 \equiv e^2 + f^2 + g^2 \mod 12$ . Sólo cuando hayas fortalecido $a^2 + b^2 + c^2 \equiv e^2 + f^2 + g^2 \mod 12$ a $a \equiv e \mod 12,\ b \equiv f \mod 12,\ c \equiv g\mod 12$ ¿el $4$ -th entero se convierten en una ventaja evidente.

Answer 2

Una vez que sepas por dónde vas, puedes reescribir la prueba para que sea más limpia y nítida.

Punto 1: Como sólo hay $4$ residuos cuadrados distintos $\mod 12$ ( $0^2\equiv 6^2\equiv 0; 1^2\equiv5^2 \equiv 7^2 \equiv 11^2\equiv 1; 2^2\equiv 4^2 \equiv 8^2 \equiv 10^2 \equiv 4; 3^2\equiv 9^2 \equiv 9$ ) entonces

Punto 2: Dado cualquier grupo de $5$ o más números enteros como mínimo $2$ al cuadrado pertenecerán al mismo residuo (uno de los cuatro residuos posibles) por el principio de pigeon hole.

Punto 3: De los once números enteros podemos etiquetarlos y ordenarlos como $\{x_{11},x_{10}, x_9, .... , x_1\}$ para que $x_{11}$ y $x_{10}$ se seleccionan entre $\{x_{11},x_{10}, x_9, .... , x_1\}$ que cuenta con más de $5$ de modo que $x_{11}^2 \equiv x_{10}^2\mod 12$ . Y mientras $2m + 1\ge 5$ (es decir $m \ge 2$ ), $x_{2m+1}$ y $x_{2m}$ se eligen entre $\{x_{2m+1} ,...., x_1\}$ para que $x_{2m+1}^2 \equiv x_{2m}^2 \mod 12$ .

Conclusiones: Así que para $m=2,3,4,5$ tenemos $x_{2m+1}^2 \equiv x_{2m}^2$ y por lo tanto:

$x_4^2 + x_6^2 + x_8^2 \equiv x_5^2 + x_7^2 + x_9^2$ ;

$x_4^2 + x_6^2 + x_8^2+x_{10}^2 \equiv x_5^2 + x_7^2 + x_9^2+x_{10}^2$